On the chromatic numbers of rational spaces (Q1646347)

The authors consider coloring problems similar to the well-known problem of determining the chromatic number of the plane. Given a rational number \(a\) and a positive integer \(n\), a rational \(a\)-distance graph in \(\mathbb{Q}^n\) is any graph whose vertices can be represented by points in \(\mathbb{Q}^n\) so that whenever two vertices are adjacent, the distance between the corresponding points in \(\mathbb{Q}^n\) is exactly \(a\). One can then define the chromatic number \(\chi(\mathbb{Q}^n)\) of the space \(\mathbb{Q}^n\) as the maximum value of \(\chi(G)\) over all graphs \(G\) such that \(G\) is a rational \(a\)-distance graph in \(\mathbb{Q}^n\) for some \(a \in \mathbb{Q}\). (In fact, it suffices to consider just \(a=1\).) It was observed by \textit{E. I. Ponomarenko} and \textit{A. M. Raigorodskii} [``On the chromatic number of the space \(\mathbb{Q}^n\)'', Trudy Mosk. Fiz. Tekhn. Inst 4, No. 1, 127--130 (2012)] that often a graph which admits such a representation in \(\mathbb{Q}^n\) in fact admits coordinates which lie in some affine subspace of smaller dimension, albeit with non-rational coordinates inside subspace. Accordingly, the affine dimension of a graph \(G\), written \(\mathrm{affdim}(G)\), is defined to be the smallest \(n\) such that: the vertices of \(G\) can be assigned coordinates in an \(n\)-dimensional affine subspace of \(\mathbb{Q}^m\) for some \(m\) so that each pair of adjacent vertices has distance exactly \(1\) between the corresponding points. Analogous with the earlier definition, one then defines \(\chi_{\mathrm{aff}}(\mathbb{Q}^n)\) to be the maximum of \(\chi(G)\) over all rational \(1\)-distance graphs \(G\) with \(\mathrm{affdim}(G) \leq 1\). The author seeks techniques to give an upper bound on \(\chi_{\mathrm{aff}}(\mathbb{Q}^n)\), by relating this chromatic number to a similar type of chromatic number. Say that a graph \(G\) whose vertices have coordinates in \(\mathbb{Q}^n\) is a \(\sqrt{Q}\)-graph if \(|x-y|^2\) is rational for all pairs of vertices \(x\) and \(y\), and say that \(G\) is a \(\sqrt{Q}\)-unit distance graph if additionally we have \(|x-y| = 1\) for every pair of adjacent vertices \(x,y\). The author then defines \(\chi_{\sqrt{Q}}(\mathbb{R}^n)\) as the maximum of \(\chi(G)\) over all \(\sqrt{Q}\)-unit distance graphs in \(\mathbb{R}^n\). The author proves the following main results concerning this parameter: {\parindent=8mm \begin{itemize}\item[(i)] \(\chi_{\mathrm{aff}}(\mathbb{Q}^n) = \chi_{\sqrt{Q}}(\mathbb{R}^n)\) for each positive integer \(n\), \item[(ii)] If \(G\) is a connected \(\sqrt{Q}\)-unit distance graph in \(\mathbb{R}^2\) containing a subgraph isomorphic to \(K_3\), then \(\chi(G) = 3\), \item[(iii)] If \(G\) is a connected \(\sqrt{Q}\)-unit distance graph in \(\mathbb{R}^3\) containing a subgraph isomorphic to \(K_4\), then \(\chi(G) = 4\), \item[(iv)] For every positive integer \(n\), \(\chi_{\sqrt{Q}}(\mathbb{R}^2) = \max\{ \chi(\mathbb{Q} \times \sqrt{q}\mathbb{Q}), q \in \mathbb{N}\}\). \end{itemize}} In light of the second and third theorems, which give upper bounds for what heuristically seem to be the ``worst-case graphs'' in their respective classes, the author poses the question of whether indeed \(\chi_{\mathrm{aff}}(\mathbb{Q}^2) = 3\) and \(\chi_{\mathrm{aff}}(\mathbb{Q}^3) = 4\). The author also asks whether analogs of these theorems hold in higher dimensions.