Finite $\epsilon$-unit distance graphs

Abstract

In 2005, Exoo posed the following question. Fix $\epsilon$ with $0\leq\epsilon<1$. Let $G_\epsilon$ be the graph whose vertex set is the Euclidean plane, where two vertices are adjacent iff the Euclidean distance between them lies in the closed interval $[1-\epsilon,1+\epsilon]$. What is the chromatic number $\chi(G_\epsilon)$ of this graph? The case $\epsilon=0$ is precisely the classical ``chromatic number of the plane'' problem. In a 2018 preprint, de Grey shows that $\chi(G_0)\geq 5$; the proof relies heavily on machine computation. In 2016, Grytczuk et al. proved a weaker result with a human-comprehensible but nonconstructive proof: whenever $0<\epsilon<1$, we have that $\chi(G_\epsilon)\geq 5$. (This lower bound of $5$ was later improved by Currie and Eggleton to $6$.) The De Bruijn - Erd\H{o}s theorem (which relies on the axiom of choice) then guarantees the existence, for each $\epsilon$, of a finite subgraph $H_\epsilon$ of $G_\epsilon$ such that $\chi(H_\epsilon)\geq 5$. In this paper, we explicitly construct such finite graphs $H_\epsilon$. We find that the number of vertices needed to create such a graph is no more than $2\pi(15+14\epsilon^{-1})^2$. Our proof can be done by hand without the aid of a computer.

Keywords

• Chromatic number of the plane
• $\epsilon$-unit distance graph
• .

References

1. [1] J. D. Currie and R. B. Eggleton, Chromatic properties of the Euclidean plane, arXiv:1509.03667 11 Sep 2015.
2. [2] G. Exoo, $\epsilon$-unit distance graphs, Discrete Comput. Geom. 33(1) (2005) 117-123.
3. [3] K. J. Falconer, The realization of distances in measurable subsets covering Rn, J. Combin. Theory Ser. A 31(2) (1981) 184-189.
4. [4] A. D. de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28(1) (2018) 18–31.
5. [5] J. Grytczuk, K. Junosza-Szaniawski, J. Sokół, K. Wesek, Fractional and j-fold coloring of the plane, Discrete Comput. Geom. 55(3) (2016) 594-609.
6. [6] M. J. Nielsen, Approximating monochromatic triangles in a two-colored plane, Acta Math. Hungar. 74(4) (1997) 279-286.
7. [7] A. Soifer, The mathematical coloring book, Springer, New York (2009).