Micha Christoph, ETH Zurich

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. We show that this deterministic graph decomposition conjecture is true. 

See: https://sites.google.com/view/rutgersdmseminar