The typical structure of H-free graphs

16 June 2015

How many $H$-free graphs are there on $n$ vertices? What is the typical structure of such a graph $G$? And how do these answers change if we restrict the number of edges of $G$? In this talk I will describe some recent progress on these basic and classical questions, focusing on the cases $H=K_{r+1}$ and $H=C_{2k}$. The key tools are the hypergraph container method, the Janson inequalities, and some new "balanced" supersaturation results. The techniques are quite general, and can be used to study similar questions about objects such sum-free sets, antichains and metric spaces.

I will mention joint work with a number of different coauthors, including Jozsi Balogh, Wojciech Samotij, David Saxton, Lutz Warnke and Mauricio Collares Neto. 

  • Combinatorial Theory Seminar