Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 20, 2019 | Submitted
Report Open

On the extremal number of subdivisions

Abstract

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 Information

Conlon 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.

Attached Files

Submitted - 1807.05008.pdf

Files

1807.05008.pdf
Files (226.1 kB)
Name Size Download all
md5:56061b6bca16c5174feaad4128290701
226.1 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 18, 2023