The typical structure of graphs without given excluded subgraphs

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)