Asymptotic normality conjecture for the chromatic number of random graphs

About 5 years old · traced to

Let Gn,pG_{n,p} be the binomial random graph with constant p∈(0,1−1/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,

Yn−f(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.

References

Primary source

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

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.