On the concentration of the chromatic number of random graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914803391397888 |
|---|---|
| author | Surya, Erlang Warnke, Lutz |
| author_facet | Surya, Erlang Warnke, Lutz |
| contents | 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 ω\sqrt{n}, and in the 1990s Alon showed that an interval of length ω\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_00906 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the concentration of the chromatic number of random graphs Surya, Erlang Warnke, Lutz Combinatorics Discrete Mathematics Probability 05C80, 05C15, 60C05 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 ω\sqrt{n}, and in the 1990s Alon showed that an interval of length ω\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. |
| title | On the concentration of the chromatic number of random graphs |
| topic | Combinatorics Discrete Mathematics Probability 05C80, 05C15, 60C05 |
| url | https://arxiv.org/abs/2201.00906 |