CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170943053

[img] PDF - Submitted Version
See Usage Policy.

292Kb

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(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
http://arxiv.org/abs/1903.10631arXivDiscussion Paper
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
European Research Council (ERC)676632
European Research Council (ERC)724903
Record Number:CaltechAUTHORS:20190819-170943053
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190819-170943053
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:03 Oct 2019 21:37

Repository Staff Only: item control page