Resolution of the Kohayakawa–Kreuter conjecture
OPEN ACCESS
Loading...
Author / Producer
Date
2025-01
Publication Type
Journal Article
ETH Bibliography
yes
OPEN ACCESS
Data
Rights / License
Abstract
A graph G is said to be Ramsey for a tuple of grahps (H₁,…,Hᵣ) if every r-coloring of the edges of G contains a monochromatic copy of Hᵢ 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ₙ,ₚ becomes asymptotically almost surely Ramsey for a fixed tuple (H₁,…,Hᵣ), 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 that may be of independent interest.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
130 (1)
Pages / Article No.
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
Notes
Funding
216071 - Graph coloring motivated by Hadwiger's conjecture (SNF)