On the chromatic number and equilateral dimension of ${\mathbb{R}}^n$ with the tropical norm

Abstract

We study the tropical chromatic number of ${\mathbb{R}}^n$, ${\chi }_{\mathrm{tr}}({\mathbb{R}}^n)$, the minimal number of colors needed to color ${\mathbb{R}}^n$, so that no two points at tropical unit distance have the same color. It is the tropical analogue of the well-known Hadwiger-Nelson problem in ${\mathbb{R}}^2$. We have $\left(\genfrac{}{}{0ex}{}{n+1}{\lfloor (n+1)/2\rfloor }\right)\le {\chi }_{\mathrm{tr}}({\mathbb{R}}^n)\le 2^n$ for every $n$, where the lower bound comes from Sperner's antichain bound on a maximal equilateral set, as shown by Swanepoel. It is conjectured that ${\chi }_{\mathrm{tr}}({\mathbb{R}}^n)=2^n$, which is known to be the case for the measurable chromatic number. By constructing a graph with 62 vertices and 577 edges we demonstrate that ${\chi }_{\mathrm{tr}}({\mathbb{R}}^3)=8$. We also construct a graph in ${\mathbb{Z}}^4$ with 37 vertices and 386 edges that is 11-colorable but not 10-colorable, which is above Sperner's lower bound of 10.

24 pages, 3 figures