Algebraic formulation of Hadwiger-Nelson problem

This is a part of Polymath16 - for the main page, see Hadwiger-Nelson problem.

Given a unit distance graph [math]\displaystyle{ G }[/math], the edges of the graph are formed by a set of vectors [math]\displaystyle{ V }[/math] of unit length. Often a single vector is used many times in the same graph for different edges. The vectors generate an infinite abelian group [math]\displaystyle{ \mathcal{G} }[/math] under addition. The Cayley graph [math]\displaystyle{ \Gamma(\mathcal{G},S) }[/math] is a unit distance graph that will contain [math]\displaystyle{ G }[/math] as a subgraph. A colouring of the Cayley graph reduces to a colouring of [math]\displaystyle{ G }[/math], and is an efficient way to set an upper bound on its chromatic number.

In two dimensions it is useful to identify the vectors with complex numbers. For example the Eisenstein integers [math]\displaystyle{ \mathbb{Z}[\omega] }[/math] are generated by an equilateral triangle or hexagon with unit length sides. These are complex numbers of the form [math]\displaystyle{ z = a + b\omega, a,b \in \mathbb{Z} }[/math] where [math]\displaystyle{ \omega = \frac{-1 + i\sqrt{3}}{2} }[/math] is a cube root of one. A 3-colouring is given by a mapping to the group [math]\displaystyle{ \mathbb{Z}_3 }[/math] defined by [math]\displaystyle{ c(z) = x \in \mathbb{Z}, x \equiv a + b \bmod{3} }[/math]. To verify that this is valid it is sufficient to check that no element of [math]\displaystyle{ \mathbb{Z}[\omega] }[/math] which is of unit modulus is sent to the identity (zero) in [math]\displaystyle{ \mathbb{Z}_3 }[/math].