Ramsey Graphs

An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. As one of the first applications of the probabilistic method, Erdos proved that 2-Ramsey graphs exist, but our understanding of Ramsey graphs is still extremely limited. For example, there are still no known explicit constructions of C-Ramsey graphs, for any constant C. Benny and his coauthors have had a large impact in an ongoing line of research towards understanding the structure of Ramsey graphs and in particular showing that they must satisfy certain ”richness” properties characteristic of random graphs. I’ll talk about some of Benny’s earlier work on this subject, some of my recent joint work with Benny, and some new directions joint with Lisa Sauermann.