The Tur��n number of blow-ups of trees

Autor: Grzesik, Andrzej, Janzer, Oliver, Nagy, Zolt��n L��r��nt
Rok vydání: 2019
Předmět:
DOI: 10.48550/arxiv.1904.07219
Popis: A conjecture of Erd��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��s conjecture, including the related results of F��redi and Alon, Krivelevich and Sudakov. Our proof uses supersaturation and a random walk on an auxiliary graph.
Databáze: OpenAIRE