Abstract

The Typical Structure of Graphs without Given Excluded Subgraphs

József Balogh
University of Illinois at Urbana-Champaign
Mathematics

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(\mathcal{L})=\underset{L\in \mathcal{L}}{min}\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.