Description
In this talk we prove the following theorem.
Theorem
Let $T_k$ denote a tree on $k$ vertices and $T_k[r]$ denotes its blow-up, where every vertex is replaced by an independent set of $r$ vertices. Then $ex(n, T_k[r])=Cn^{2-1/r}$ holds with a constant C depending on r and k.
To put this result into perspective, we present a short survey on recent (and not so recent) results concerning the maximum number of edges of simple graphs $G_n$ which do not contain a certain bipartite graph F; where we focus on the case when F is r-degenerate, i.e., every subgraph of F has a vertex of degree at most r. An old conjecture of Erdős asserts that the order of magnitude is at most$ n^{2-1/r}$. This has been proved for some classes of r-degenerate graphs by Zoltán Füredi, and later Alon, Krivelevich and Sudakov showed that a weaker upper bound of $O(n^{2-1/(4r)})$ holds, by applying the so-called Dependent Random Choice technique. We point out the connection between our new result and the previously known ones, and also prove a generalization.
Joint work with Andrzej Grzesik (Jagellonian University)