This week's seminar in Discrete Mathematics is given by Robert Hancock, University of Oxford.
Title: A resolution of the Kohayakawa Kreuter conjecture for almost all pairs of graphs
Abstract: We study asymmetric Ramsey properties of the random graph G(n,p). For r ≥ 2 and a graph H, Rödl and Rucinski (1993-5) provided the asymptotic threshold for G(n,p) to have the following property: whenever we r-colour the edges of G(n,p) there exists a monochromatic copy of H as a subgraph. In 1997, Kohayakawa and Kreuter conjectured an asymmetric version of this result, where one replaces H with a set of graphs H_1,...,H_r and we seek the threshold for when every r-colouring contains a monochromatic copy of H_i in colour i for some i ∈ {1,...,r}.
The 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij in 2020. We extend upon the many partial results for the 0-statement, by resolving it for almost all cases. We reduce the remaining cases to a deterministic colouring problem.
Our methods also extend to the hypergraph setting.
Joint work with Candida Bowtell (University of Warwick) and Joseph Hyde (University of Victoria).
