Printable PDF
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

****************************