On the structure of distance graphs with large chromatic numbers (Q881128)

\textit{P. Frankl} and \textit{R. M. Wilson} [Combinatorica 1, 357--368 (1981; Zbl 0498.05048)] showed that the chromatic number of the unit distance (or equivalently, distance \(a\)) graph in \(R^n\) grows exponentially with \(n\), more precisely, it is at least \((1.207\dots +o(1))^n\). They showed that some subgraph already has the chromatic number that large: take for the the vertex set length \(n\) 0-1 vectors with exactly \(l\) of 1's, where \(l\) can be selected near \((1-\sqrt{2}/2)n\) and \(a\) is near \(\sqrt{l}\). The paper studies the question if other \(l\geq (1-\sqrt{2}/2)n \) values have corresponding \(a\) values realizing a graph with equally large chromatic number, and finds a positive answer. This yields very different subgraphs of the unit distance graph in \(R^n\) with the largest known chromatic number.