A Caltech Library Service

More on the extremal number of subdivisions

Conlon, David and Janzer, Oliver and Lee, Joonkyung (2019) More on the extremal number of subdivisions. . (Unpublished)

[img] PDF - 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(n^(1 + 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_4 as a subgraph satisfies ex(n, H) = o(n^(2 - 1/r).

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:Conlon research supported by ERC Starting Grant RanDM 676632. Lee research supported by ERC Consolidator Grant PEPCo 724903.
Funding AgencyGrant Number
European Research Council (ERC)676632
European Research Council (ERC)724903
Record Number:CaltechAUTHORS:20190819-170943053
Persistent URL:
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:03 Oct 2019 21:37

Repository Staff Only: item control page