11/10/2009 - 12:15pm

11/10/2009 - 1:10pm

Speaker:

Jozsef Balogh (University of Illinois at Urbana-Champaign)

Abstract:

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.

Where:

Millikan 208 (Pomona College)