The Turan number of blow-ups of trees

Abstract

A conjecture of Erdos 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 Erdos conjecture, including the related results of Furedi and Alon, Krivelevich and Sudakov. Our proof uses supersaturation and a random walk on an auxiliary graph.Crown Copyright (C) 2022 Published by Elsevier Inc.