Best-case variance 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], 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/4log⁡7/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.

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.