Realization of subgraphs of random graphs by graphs of diameters in Euclidean spaces (Q471395)

A graph of diameters in \(\mathbb{R}^{d}\) is a graph whose vertex set \(V\) is a set of points in \(\mathbb{R}^{d}\) and whose edge set consists of those pairs of points for which \(d(x,y)=\max_{x,y \in V}d(x,y)\). In other words, two vertices are adjacent if and only if the distance between them is the largest distance in the set of distances. Clearly the smallest number of sets of smaller diameter into which \(V\) can be partitioned is equal to the chromatic number of \(G\). The former quantity is the so-called Borsuk number of the set, related to the (now known to be false) Borsuk conjecture on the minimum number of sets of diameter strictly less than one into which a set of diameter one can be partitioned. The paper under review studies the quantity \(u_{d}(n,p)\) which is \[ \begin{multlined}\max\{k: \mathbb{P}_{n,p}\big( \exists H=(W,F)\subset G: | W|=k,\,H=G\mid_W,\\ H {\text{ is a graph of distances in }}\mathbb{R}^{d}, \chi(H)\geq d+1\big)>1/2\}.\end{multlined} \] In words, this is, for \(d\leq 3\), the maximum \(k\) such that, in an Erdős-Rényi random graph \(G(n,p)\), there is an induced subgraph on \(k\) vertices which is a graph of diameters in \(\mathbb{R}^{d}\) with the maximum possible chromatic number. We use here the truth of the Borsuk conjecture in dimensions \(\leq 3\). The paper states (but does not prove) various results on values on the typical (i.e. the \textbf{whp} values) of \(u_{d}(n,p)\) as \(p=p(n)\) varies, for various values of \(d\) -- especially 2 and 3. For example, \(u_{2}(n,p)\) is typically about \(2\log_{b}(np)\) where \(b=1/(1-p)\). Some less sharp \textbf{whp} bounds on \(U_{d}(n,p)\) for more general \(d\) are also stated. Proofs are in another paper by \textit{A. A. Kokotkin} and \textit{A. M. Raigorodskii} [Mosk. Fiz.-Tekh. Inst., Trudy Inst. 4, 19--28 (2012)].