The unit distance graph on has edges between those pairs of points at Euclidean distance
. The chromatic number of this graph lies between
(by exhibiting a small subgraph on
vertices with chromatic number
) and
(by an explicit colouring based on a hexagonal tiling of the plane). Aubrey de Grey has just posted a construction of a unit distance graph with chromatic number
, raising the lower bound on
by
. This MathOverflow post is a good jumping off point into the discussion online.
I was explaining this problem to a colleague and they asked whether this graph was connected (it is) and whether that was still true if we restricted to rational coordinates. It turns out this was addressed by Kiran B.Chilakamarri in 1988, and the answer is the rational unit distance graph is connected from dimension onwards.
To see that is not connected, consider a general unit vector
where
is coprime to
. Then
.
Claim. is divisible by
at most once.
Proof. Squares mod are either
,
or
. If
is divisible by
then one of the
is odd, hence squares to
mod
. But then
cannot be divisible by
, which is a contradiction.
So the entries of in their reduced form do not contain any
‘s in their denominator, and so the same must hold for all sums of unit vectors. Hence we can’t express, say,
as a sum of unit vectors, and
is not connected to
.
Connectedness in dimension (hence also later) uses Lagrange’s theorem on the sums of four squares. We’ll show that
can be expressed as a sum of
unit vectors. By Lagrange’s theorem, write
. Then
hence
is a sum of unit vectors.