##### Department of Mathematics,

University of California San Diego

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

### Math 269 - Combinatorics

## Paul Horn

#### Harvard

## Density Jumps in Multigraphs

##### Abstract:

A corollary of the Erd\H{o}s-Stone theorem is that, for any $0 \leq \alpha < 1$, graphs with density greater than $\alpha$ contain an (arbitrarily) large subgraph of density at least $\alpha+c$ for some fixed $c = c(\alpha)$, so long as the graph itself is sufficiently large. This phenomenon is known as a jump at $\alpha$. Erd\H{o}s conjectured that similar statements should hold for hypergraphs, and multigraphs where each edge can appear with multiplicity at most $q$, for $q \geq 2$ fixed. Brown, Erd\H{o}s, and Simonovits answered this conjecture in the affirmative for $q=2$, that is for multigraphs where each edge can appear at most twice. R\"{o}dl answered the question in

Host: Fan Chung Graham

### November 6, 2012

### 3:00 PM

### AP&M 7321

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