Thresholds for colouring the random Borsuk graph
Álvaro Acitores Montero, Matthias Irlbeck, Tobias Müller, Matěj Stehlík · 2026
Read Thresholds for colouring the random Borsuk graph by Álvaro Acitores Montero, Matthias Irlbeck, Tobias Müller, Matěj Stehlík (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05467.txt.
Introduction
Acitores Montero and colleagues study colouring of the random Borsuk graph, formed by sampling points uniformly on a sphere and joining distant pairs. Kahle and Martinez-Figueroa had shown the switch from (d+1)-colourable to needing d+2 colours occurs at logarithmic average degree. The authors show that for each k between 2 and d, the switch from k-colourable to needing more colours occurs at constant average degree. For k equals 2 the threshold is sharp, and for higher k it is sharp for almost all n.
Catalog record
| CREATOR | Álvaro Acitores Montero, Matthias Irlbeck, Tobias Müller, Matěj Stehlík |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 171425 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.05467