CaltechAUTHORS
  A Caltech Library Service

On the extremal number of subdivisions

Conlon, David and Lee, Joonkyung (2019) On the extremal number of subdivisions. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170921338

[img] PDF - Submitted Version
See Usage Policy.

220Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190819-170921338

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1807.05008arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
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.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
European Research Council (ERC)676632
Gordon and Betty Moore FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20190819-170921338
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190819-170921338
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98029
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 21:46
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page