On the Clique and the Chromatic Numbers of High-Dimensional Distance Graphs
Andrei Mikhailovich Raigorodskii, Oleg Igorevich Rubanov · Hindustan Book Agency · 2009
The classical Nelson — Erdős — Hadwiger problem, which was proposed in the late 1940’s (see [1], [2]), consists in finding or at least estimating the so-called chromatic number χ(ℝ d ) of the Euclidean space ℝ d , where the value χ(ℝ d ) is defined as the minimum number of colours needed to paint all the points in ℝ d in such a way that any two points at the distance 1 apart receive different colours. Of course, in this definition, distance 1 may be replaced by an arbitrary fixed distance a > 0, due to the homogeneity of the Euclidean space. In other words, the quantity χ(ℝ d ) is the usual chromatic number of a graph G a d =( G d , E a d ) $$\mathfrak{G}_a^d = \left( {{\mathfrak{G}^d},\mathfrak{E}_a^d} \right)$$ , provided V d = ℝ d , E a d ={(a,y)∈ V d × V d :|a−y|=a}, a>0 $${\mathfrak{V}^d} = {\mathbb{R}^d},\mathfrak{E}_a^d = \{ (a,y) \in {\mathfrak{V}^d} \times {\mathfrak{V}^d}:|a - y| = a\} ,\,a > 0$$ .