On the extremal number of subdivisions
One of the cornerstones of extremal graph theory is a result of Füredi, later reproved and given due prominence by Alon, Krivelevich and Sudakov, saying that if H is a bipartite graph with maximum degree r on one side, then there is a constant C such that every graph with n vertices and Cn^(2 - (1/r)) edges contains a copy of H. This result is tight up to the constant when H contains a copy of K_(r,s) with s sufficiently large in terms of r. We conjecture that this is essentially the only situation in which Füredi's result can be tight and prove this conjecture for r = 2. More precisely, we show that if H is a C_(4)-free bipartite graph with maximum degree 2 on one side, then there are positive constants C and δ such that every graph with n vertices and Cn^(3/2) - δ) edges contains a copy of H. This answers a question of Erdős from 1988. The proof relies on a novel variant of the dependent random choice technique which may be of independent interest.
Additional InformationConlon research supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. Lee research supported by ERC Starting Grant 676632. This paper was partially written while the first author was visiting the California Institute of Technology as a Moore Distinguished Scholar and he is extremely grateful for their kind support.
Submitted - 1807.05008.pdf