Conlon, David and Lee, Joonkyung (2019) On the extremal number of subdivisions. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170921338
![]() |
PDF
- Submitted Version
See Usage Policy. 226kB |
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: |
| ||||||||
ORCID: |
| ||||||||
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: |
| ||||||||
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