Realization of subgraphs of random graphs by graphs of diameters in Euclidean spaces
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)].
- On the realization of subgraphs of a random graph by diameter graphs in Euclidean spaces
- The Nelson-Erdős-Hadwiger problem and a space realization of a random graph
- The chromatic number of random Borsuk graphs
- On the realization of random graphs as distance graphs in spaces of fixed dimension
- The Nelson-Erdős-Hadwiger problem and embeddings of random graphs into geometric ones
- Coloring distance graphs and graphs of diameters
- Counterexamples to Borsuk's conjecture on spheres of small radius
- Drei Sätze über die n-dimensionale euklidische Sphäre
- Excursions into combinatorial geometry
- New bounds for the distance Ramsey number
- On a bound in Borsuk's problem
- On the chromatic numbers of spheres in \(\mathbb R^n\)
- On the realization of random graphs as distance graphs in spaces of fixed dimension
- Random graphs.
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
This page was built for publication: Realization of subgraphs of random graphs by graphs of diameters in Euclidean spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471395)
