The seminars in Discrete Mathematics are aimed at researchers, employees, and students.
This week's seminar is given by Raphael Steiner, ETH Zürich
Title: Resolution of the Kohayakawa-Kreuter conjecture.
Abstract: A graph G is said to be Ramsey for a tuple of graphs (H_1,... ,H_r) if every r-coloring of the edges of G contains a monochromatic copy of H_i in color i for some i. A fundamental question at the intersection of Ramsey theory and the theory of random graphs is to determine the threshold at which the binomial random graph G_{n,p} becomes a.a.s. Ramsey for a fixed tuple (H_1,... ,H_r), and a famous conjecture of Kohayakawa and Kreuter predicts this threshold.
Earlier work of Mousset--Nenadov--Samotij, Bowtell--Hancock--Hyde, and Kuperwasser--Samotij--Wigderson has reduced this probabilistic problem to a deterministic graph decomposition conjecture. In this talk, I will discuss the history of this problem and sketch our recent resolution of this deterministic problem, which completes the proof of the Kohayakawa--Kreuter conjecture.
