Resolution of the Kohayakawa-Kreuter conjecture
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909291038900224 |
|---|---|
| author | Christoph, Micha Martinsson, Anders Steiner, Raphael Wigderson, Yuval |
| author_facet | Christoph, Micha Martinsson, Anders Steiner, Raphael Wigderson, Yuval |
| contents | A graph $G$ is said to be Ramsey for a tuple of graphs $(H_1,\dots,H_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theory and the theory of random graphs is to determine the threshold at which the binomial random graph $G_{n,p}$ becomes a.a.s. Ramsey for a fixed tuple $(H_1,\dots,H_r)$, and a famous conjecture of Kohayakawa and Kreuter predicts this threshold. Earlier work of Mousset-Nenadov-Samotij, Bowtell-Hancock-Hyde, and Kuperwasser-Samotij-Wigderson has reduced this probabilistic problem to a deterministic graph decomposition conjecture. In this paper, we resolve this deterministic problem, thus proving the Kohayakawa-Kreuter conjecture. Along the way, we prove a number of novel graph decomposition results which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_03045 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Resolution of the Kohayakawa-Kreuter conjecture Christoph, Micha Martinsson, Anders Steiner, Raphael Wigderson, Yuval Combinatorics 05C05, 05C20, 05C21, 05C42, 05C55, 05C70, 05C80, 05D10 A graph $G$ is said to be Ramsey for a tuple of graphs $(H_1,\dots,H_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theory and the theory of random graphs is to determine the threshold at which the binomial random graph $G_{n,p}$ becomes a.a.s. Ramsey for a fixed tuple $(H_1,\dots,H_r)$, and a famous conjecture of Kohayakawa and Kreuter predicts this threshold. Earlier work of Mousset-Nenadov-Samotij, Bowtell-Hancock-Hyde, and Kuperwasser-Samotij-Wigderson has reduced this probabilistic problem to a deterministic graph decomposition conjecture. In this paper, we resolve this deterministic problem, thus proving the Kohayakawa-Kreuter conjecture. Along the way, we prove a number of novel graph decomposition results which may be of independent interest. |
| title | Resolution of the Kohayakawa-Kreuter conjecture |
| topic | Combinatorics 05C05, 05C20, 05C21, 05C42, 05C55, 05C70, 05C80, 05D10 |
| url | https://arxiv.org/abs/2402.03045 |