\documentstyle[12pt,pslatex]{article}
%\renewcommand{\baselinestretch}{2}
\begin{document}

\def\frak{\cal }
\def\Bbb{\bf }

\title{Solution of problem \#10769}
\author{Karl Svozil\\
 {\small Institut f\"ur Theoretische Physik,}
  {\small Technische Universit\"at Wien }     \\
  {\small Wiedner Hauptstra\ss e 8-10/136,}
  {\small A-1040 Vienna, Austria   }            \\
  {\small e-mail: svozil@tuwien.ac.at}}
\date{ }
\maketitle

\begin{flushright}
{\scriptsize
http://tph.tuwien.ac.at/$\widetilde{\;\;}\,$svozil/publ/blatter.$\{$htm,ps,tex$\}$}
\end{flushright}

\begin{abstract}
We review previous solutions of problem nr. 10769 posed by Christian Blatter
\end{abstract}

A 1988 paper by C. D. Godsil and J. Zaks \cite{godsil-zaks} states the following result, which is
the solution of problem nr. 10769:

{\em ``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 $\pi /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
$\theta$ be the angle between the $z-$axis and the line connecting the origin and the point, and
$\varphi$ 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
$(\theta, \varphi, r=1) \equiv (\theta,\varphi)$.
\begin{itemize}
\item
The colors of the cartesian coordinate axes $(\pi/2,0)$, $(\pi/2,\pi/2)$, $(0,0)$
are
green,
blue and  red, respectively.
\item
The color of the octant
$\{(\theta, \varphi ) \mid 0 < \theta \le \pi /2,\; 0\le \varphi < \pi/2\}$ is green.
\item
The color of the  octant
$\{(\theta, \varphi ) \mid 0 \le \theta < \pi /2,\; \pi /2 \le \varphi \le \pi\}$ is red.
\item
The color of the octant
$\{(\theta, \varphi ) \mid 0 < \theta < \pi /2,\; \pi  < \varphi < -\pi /2\}$ is white.
\item
The color of the octant
$\{(\theta, \varphi ) \mid 0 < \theta \le \pi /2,\; -\pi /2  \le \varphi < 0\}$ is blue.
\item
The colors of the points in the half space $z<0$ are inherited from their antipodes.
This completes the coloring of the sphere.
\end{itemize}


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 \cite{hales}, but refer to an old result of
E. Specker \cite{specker-60} and S. Kochen and E. Specker \cite{kochen1},
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 $\pi /2$ apart get different colors.'')

Indeed, already in 1967, S. Kochen and E. Specker \cite{kochen1}
gave an explicit example (their $\Gamma_3$)
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 \cite{godsil-zaks} also proved the following
rather unexpected result: {\em The chromatic number of the
 the subgraphs of $G$ induced by the unit
vectors with all coordinates rational (i.e., the {\em rational} unit sphere) is three.}
They gave an explicit construction for which each color class is dense in the sphere.




%\bibliography{svozil}
%\bibliographystyle{unsrt}
%\bibliographystyle{plain}


\begin{thebibliography}{1}

\bibitem{godsil-zaks}
C.~D. Godsil and J.~Zaks.
\newblock Coloring the sphere.
\newblock University of Waterloo research report CORR 88-12, 1988.

\bibitem{hales}
A.W. Hales and E.G. Straus.
\newblock {Projective colorings.}
\newblock {\em Pac. J. Math.}, 99:31--43, 1982.

\bibitem{hooker}
Clifford~Alan Hooker.
\newblock {\em The logico-algebraic approach to quantum mechanics}.
\newblock D. Reidel Pub. Co., Dordrecht; Boston, [1975]-1979.

\bibitem{kochen1}
Simon Kochen and Ernst~P. Specker.
\newblock The problem of hidden variables in quantum mechanics.
\newblock {\em Journal of Mathematics and Mechanics}, 17(1):59--87, 1967.
\newblock Reprinted in \cite[pp. 235--263]{specker-ges}.

\bibitem{specker-60}
Ernst Specker.
\newblock {D}ie {L}ogik nicht gleichzeitig entscheidbarer {A}ussagen.
\newblock {\em Dialectica}, 14:175--182, 1960.
\newblock Reprinted in \cite[pp. 175--182]{specker-ges}; English translation:
  {\it The logic of propositions which are not simultaneously decidable},
  reprinted in \cite[pp. 135-140]{hooker}.

\bibitem{specker-ges}
Ernst Specker.
\newblock {\em Selecta}.
\newblock Birkh{\"{a}}user Verlag, Basel, 1990.

\end{thebibliography}


\end{document}