Best-case variance 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], let Yn=χ(Gn,p)Y_n=\chi(G_{n,p}), and let σn2=Var(Yn)\sigma_n^2=\operatorname{Var}(Y_n). Define

w~n=n1/4log7/4n.\widetilde w_n=\frac{n^{1/4}}{\log^{7/4}n}.

Best-case variance conjecture. One has

0<lim infσnw~n<.0<\liminf\frac{\sigma_n}{\widetilde w_n}<\infty.

This is the proposed lower-order scale for the variance in the best case. The authors explicitly describe this conjecture as less certain than the worst-case statement and give no resolution.

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.