arXiv Analytics

Sign in

arXiv:1904.07219 [math.CO]AbstractReferencesReviewsResources

The Turán number of blow-ups of trees

Andrzej Grzesik, Oliver Janzer, Zoltán Lóránt Nagy

Published 2019-04-15Version 1

A conjecture of Erd\H{o}s from 1967 asserts that any graph on $n$ vertices which does not contain a fixed $r$-degenerate bipartite graph $F$ has at most $Cn^{2-1/r}$ edges, where $C$ is a constant depending only on $F$. We show that this bound holds for a large family of $r$-degenerate bipartite graphs, including all $r$-degenerate blow-ups of trees. Our results generalise many previously proven cases of the Erd\H{o}s conjecture, including the related results of F\"uredi and Alon, Krivelevich and Sudakov. Our proof uses supersaturation and a random walk on an auxiliary graph.

Related articles: Most relevant | Search more
arXiv:math/0009230 [math.CO] (Published 2000-09-26)
The conjecture cr(C_m\times C_n)=(m-2)n is true for all but finitely many n, for each m
arXiv:math/0610977 [math.CO] (Published 2006-10-31)
New results related to a conjecture of Manickam and Singhi
arXiv:1305.6482 [math.CO] (Published 2013-05-28, updated 2013-11-04)
A new result on the problem of Buratti, Horak and Rosa