Resolution of the Kohayakawa-Kreuter conjecture
| Autor: | Christoph, Micha, Martinsson, Anders, Steiner, Raphael, Wigderson, Yuval |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 28 pages, updated according to the referee's comments |
| Databáze: | arXiv |
| Externí odkaz: |
|