Abstract
The Typical Structure of Graphs without Given Excluded Subgraphs
József Balogh
University of Illinois at Urbana-Champaign
Let \( \mathcal{L} \) be a finite family of graphs. We describe the typical structure of \( \mathcal{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}) = \min_{L \in \mathcal{L}} \chi(L) - 1.
\]
We shall prove that the structure of almost all \( \mathcal{L} \)-free graphs are very similar to the Tur\'an graph \( T_{n,p} \), where ``similarity'' is measured in terms of graph-theoretical parameters of \( \mathcal{L} \).
Some more recent developments, including extensions for induced containment, bipartite graphs, and hypergraphs, will be discussed as well.
Partially joint work with: Alon, Bollob\'as, Butterfield, Morris, Mubayi, Samotij, and Simonovits.
\[
p = p(\mathcal{L}) = \min_{L \in \mathcal{L}} \chi(L) - 1.
\]
We shall prove that the structure of almost all \( \mathcal{L} \)-free graphs are very similar to the Tur\'an graph \( T_{n,p} \), where ``similarity'' is measured in terms of graph-theoretical parameters of \( \mathcal{L} \).
Some more recent developments, including extensions for induced containment, bipartite graphs, and hypergraphs, will be discussed as well.
Partially joint work with: Alon, Bollob\'as, Butterfield, Morris, Mubayi, Samotij, and Simonovits.
No video available