Department of Mathematics,
University of California San Diego
****************************
Math 269 - Combinatorics
Wojtek Samotij
U. of Illinois and Tel Aviv U.
Counting graphs without a fixed complete bipartite subgraph
Abstract:
A graph is called $H$-free if it contains no copy of $H$. Denote by $f_n(H)$ the number of (labeled) $H$-free graphs on $n$ vertices. Since every subgraph of an $H$-free graph is also $H$-free, it immediately follows that $f_n(H) \geq 2^{\mathrm{ex}(n,H)}$. Erd{\H o}s conjectured that, provided that $H$ contains a cycle, this trivial lower bound is asymptotically tight, i.e., \[ f_n(H) = 2^{(1+o(1))\mathrm{ex}(n,H)}. \] The conjecture was resolved in the affirmative for graphs with chromatic number at least $3$ by Erd{\H o}s, Frankl, and R{\"o}dl (1986)
Host: Jozsef Balogh
May 20, 2010
2:00 PM
AP&M 6402
****************************