On the concentration of the chromatic number of random graphs (Q6194237)

Summary: Shamir and Spencer proved in the 1980s that the chromatic number of the binomial random graph \(G_{n,p}\) is concentrated in an interval of length at most \(\omega\sqrt{n}\), and in the 1990s Alon showed that an interval of length \(\omega\sqrt{n}/\log n\) suffices for constant edge-probabilities \(p\in (0,1)\). We prove a similar logarithmic improvement of the Shamir-Spencer concentration results for the sparse case \(p=p(n) \to 0\), and uncover a surprising concentration ``jump'' of the chromatic number in the very dense case \(p=p(n) \to 1\).