printable pdf
比利时vs摩洛哥足彩 ,
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

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