MATH Seminar

Title: Induced Subgraphs of Ramsey Graphs
Seminar: Combinatorics
Speaker: Matthew Kwan of Stanford University
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2018-11-12 at 4:00PM
Venue: MSC E408
Download Flyer
Abstract: An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. It is simple to show that various kinds of random graphs are likely to be $O(1)$-Ramsey graphs, but there are no known explicit examples of C-Ramsey graphs for any constant C. We discuss two new additions to the ongoing line of research showing that in fact all Ramsey graphs must obey certain “richness' properties characteristic of random graphs. First, resolving a conjecture of Narayanan, Sahasrabudhe and Tomon, motivated by an old problem of Erd?s and McKay, we prove that every C-Ramsey graph has $\Omega(n^2)$ induced subgraphs with different numbers of edges. Second, resolving a conjecture of Erd?s, Faudree and Sós, we prove that every C-Ramsey graph has $\Omega(n^{5/2})$ induced subgraphs, no two of which have the same numbers of vertices and edges. This is joint work with Benny Sudakov.