Erdős Problems

Tags Prizes

OPEN

Let $G_n$ be the unit distance graph in $\mathbb{R}^n$, with two vertices joined by an edge if and only if the distance between them is $1$.

Estimate the chromatic number $\chi(G_n)$. Does it grow exponentially in $n$? Does \[\lim_{n\to \infty}\chi(G_n)^{1/n}\] exist?

#704: [Er81]

graph theory, geometry, chromatic number

A generalisation of the Hadwiger-Nelson problem (which addresses $n=2$). Frankl and Wilson [FrWi81] proved exponential growth: \[\chi(G_n) \geq (1+o(1))1.2^n.\] The trivial colouring (by tiling with cubes) gives \[\chi(G_n) \leq (2+\sqrt{n})^n.\] Larman and Rogers [LaRo72] improved this to \[\chi(G_n) \leq (3+o(1))^n,\] and conjecture the truth may be $(2^{3/2}+o(1))^n$. Prosanov [Pr20] has given an alternative proof of this upper bound.