Proof of the Kohayakawa--Kreuter conjecture for the majority of cases

Abstract

For graphs $G,H_1,\dots ,H_r$, write $G\to (H_1,\dots ,H_r)$ to denote the property that whenever we $r$-colour the edges of $G$, there is a monochromatic copy of $H_i$ in colour $i$ for some $i\in \{1,\dots ,r\}$. Mousset, Nenadov and Samotij proved an upper bound on the threshold function for the property that $G_{n,p}\to (H_1,\dots ,H_r)$, thereby resolving the $1$-statement of the Kohayakawa--Kreuter conjecture. We reduce the $0$-statement of the Kohayakawa--Kreuter conjecture to a natural deterministic colouring problem and resolve this problem for almost all cases, which in particular includes (but is not limited to) when $H_2$ is strictly $2$-balanced and either has density greater than $2$ or is not bipartite. In addition, we extend our reduction to hypergraphs, proving the colouring problem in almost all cases there as well.

38 pages, 5 figures, plus an appendix with 25 pages, 7 figures. arXiv admin note: text overlap with arXiv:2105.15151