
\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=4.00.0.2312}
%TCIDATA{Created=Friday, July 06, 2007 23:36:28}
%TCIDATA{LastRevised=Thursday, August 16, 2007 18:11:00}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
%TCIDATA{CSTFile=40 LaTeX article.cst}

\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}

\begin{document}

\begin{center}
\bigskip {\LARGE The }$\mathbb{C}${\LARGE \ Unit Distance Graph.}

David Cohen

\textbf{ABSTRACT}
\end{center}

\begin{quotation}
We examine some results on coloring the unit distance graph in the plane. \
In particular, we examine Coulson's proof that it cannot be 5-colored by
polygons, and Woodall's result that $
\mathbb{Q}
\lbrack i]$ is 2-colorable.
\end{quotation}

The unit distance graph in the plane is the graph whose vertices are the
points of $
\mathbb{C}
$, with edges connecting any two points a unit distance apart. \ The
Hadwiger-Nelson problem asks the chromatic number of this graph. \ By the
theorem of Erdos and de Bruijn, this is the same as the supremum of the
chromatic numbers attained by finite subgraphs. \ It is known that $4\leq
\chi (
\mathbb{C}
)\leq 7$. \ We obtain the lower bound by noting that in any hypothetical
three-coloring of $
\mathbb{C}
$, two points at a distance of $\sqrt{3}$ would have to be the same color. \
Thus all points of $\{|z|=3\}$ are the same color as 0, but since this set
contains a unit distance we need a fourth color. \ (See diagram 0a.) \ This
construction is due to Moser and Moser. \ The 7 coloring can be obtained by
using regular hexagons of diameter slightly less than 1 as the coloring base
(so the set of points of a given color consists of a union of regular
hexagons.) \ See diagram 0b.

There are many interesting directions from which to approach the theory, two
of which shall be highlighted: first, Coulson's proof that we cannot 5-color
the plain using polygons as a coloring base, and then Woodall's proof that $
\mathbb{Q}
\lbrack i]$ is 2-colorable, which is presented along with a similar proof
that $
\mathbb{Q}
\lbrack \omega ]$ is 3 colorable, where $\omega $ is a third root of unity.
\ The natural conjecture is that $
\mathbb{Q}
\lbrack \alpha ]$ is 3-colorable for all $\alpha $\ quadratic over $
\mathbb{Q}
$. \ "Moser's extension" for instance (i.e., the extension containing $
\omega $ and $\alpha $ where $|\alpha -\sqrt{3}i|=1$ and $|\alpha |=\sqrt{3}$
) is the "simplest" non 3-colorable number field; its degree is 4.

\begin{theorem}
(Coulson[2]): at least 6 colors are required to color $
\mathbb{C}
$ if we use polygons (with convex interior and measure bounded below)\ as
the coloring base. \ (I.e., if the set of points of each color is a union of
polygons with the desired properties.)
\end{theorem}

\begin{proof}
There are several lemmas:

\begin{lemma}
Any path-connected set S of diameter more than 1 contains a unit distance.
\end{lemma}

\begin{proof}Take two points x,y in S such that d(x,y) \TEXTsymbol{>} 1. \ Let $
\alpha :[0,1]\longrightarrow S$ be a path connecting x and y (i.e., $\alpha $
continuous, $\alpha (0)=x$ and $\alpha (1)=y$.)

Then $d(x,\alpha (t))$ achieves the value 1 for some $t\in \lbrack 0,1]$ by
the intermediate value theorem.
\end{proof}

\begin{lemma} Any coloring by polygons contains a point where (at least) three
colors meet \ (see diagram 1.)
\end{lemma}

\begin{proof}Assume otherwise. \ A region is defined to be a "maximal" connected
set whose points are all the same color \ (again, see diagram 1.) \ By lemma
0, no region has diameter greater than 1. \ By assumption, each region is
surrounded by a region of a different color. \ By our lower bound on the
measure of polygons, \ we cannot have a region surrounded by a region
surrounded by a region ad infinitum (since eventually one of these regions
will have diameter greater than 1, as it will surround a set of measure
greater than $\pi $.) \ Thus we have a contradiction (see diagram 2a.)

A tricolor point is one where (at least)\ three colors meet, i.e., it is a
limit point of regions of three different colors.
\end{proof}

\bigskip

\begin{lemma}
The circle C\ of radius 1 around a tricolor point X must pass through at
least two colors (which are neccessarily different from those which meet at
X.) \ This establishes that a coloring by polygons uses at least 5-colors.
\end{lemma}

\begin{proof}
(see diagram 2b) Say colors a, b, and c meet at X. \ Let $R_{Y}$ denote the
region a point Y is in. \ If Y is a point on C, then d(X,Y) = 1. \ For all
but finitely many such Y, we know $\exists \varepsilon >0$ s.t. $%
d(Y,y)<\varepsilon \Longrightarrow y\in R_{Y}$ (in other words, Y is an
interior point of $R_{Y}$ for all but finitely many Y on C, since the $R_{Y}$
are finite unions of polygons with measure bounded below, and C is a
circle.) \ But the ball of radius $\varepsilon $ around X contains points of
colors a, b, and c, so $R_{Y}$ requires a fourth color, d, whenever Y an
interior point of $R_{Y}$ (remember, all points of $R_{Y}$ are the same
color.) \ For such a\ Y, consider $Y^{\prime }\in R_{Y}\cap C$. \ For all
but finitely many such $Y^{\prime }$, the points on C which are at a
distance of 1 from Y' are interior points of their regions, and thus require
a fifth color by the same argument.
\end{proof}

\begin{lemma}
Say we have a 5-coloring by convex polygons, and say the regions which cover
C are (moving clockwise, in order) $S_{1},S_{2},...,S_{n}$. \ Then setting $%
Y_{i}$ to be the place where $S_{i}$ and $S_{i+1}$ meet, we have that for $Y$
on C, $d(Y,Y_{i})=1$ $\Longrightarrow Y=Y_{j}$ for some j. \ (See diagram 3.)
\end{lemma}

\begin{proof}
For $Y$ on C with $d(Y,Y_{i})=1$, we have $Y=Y_{j}$ for some j or Y an
interior point of $R_{Y}$. \ In the latter case, a contradiction arises
because there is an $\varepsilon $ ball around Y contained entirely within $%
R_{Y}$, but any $\varepsilon $ ball around $Y_{i}$ contains both points of
color d and points of color e. \ This proves the lemma.
\end{proof}

Note that if $d(Y_{i},Y_{j})=1$, and Y$_{j}$ is $\pi /3$ radians clockwise
of Y$_{i}$ , then the region clockwise of $Y_{i}$ is the same color as the
region clockwise of Y$_{j}$ (by essentially the same argument.)

With notation as in lemma 3, inscribe a unit hexagon D in C, with Y$_{1}$ a
vertex of D, then the other vertices are Y$_{j}$ as well. \ Let us label
them Z$_{1}$ through Z$_{6}$ going clockwise, with Y$_{1}$ = Z$_{1}$. \ (See
diagram 4.)

\begin{lemma}
>From point \NEG{Z}$_{i}$ , draw a ray R perpendicular to the segment $%
Z_{i}Z_{i+1}$. \ The region lying clockwise of Z$_{i}$ lies entirely to the
right of R.
\end{lemma}

\begin{proof}
(See diagrams 5 and 6.)  If we draw a circle $C^{^{\prime }}$ of radius 1
around Z$_{i+1}$ , it bounds the region lying clockwise of Z$_{i}$. \ But
since this region's boundary is made up of line segments with length bounded
below, the segment which passes through Z$_{i}$ going outward must lie
entirely inside $C^{^{\prime }}$ and thus entirely to the right of R.
\end{proof}

Clearly, we also have that the region lying counterclockwise of \NEG{Z}$_{i}$
is bounded by the ray R$^{^{\prime }}$ which starts at Z$_{i}$ and runs
perpendicular to $Z_{i-1}Z_{i}$.

Thus, we have that the region between R and R$^{^{\prime }}$ near Z$_{i}$ is
colored with a, b, or c. \ We call this region the wedge region at Z$_{i}$.
\ (Of course, there might be several such regions, the point is that at
least 1 exists, and none is colored with d or e.)

We are now ready to complete the proof. \ Consider a ray L out of X which
separates colors a and b at X. \ (Such a ray exists WLOG because we can
permute the labels a, b, and c, and X is a tricolor point.) \ This ray
passes through D between two vertices (or at a vertex, the argument is
similar,) say Z$_{i}$ and Z$_{i+1}$. \ A point close to Z$_{i}$ in the wedge
region cannot be colored a or b, so it must be c, but the same is true of
the wedge region at Z$_{i+1}$. \ Since these regions contain points at a
unit distance from each other, we have obtained the desired contradiction.
\end{proof}

Now we examine the other side of the theory (succesful colorings) by
coloring numberfields.

\begin{theorem}
(Woodall[1]): $
\mathbb{Q}
\lbrack i]$ (as a subset of $
\mathbb{C}
$) is 2-colorable.
\end{theorem}

\begin{proof}
There are three steps:

Step 0: show that $|z|=1$ and $z\in 
\mathbb{Q}
\lbrack i]$ imply $z\in O[i]$, where $O$ is the set of rationals with odd
denominator in lowest terms.

Step 1: show that $O[i]$ is 2-colorable.

Step 2: choose a system $S$ of coset representatives of $
\mathbb{Q}
\lbrack i]/O[i]$, then color $
\mathbb{Q}
\lbrack i]$ by coloring $s+z$ the same color as $z$, where $s\in S$ and $
z\in O[i]$.

Say that $|z|=1$, where $z\in 
\mathbb{Q}
\lbrack i]$. \ Write $z=\frac{1}{c}(a+bi)$ where $a,b,c\in 
\mathbb{Z}
$ and $c$ positive and minimal, then $a^{2}+b^{2}=c^{2}$. \ If $(a,b)\neq 1$%
, we have that $\frac{a}{(a,b)}$, $\frac{b}{(a,b)}$, $\frac{c}{(a,b)}\in 
\mathbb{Z}
$ and $(\frac{c}{(a,b)})^{-1}(\frac{a}{(a,b)}+\frac{b}{(a,b)}i)=z$,
contradicting our assumption that $c$ minimal. \ Thus, at least one of $a,b$
must be odd, but both cannot be odd because then $a^{2}+b^{2}\equiv 2(\func{%
mod}4)$ and $c^{2}\equiv 2(\func{mod}4)$ has no solutions. \ So exactly one
of $a,b$ is odd, thus $c$ is odd, so $\frac{a}{c}$ and $\frac{b}{c}$have odd
denominator when written in lowest terms.

We color $O[i]$\ as follows: color $2O[i]$ and $1+i+2O[i]$ with color 0. \
Color $1+2O[i]$ and $i+2O[i]$ with color 1. \ We showed above that if $z=
\frac{1}{c}(a+bi)$ has norm 1, then exactly one of $a,b$ is odd and $c$ is
odd, so we can see that adding $z$ to something colored with 0 results in
something colored with 1 and vice-versa.

Finally, choose a system $S$ of coset representatives of $
\mathbb{Q}
\lbrack i]/O[i]$, and color $
\mathbb{Q}
\lbrack i]$ by making $s+z$ the same color as $z$, where $s\in S$ and $z\in
O[i]$. \ This is well defined (expression as $s+z$ is unique.) \ If $
z_{1},z_{2}\in
\mathbb{Q}
\lbrack i]$ and $|z_{1}-z_{2}|=1$, then $z_{1}-z_{2}\in O[i]$, so $z_{1}$
and $z_{2}$ are in the same coset, therefore there exists $s\in S$ and $
z_{1}^{\prime },z_{2}^{\prime }\in O[i]$ with $z_{1}=s+z_{1}^{\prime }$ and $
z_{2}=s+z_{2}^{\prime }$. \ But then $|z_{1}^{\prime }-z_{2}^{\prime }|=1$,
so $z_{1}^{\prime }$ and $z_{2}^{\prime }$ have different colors, so $z_{1}$
and $z_{2}$ have different colors. \ We have thus successfully colored $
\mathbb{Q}
\lbrack i]$.
\end{proof}

\begin{theorem}
$
\mathbb{Q}
\lbrack \omega ]$ (as a subset of $
\mathbb{C}
$) is 2-colorable, where $\omega $ is a third root of unity.
\end{theorem}

\begin{proof}
There are three steps:

Step 0: show that $|z|=1$ and $z\in 
\mathbb{Q}
\lbrack \omega ]$ imply $z\in O[\omega ]$, where $O$ is the set of rationals
with denominator not divisible by three in lowest terms.

Step 1: show that $O[\omega ]$ is 2-colorable.

Step 2: choose a system $S$ of coset representatives of $
\mathbb{Q}
\lbrack \omega ]/O[\omega ]$, then color $
\mathbb{Q}
\lbrack \omega ]$ by coloring $s+z$ the same color as $z$, where $s\in S$
and $z\in O[\omega ]$.

Say that $|z|=1$, where $z\in 
\mathbb{Q}
\lbrack \omega ]$. \ Write $z=\frac{1}{c}(a+b\omega )$ where $a,b,c\in 
\mathbb{Z}
$ and $c$ positive and minimal, then $a^{2}+b^{2}-ab=c^{2}$. \ If $(a,b)\neq
1$, we have that $\frac{a}{(a,b)}$, $\frac{b}{(a,b)}$, $\frac{c}{(a,b)}\in 
\mathbb{Z}
$ and $(\frac{c}{(a,b)})^{-1}(\frac{a}{(a,b)}+\frac{b}{(a,b)}\omega )=z$,
contradicting our assumption that $c$ minimal. \ Thus, at least one of $a,b$
must not be divisible by 3. Consider the following table, whose entries are
possible values of $a^{2}+b^{2}-ab$ mod 3:

\begin{tabular}{llll}
a,b & 0 & 1 & 2 \\ 
0 & - & 1 & 2 \\ 
1 & 1 & 1 & 0 \\ 
2 & 2 & 0 & 1%
\end{tabular}

\bigskip We see that $a^{2}+b^{2}-ab$ can only be divisible by 3 if $a\equiv
1$ and $b\equiv 2$ (or vice-versa.) \ We compute:

$(3j+1)^{2}+(3k-1)^{2}-(3j+1)(3k-1)=9j^{2}+6j+1+9k^{2}-6k+1-9jk+3j-3k+1$

$=9j^{2}+9j+9k^{2}-9k-9jk+3\equiv 3(\func{mod}9)$ which is impossible, since 
$c^{2}\equiv 3(\func{mod}9)$ has no solutions. \ Thus c is not divisible by
3, as desired. \ Furthermore, we can see that we cannot have $a\equiv 1$ and 
$b\equiv 2$ or $a\equiv 2$ and $b\equiv 1$ (mod 3).

\bigskip

For $x,y=0,1,2$ we color $x+y\omega +3O[\omega ]$\ as follows:

\bigskip 
\begin{tabular}{llll}
$x,y$ & 0 & 1 & 2 \\ 
0 & 0 & 1 & 2 \\ 
1 & 1 & 2 & 0 \\ 
2 & 2 & 0 & 1%
\end{tabular}

This coloring works, since if $z_{1}$ and $z_{2}$ have the same color, then
they differ by some $\frac{1}{c}(a+b\omega )$ where $a\equiv 1$ and $b\equiv
2$ or $a\equiv 2$ and $b\equiv 1(\func{mod}3)$.

The final part of the proof is exactly the same as in the $
\mathbb{Q}
\lbrack i]$ case.
\end{proof}

References:

[1]Woodall, D.R. (1973). \ Distances Realized by Sets Covering The Plane. \ 
\textit{Journal of Combinatorial Theory Series A} \textbf{14}: 187-200.

[2]Coulson, D. (2004). On the chromatic number of plane tilings. \textit{%
Journal of the Australian Mathematical Society} \textbf{77}: 191--196.

[3]Jensen, T.R. (1995). \ \textit{Graph Coloring Problems.} 150-152.

\end{document}
