19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Density jumps in multigraphs

Presented by Dr. Paul HORN
Type: Oral presentation
Track: General session


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 the negative for hypergraphs, and later R\"{o}dl and Sidorenko answered the question in the negative for multigraphs where $q\geq 4$. No jumps or non-jumps were known for $q=3$. In this talk we investigate some related questions. In particular, we exhibit the first known jumps for multigraphs where $q=3$. We also exhibit a new proof of the theorem of R\"{o}dl and Sidorenko that there are non-jumps for multigraphs with $q \geq 4$. This proof uses tools from spectral graph theory, and allows us to exhibit new non-jumps. This is based on joint work with V. R\"{o}dl and S. LaFleur.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors