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

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