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