Non-concentration of the chromatic number of a random graph, arxiv.org/abs/1906.11808, via gilkalai.wordpress.com/2019/06

Shamir & Spencer '87 (doi.org/10.1007/BF02579208) and Alon & Krivelevich '97 (doi.org/10.1007/10.1007/BF0121) proved that random graphs $$G(n,p)$$ with $$p=n^{1/2-\epsilon}$$ have almost surely only two possible chromatic numbers. But now Annika Heckel has shown that dense random graphs have a significantly wider spread in colors.

· · Web · · ·

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!