On the Kohayakawa-Kreuter conjecture

Abstract

Let us say that a graph $G$ is Ramsey for a tuple $(H_1,\dots ,H_r)$ of graphs if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i\in [r]$. A famous conjecture of Kohayakawa and Kreuter, extending seminal work of Rödl and Ruciński, predicts the threshold at which the binomial random graph $G_{n,p}$ becomes Ramsey for $(H_1,\dots ,H_r)$ asymptotically almost surely. In this paper, we resolve the Kohayakawa-Kreuter conjecture for almost all tuples of graphs. Moreover, we reduce its validity to the truth of a certain deterministic statement, which is a clear necessary condition for the conjecture to hold. All of our results actually hold in greater generality, when one replaces the graphs $H_1,\dots ,H_r$ by finite families ${\mathcal{H}}_1,\dots ,{\mathcal{H}}_r$. Additionally, we pose a natural (deterministic) graph-partitioning conjecture, which we believe to be of independent interest, and whose resolution would imply the Kohayakawa-Kreuter conjecture.

20 pages, plus short appendix