The Nelson-Erdős-Hadwiger problem and embeddings of random graphs into geometric ones (Q2455210)

The problem in the title asks for the chromatic number \(\chi(d)\) of the infinite geometric graph \(E_d\) whose vertices are the points of Euclidian \(d\)-space and whose edges are pairs of points at unit distance apart. The inequality \(\chi(2)\geq 4\) follows from the existence of a finite subgraph of \(E_2\) of chromatic number 4. The author announces some results that, roughly speaking, give some insight into the frequency with which graphs with ``large'' chromatic number are found in \(E_d\). Let \(t(n, p)\) denote the largest integer \(k\), \(1\leq k\leq n\), such that a random graph \(G(n,p)\) is almost certain to contain an induced connected subgraph \(H\) with \(k\) vertices and chromatic number at least 4 that can be embedded in \(E_2\). Suppose, for example, that \(p= n^{-\alpha}\). If \(\alpha> 5/6\) and \(t(n,p)\) exists, then \(t(n,p)\gg\sqrt{n}\); but if \(\alpha> 1\), then \(t(n,p)\) does not exist. Results are also stated for the analogously defined function \(t(n,d,p)\) with the 4 in the earlier definition replaced by \((1.239\cdots+ o(1))^d\).