Polynomial threshold conjecture for intermediate chromatic numbers of random Borsuk graphs

Less than 1 year old · traced to

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 d≥2d\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 3≤k≤d3\leq k\leq d, and every sequence α=α(n)\alpha=\alpha(n),

lim⁡n→∞P(χ(G(n,α))>k)={1if α>(1+ε)ckn−1/d,0if α<(1−ε)ckn−1/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.

References

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.