Polynomial threshold conjecture for intermediate chromatic numbers 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. Polynomial threshold conjecture. For each d2d\geq 2, there exist constants c3=c3(d),,cd=cd(d)c_3=c_3(d),\dots,c_d=c_d(d) such that

c2<c3<<cd,c_2<c_3<\dots<c_d,

where c2c_2 is the constant supplied by the paper's theorem, and, for every fixed ε>0\varepsilon>0, every 3kd3\leq k\leq d, and every sequence α=α(n)\alpha=\alpha(n),

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

The claim gives the expected sharp thresholds for the intermediate chromatic-number transitions, refining the paper's almost-all-nn result. The constants and the asserted sharpness are not proved.

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).

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.