Solution of problem #10769

Karl Svozil
Institut für Theoretische Physik, Technische Universität Wien
Wiedner Hauptstraße 8-10/136, A-1040 Vienna, Austria
e-mail: svozil@tuwien.ac.at

http://tph.tuwien.ac.at/[    \tilde] svozil/publ/blatter.{htm,ps,tex}

Abstract

We review previous solutions of problem nr. 10769 posed by Christian Blatter

A 1988 paper by C. D. Godsil and J. Zaks [1] states the following result, which is the solution of problem nr. 10769:

``Let G be the graph with the points of the unit sphere in three dimensions as its vertices, and two vertices adjacent if and only if they are orthogonal as unit vectors (i.e., their spherical distance is p/2. The chromatic number of G is four.''

A proof that four colors suffice for G is constructive and rather elementary. Consider first the intersection points of the sphere with the the x-, the y- and the z-axis, colored by green, blue and red, respectively. There are exactly three great circles which pass through two of these three pairs of points. The great circles can be colored with the two colors used on the four points they pass through. The three great circles divide the sphere into eight open octants of equal area. Four octants, say, in the half space z > 0, are colored by the four colors red, white, green and blue. The remaining octants obtain their color from their antipodal octant.

Although the paper is not entirely specific, it is easy to write down an explicit coloring scheme according to the above prescription. Consider spherical coordinates: let q be the angle between the z-axis and the line connecting the origin and the point, and j be the angle between the x-axis and the projection of the line connecting the origin and the point onto the x-y-plane. In terms of these coordinates, an arbitrary point on the unit sphere is given by (q, j, r=1) (q,j).

The fact that three colors are not sufficient is not so obvious. We shall not review Godsil and Zaks' proof based on a paper by A. W. Hales and E. G. Straus [2], but refer to an old result of E. Specker [5] and S. Kochen and E. Specker [4], which is of great importance in the present debate on hidden parameters in quantum mechanics. They have proven that there does not exist a valuation on the one dimensional subspaces of real Hilbert space in three dimensions. (In physics, each subspace is interpreted as physical proposition, and valuations are interpreted as truth assignments.) The nonexistence of valuations is a stronger result than the impossibility to color the sphere appropriately with three colors, since an appropriate coloring of one dimensional linear subspaces with two colors could be immediately obtained from any possible appropriate coloring of the sphere with three colors by just identifying two of the three colors and taking the linear span of the vectors from the origin to the respective points on the sphere. (``Appropriate'' here means: ``points at spherical distance p/2 apart get different colors.'')

Indeed, already in 1967, S. Kochen and E. Specker [4] gave an explicit example (their G3) of a finite point set of the sphere which is colorable by two colors but not by three colors, although they did not mention nor discuss this particular feature.

C. D. Godsil and J. Zaks [1] also proved the following rather unexpected result: The chromatic number of the the subgraphs of G induced by the unit vectors with all coordinates rational (i.e., the rational unit sphere) is three. They gave an explicit construction for which each color class is dense in the sphere.

References

[1]
C. D. Godsil and J. Zaks. Coloring the sphere. University of Waterloo research report CORR 88-12, 1988.

[2]
A.W. Hales and E.G. Straus. Projective colorings. Pac. J. Math., 99:31-43, 1982.

[3]
Clifford Alan Hooker. The logico-algebraic approach to quantum mechanics. D. Reidel Pub. Co., Dordrecht; Boston, [1975]-1979.

[4]
Simon Kochen and Ernst P. Specker. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics, 17(1):59-87, 1967. Reprinted in [6,pp. 235-263].

[5]
Ernst Specker. Die Logik nicht gleichzeitig entscheidbarer Aussagen. Dialectica, 14:175-182, 1960. Reprinted in [6,pp. 175-182]; English translation: The logic of propositions which are not simultaneously decidable, reprinted in [3,pp. 135-140].

[6]
Ernst Specker. Selecta. Birkhäuser Verlag, Basel, 1990.




File translated from TEX by TTH, version 3.02.
On 7 Mar 2002, 12:18.