Logarithmic threshold conjecture for the chromatic number of random Borsuk graphs

Let G(n,α)G(n,\alpha) be the random Borsuk graph in dimension dd, and let χ(G(n,α))\chi(G(n,\alpha)) denote its chromatic number. Logarithmic threshold conjecture. For every d2d\geq 2 there exists a constant c=c(d)c=c(d) such that, for every fixed ε>0\varepsilon>0 and every sequence α=α(n)\alpha=\alpha(n),

limnP(χ(G(n,α))>d+1)={1if α>(1+ε)c(lnn/n)1/d,0if α<(1ε)c(lnn/n)1/d.\lim_{n\to\infty}\mathbb{P}\bigl(\chi(G(n,\alpha))>d+1\bigr)= \begin{cases} 1 & \text{if }\alpha>(1+\varepsilon)c(\ln n/n)^{1/d},\\ 0 & \text{if }\alpha<(1-\varepsilon)c(\ln n/n)^{1/d}. \end{cases}

The paper identifies the logarithmic regime as the relevant one for chromatic number at least d+2d+2 and suggests a connection with coverage of the sphere by random caps. Establishing the claimed threshold and its constant remains open.

Sources & referencesView supporting material

Primary source

Álvaro Acitores Montero, Matthias Irlbeck, Tobias Müller and Matěj Stehlík, “Thresholds for colouring the random Borsuk graph”, arXiv:2603.05467 (2026).

Additional references

2 papers in this index state this conjecture (2006–2026). The statement above is taken from the most recent of them; the others are arXiv:math/0611416.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.