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
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE171425
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.05467

Browse the full library · About the Tower of Babel