Thresholds for colouring the random Borsuk graph

Abstract

We consider the chromatic number of the random Borsuk graph. The random Borsuk graph is obtained by sampling $n$ points i.i.d. uniformly at random on the $d$-dimensional sphere $S^d$, and joining a pair of points by an edge whenever their geodesic distance is $>\ddot{I}€-\hat{I}\pm$ where the parameter $\hat{I}\pm =\hat{I}\pm (n)$ may depend on $n$. Kahle and Martinez-Figueroa have shown that the switch from being $(d+1)$-colourable to needing $\ge d+2$ colours occurs in the regime where the average degree is of logarithmic order. We show that for each $2\le k\le d$, the switch from being $k$-colourable to needing $>k$ colours occurs in the regime when the average degree is constant. What is more, we show that for $k=2$ there is a sharp threshold of the form $\hat{I}\pm (n)=c\cdot n^{-1/d}$, where the constant $c$ can be expressed in terms of the critical intensity for continuum AB percolation on ${\mathbb{R}}^d$. For $k=3,\dots ,d+1$ we show that there is a sharp threshold for "almost all $n$".