A Caltech Library Service

More on the extremal number of subdivisions

Conlon, David and Janzer, Oliver and Lee, Joonkyung (2021) More on the extremal number of subdivisions. Combinatorica, 41 (4). pp. 465-494. ISSN 0209-9683. doi:10.1007/s00493-020-4202-1.

[img] PDF (25 Apr 2020) - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Given a graph H, the extremal number ex(n, H) is the largest number of edges in an H-free graph on n vertices. We make progress on a number of conjectures about the extremal number of bipartite graphs. First, writing K′_(s,t) for the subdivision of the bipartite graph K_(s,t), we show that ex(n,K′_(s,t)) = O(n^(3/2)−1/2s)). This proves a conjecture of Kang, Kim and Liu and is tight up to the implied constant for t sufficiently large in terms of s. Second, for any integers s,k ≥ 1, we show that ex(n,L) = Θ(n^(1+s/sk+1)) for a particular graph L depending on s and k, answering another question of Kang, Kim and Liu. This result touches upon an old conjecture of Erdős and Simonovits, which asserts that every rational number r ∈ (1, 2) is realisable in the sense that ex(n, H) = Θ(n^r) for some appropriate graph H, giving infinitely many new realisable exponents and implying that 1 + 1/k is a limit point of realisable exponents for all k ≥ 1. Writing H^k for the k-subdivision of a graph H, this result also implies that for any bipartite graph H and any k, there exists δ > 0 such that ex(n, H^(k−1)) = O(^(n1+1/k−δ)), partially resolving a question of Conlon and Lee. Third, extending a recent result of Conlon and Lee, we show that any bipartite graph H with maximum degree r on one side which does not contain C₄ as a subgraph satisfies ex(n, H) = o(n^(2−1/r)).

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access Paper
Conlon, David0000-0001-5899-1829
Additional Information:© 2021 János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg. Received 16 April 2019; Revised 24 April 2020; Published 26 August 2021. We would like to thank the anonymous referees for their careful reviews. Research supported by ERC Starting Grant RanDM 676632. Research supported by ERC Consolidator Grant PEPCo 724903.
Funding AgencyGrant Number
European Research Council (ERC)676632
European Research Council (ERC)724903
Issue or Number:4
Classification Code:Mathematics Subject Classification (2010): 05C35
Record Number:CaltechAUTHORS:20190819-170943053
Persistent URL:
Official Citation:Conlon, D., Lee, J. & Janzer, O. More on the Extremal Number of Subdivisions. Combinatorica 41, 465–494 (2021).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98035
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 23:02
Last Modified:29 Oct 2021 20:50

Repository Staff Only: item control page