Non-concentration of the chromatic number of a random graph,, via

Shamir & Spencer '87 ( and Alon & Krivelevich '97 ( 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

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