Follow

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.

Sign in to participate in the conversation
Mathstodon

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