The ACO Seminar (2024–2025)

A basic result of probabilistic combinatorics, originally due to Erdős and Rényi, is the determination of the threshold at which the random graph $G_{n,p}$ contains a triangle with high probability. But one can also ask more refined versions of this question, where we ask not just for one triangle but for many triangles which interact in complicated ways. For example, what is the threshold at which we can no longer partition $G_{n,p}$ into two triangle-free subgraphs? In this talk, I will discuss the proof of the Kohayakawa–Kreuter conjecture, which gives a general answer to all such questions. Rather surprisingly, a key step of the proof is a purely deterministic graph decomposition statement, closely related to classical results such as Nash-Williams' tree decomposition theorem, whose proof uses techniques from combinatorial optimization and structural graph theory. Based on joint works with Micha Christoph, Eden Kuperwasser, Anders Martinsson, Wojciech Samotij, and Raphael Steiner.