Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2021 | Submitted
Journal Article Open

More on the extremal number of subdivisions


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)).

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.

Attached Files

Submitted - 1903.10631.pdf


Files (312.4 kB)
Name Size Download all
312.4 kB Preview Download

Additional details

August 20, 2023
October 18, 2023