Asymptotic normality conjecture for the chromatic number of random graphs

From papers

Let Gn,pG_{n,p} be the binomial random graph with constant p(0,11/e2]p\in(0,1-1/e^2], and let Yn=χ(Gn,p)Y_n=\chi(G_{n,p}). Call nn good when it is outside the paper's designated bad range, namely when μα(n)(n)\mu_{\alpha(n)}(n) is not between n1/2δn^{1/2-\delta} and n1/2+δn^{1/2+\delta} for the fixed constant δ>0\delta>0. Let λ(n)\lambda(n) be the exponent from the Zigzag Conjecture.

Asymptotic normality conjecture. There are functions f(n)f(n) and g(n)g(n) such that, at least for good nn,

Ynf(n)g(n)dN(0,1),\frac{Y_n-f(n)}{g(n)}\overset{\mathrm d}{\longrightarrow}N(0,1),

where N(0,1)N(0,1) is standard Gaussian, and

g(n)=nλ(n)+o(1).g(n)=n^{\lambda(n)+o(1)}.

The conjecture refines the proposed fluctuation scale by asserting a Gaussian limit, but leaves the transition points called bad unresolved.

Progress summary

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

Sources & referencesView supporting material

Primary source

Annika Heckel and Oliver Riordan, “How does the chromatic number of a random graph vary?”, arXiv:2103.14014 (2023).

Solutions 0

No solutions have been posted yet.