On the concentration of the chromatic number of random graphs (Q6194237)
From MaRDI portal
scientific article; zbMATH DE number 7820338
Language | Label | Description | Also known as |
---|---|---|---|
English | On the concentration of the chromatic number of random graphs |
scientific article; zbMATH DE number 7820338 |
Statements
On the concentration of the chromatic number of random graphs (English)
0 references
19 March 2024
0 references
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\).
0 references