##### 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

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