Progress on the Kohayakawa-Kreuter conjecture

Abstract: Let $H_1, ..., H_r$ be graphs. We write $G(n,p) \to (H_1, ..., H_r)$ to denote the property that whenever we colour the edges of $G(n,p)$ with colours from the set $[r] := \{1, ..., r\}$ there exists some $1 \le i \le r$ and a copy of $H_i$ in $G(n,p)$ monochromatic in colour $i$.

There has been much interest in determining the asymptotic threshold function for this property. Rödl and Ruciński (1995) determined the threshold function for the general symmetric case; that is, when $H_1 = ... = H_r$. A conjecture of Kohayakawa and Kreuter (1997), if true, would effectively resolve the asymmetric problem. Recently, the $1$-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij (2021+). The $0$-statement however has only been proved for pairs of cycles, pairs of cliques and pairs of a clique and a cycle.

In this talk we introduce a reduction of the $0$-statement of Kohayakawa and Kreuter's conjecture to a certain deterministic, natural subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs (satisfying properties one can assume when proving the $0$-statement).

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.