The chromatic number of random Borsuk graphs

DOI10.1002/RSA.20897zbMATH Open1442.05210arXiv1901.08488OpenAlexW2988839058MaRDI QIDQ5113958FDOQ5113958

Francisco Martinez-Figueroa, Matthew Kahle

Publication date: 19 June 2020

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

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.

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)

Cited In (3)

• Borel chromatic numbers
• Generalized Borsuk graphs
• A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems

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)