CaltechAUTHORS
  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 . ISSN 0209-9683. doi:10.1007/s00493-020-4202-1. (In Press) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170943053

[img] PDF - Submitted Version
See Usage Policy.

299kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190819-170943053

Abstract

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
https://doi.org/10.1007/s00493-020-4202-1DOIArticle
https://rdcu.be/cxLgjPublisherFree ReadCube access
https://arxiv.org/abs/1903.10631arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:© 2021 Bolyai Society, Springer-Verlag. 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.
Funders:
Funding AgencyGrant Number
European Research Council (ERC)676632
European Research Council (ERC)724903
Classification Code:Mathematics Subject Classification (2010): 05C35
DOI:10.1007/s00493-020-4202-1
Record Number:CaltechAUTHORS:20190819-170943053
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190819-170943053
Official Citation:Conlon, D., Lee, J. & Janzer, O. More on the Extremal Number of Subdivisions. Combinatorica (2021). https://doi.org/10.1007/s00493-020-4202-1
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98035
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 23:02
Last Modified:14 Sep 2021 18:17

Repository Staff Only: item control page