Topology and chromatic number of random \epsilon-distance graphs on spheres

arXiv2207.13892MaRDI QIDQ6406313FDOQ6406313

Authors: Francisco Martinez-Figueroa 

Publication date: 28 July 2022

Abstract: Given $0<alphaleqpi$, $epsilon>0$ and $n$, we define random graphs on the $d$-dimensional sphere by drawing $n$ i.i.d. uniform random points for the vertices, and edges $usimv$ whenever the geodesic distance between $u$ and $v$ is $epsilon$-close to $alpha$. This model generalizes distance graphs on spheres, and also random Borsuk graphs. Topological tools are known to give tight bounds for the chromatic number of Borsuk graphs. We now study the efficiency of one of these topological invariants, namely the connectivity of L'ovasz's neighborhood complex, to bound the chromatic number of this model of random graphs. We show that, in general, this bound performs badly, however, it still produces some useful bounds in dimensions $d=1$ and 2.

This page was built for publication: Topology and chromatic number of random $\epsilon$-distance graphs on spheres

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