Resolving the Kohayakawa--Kreuter Conjecture for Families

Abstract

A graph $G$ is $(a,b)$-sparse if every nonempty subgraph $H$ satisfies $e(H)\le av(H)-b$. We are interested in the conditions under which an $(a,b)$-sparse graph can be partitioned $E(G)=E(G_1)\cup E(G_2)$ such that for $i\in \{1,2\}$ we have that $G_i$ is $(a_i,b_i)$-sparse. Kuperwasser, Samotij, and Wigderson conjectured that a $(m,0)$-sparse graph can be partitioned into a $(1,1)$-sparse graph and a $(m,2m-1)$-sparse graph. We prove the conjecture in full. The Kohayakawa--Kreuter Conjecture for Families claims that $n^{-1/m_2}$ is the threshold function for the random graph being Ramsey a.a.s. for graph families ${\mathcal{H}}_1,\dots {\mathcal{H}}_r$. Kuperwasser, Samotij, and Wigderson motivated their conjecture by proving that it is sufficient to establish the Kohayakawa--Kreuter Conjecture for Families.