On the Extremal Number of Subdivisions

David Conlon, Joonkyung Lee

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 C n2 - 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.

Original languageEnglish
Pages (from-to)9122-9145
Number of pages24
JournalInternational Mathematics Research Notices
Volume2021
Issue number12
DOIs
Publication statusPublished - 2021 Jun 1

Bibliographical note

Publisher Copyright:
© 2019 The Author(s).

All Science Journal Classification (ASJC) codes

  • General Mathematics

Fingerprint

Dive into the research topics of 'On the Extremal Number of Subdivisions'. Together they form a unique fingerprint.

Cite this