Distance graphs with large chromatic numbers and small clique numbers (Q1761033): Difference between revisions

An \(n\)-dimensional distance graph is a graph whose vertex set is a subset of \({\mathbb R}^n\), vertices being adjacent if their Euclidean distance equals \(a\), where \(a>0\) is an arbitrary fixed number. It is known that there exist distance graphs with large chromatic number and small clique number. More precisely, for every \(k\geq 3\) there exist a constant \(\zeta_k > 0\), a function \(\delta_k = \delta_k(n)\) such that \(\delta_k = o(1)\) as \(n\rightarrow \infty\), and a sequence of \(n\)-dimensional distance graphs \(G_n\), such that \(\chi(G) \geq (\zeta_k + \delta_k(n))^n\) and \(\omega(G_n) < k\) hold. In the present paper, all previously known bounds on \(\zeta_k\) are substantially refined. In particular, the new results yield non-trivial bounds for \(k=3\) and \(k=4\) which failed to be obtained earlier. The main tool is a considerable strengthening of the related probabilistic method. Sketches of the proofs are provided.