MATH Seminar

Title: Random Ramsey Theorems
Colloquium: Combinatorics
Speaker: Rajko Nenadov of ETH Zurich
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2019-02-11 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: We say that a graph G is Ramsey for a graph H if in every colouring of the edges of G with red and blue we can find a monochromatic copy of H, that is a copy with all edges having the same colour. Perhaps surprising at first, Ramsey's theorem states that for every graph H there is a graph G which is Ramsey for H. This existence statement raises many further questions: how many vertices or edges such G needs to have, can it share some structural properties with H such as girth or the clique number, is there a choice for G which always gives an induced monochromatic copy of H and, if yes, then how many vertices such G needs to have? Many of these questions can be fully resolved using random graphs and quite often the random graphs give the best known quantitative bounds. Even though the first major results on Ramsey properties of random graphs date back to the beginning of the '90s and the work of Rödl and Ruci?ski, many questions and conjectures remain open. In this talk we will review some of the recent progress on these questions and discuss current challenges.