Claremont Center for the Mathematical Sciences

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 Erdos-Frankl-Rodl 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 is very similar to the Turan 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.