Resolution of the Kohayakawa–Kreuter conjecture

Abstract A graph is said to be Ramsey for a tuple of graphs if every ‐coloring of the edges of contains a monochromatic copy of in color , for some . 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 becomes asymptotically almost surely Ramsey for a fixed tuple , 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.