Colouring random graphs: Tame colourings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914957174505472 |
|---|---|
| author | Heckel, Annika Panagiotou, Konstantinos |
| author_facet | Heckel, Annika Panagiotou, Konstantinos |
| contents | Given a graph G, a colouring is an assignment of colours to the vertices of G so that no two adjacent vertices are coloured the same. If all colour classes have size at most t, then we call the colouring t-bounded, and the t-bounded chromatic number of G, denoted by $χ_t(G)$, is the minimum number of colours in such a colouring. Every colouring of G is then $α(G)$-bounded, where $α(G)$ denotes the size of a largest independent set.
We study colourings of the random graph G(n, 1/2) and of the corresponding uniform random graph G(n,m) with $m=\left \lfloor \frac 12 {n \choose 2} \right \rfloor$. We show that $χ_t(G(n,m))$ is maximally concentrated on at most two explicit values for $t = α(G(n,m))-2$. This behaviour stands in stark contrast to that of the normal chromatic number, which was recently shown not to be concentrated on any sequence of intervals of length $n^{1/2-o(1)}$. Moreover, when $t = α(G_{n, 1/2})-1$ and if the expected number of independent sets of size $t$ is not too small, we determine an explicit interval of length $n^{0.99}$ that contains $χ_t(G_{n,1/2})$ with high probability. Both results have profound consequences: the former is at the core of the intriguing Zigzag Conjecture on the distribution of $χ(G_{n, 1/2})$ and justifies one of its main hypotheses, while the latter is an important ingredient in the proof of a non-concentration result for $χ(G_{n,1/2})$ that is conjectured to be optimal.
These two results are consequences of a more general statement. We consider a class of colourings that we call tame, and provide tight bounds for the probability of existence of such colourings via a delicate second moment argument. We then apply those bounds to the two aforementioned cases. As a further consequence of our main result, we prove two-point concentration of the equitable chromatic number of G(n,m). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_07253 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Colouring random graphs: Tame colourings Heckel, Annika Panagiotou, Konstantinos Combinatorics 05C15, 05C80 Given a graph G, a colouring is an assignment of colours to the vertices of G so that no two adjacent vertices are coloured the same. If all colour classes have size at most t, then we call the colouring t-bounded, and the t-bounded chromatic number of G, denoted by $χ_t(G)$, is the minimum number of colours in such a colouring. Every colouring of G is then $α(G)$-bounded, where $α(G)$ denotes the size of a largest independent set. We study colourings of the random graph G(n, 1/2) and of the corresponding uniform random graph G(n,m) with $m=\left \lfloor \frac 12 {n \choose 2} \right \rfloor$. We show that $χ_t(G(n,m))$ is maximally concentrated on at most two explicit values for $t = α(G(n,m))-2$. This behaviour stands in stark contrast to that of the normal chromatic number, which was recently shown not to be concentrated on any sequence of intervals of length $n^{1/2-o(1)}$. Moreover, when $t = α(G_{n, 1/2})-1$ and if the expected number of independent sets of size $t$ is not too small, we determine an explicit interval of length $n^{0.99}$ that contains $χ_t(G_{n,1/2})$ with high probability. Both results have profound consequences: the former is at the core of the intriguing Zigzag Conjecture on the distribution of $χ(G_{n, 1/2})$ and justifies one of its main hypotheses, while the latter is an important ingredient in the proof of a non-concentration result for $χ(G_{n,1/2})$ that is conjectured to be optimal. These two results are consequences of a more general statement. We consider a class of colourings that we call tame, and provide tight bounds for the probability of existence of such colourings via a delicate second moment argument. We then apply those bounds to the two aforementioned cases. As a further consequence of our main result, we prove two-point concentration of the equitable chromatic number of G(n,m). |
| title | Colouring random graphs: Tame colourings |
| topic | Combinatorics 05C15, 05C80 |
| url | https://arxiv.org/abs/2306.07253 |