Journal article
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 Cn2−1/r edges contains a copy of H. This result is tight up to the constant when H contains a copy of Kr,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 C4-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 Cn3/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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 327.8KB, Terms of use)
-
- Publisher copy:
- 10.1093/imrn/rnz088
Authors
- Publisher:
- Oxford University Press
- Journal:
- International Mathematics Research Notices More from this journal
- Volume:
- 2021
- Issue:
- 12
- Pages:
- 9122–9145
- Publication date:
- 2019-06-03
- Acceptance date:
- 2019-04-09
- DOI:
- EISSN:
-
1687-0247
- ISSN:
-
1687-0247
- Language:
-
English
- Keywords:
- Pubs id:
-
pubs:987738
- UUID:
-
uuid:e22193b2-05e5-4b70-a2b5-1717fc803203
- Local pid:
-
pubs:987738
- Source identifiers:
-
987738
- Deposit date:
-
2019-04-09
Terms of use
- Copyright holder:
- Conlon and Lee
- Copyright date:
- 2019
- Rights statement:
- © The Author(s) 2019. Published by Oxford University Press. All rights reserved. This article is published and distributed under the terms of the Oxford University Press, Standard Journals Publication Model.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Oxford University Press at: https://doi.org/10.1093/imrn/rnz088
- Licence:
- Other
If you are the owner of this record, you can report an update to it here: Report update to this record