The Typical Structure of Graphs without Given Excluded Subgraphs

József Balogh
University of Illinois at Urbana-Champaign

Let $\cal L$ be a finite family of graphs. We describe the typical structure of $\cal L$-free graphs, improving our earlier results on the Erd\H{o}s-Frankl-R\"odl theorem, by proving our conjecture from our earlier paper. Let $$p=p({\cal L})=\min_{L\in {\cal L}}\chi(L)-1.$$ We shall prove that the structure of almost all $\LL$-free graphs are very similar to the Tur\'an graph $T_{n,p}$, where ``similarity'' is measured in terms of graph theoretical parameters of $\LL$.
Some more recent developments, including extensions for induced containment, bipartite graphs, hypergraphs, will be discussed as well.

Partially joint work with: Alon, Bollobas, Butterfield, Morris, Mubayi, Samotij, and Simonovits.

Presentation (PDF File)

Back to Workshop I: Probabilistic Techniques and Applications