The chromatic number of random Borsuk graphs

DOI10.1002/RSA.20897MaRDI QIDQ5113958zbMATH OpenOpenAlexFDO

Authors Matthew Kahle, Francisco Martinez-Figueroa

Publication date 19 June 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.08488

zbMATH Keywords

random graphsBorsuk-Ulamtopological combinatorics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Abstract: We study a model of random graph where vertices are $n$ i.i.d. uniform random points on the unit sphere $S^d$ in $mathbb{R}^{d+1}$, and a pair of vertices is connected if the Euclidean distance between them is at least $2-epsilon$. We are interested in the chromatic number of this graph as $n$ tends to infinity. It is not too hard to see that if $epsilon>0$ is small and fixed, then the chromatic number is $d+2$ with high probability. We show that this holds even if $epsilono0$ slowly enough. We quantify the rate at which $epsilon$ can tend to zero and still have the same chromatic number. The proof depends on combining topological methods (namely the Lyusternik--Schnirelman--Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor --- if $epsilono0$ faster than this, we show that the graph is $(d+1)$-colorable with high probability.

Recommendations

• On the chromatic number of random subgraphs of a certain distance graph
• On the chromatic number of random geometric graphs
• On the chromatic number of random graphs
• The Nelson-Erdős-Hadwiger problem and a space realization of a random graph
• scientific article; zbMATH DE number 3989376

Cited in

(6)

• Borel chromatic numbers
• Realization of subgraphs of random graphs by graphs of diameters in Euclidean spaces
• Generalized Borsuk graphs
• A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems
• The distant-\(l\) chromatic number of random geometric graphs
• The chromatic and clique numbers of random scaled sector graphs

This page was built for publication: The chromatic number of random Borsuk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113958)