More on the Extremal Number of Subdivisions
2021
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}^\prime $$
for the subdivision of the bipartite graph Ks,t, we show that $${\rm{ex}}(n,K_{s,t}^\prime ) = O({n^{3/2 - {1 \over {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 $${\rm{ex}}(n,L) = \Theta ({n^{1 + {s \over + 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) = Θ(nr) 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 Hk 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, Hk−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 C4 as a subgraph satisfies ex(n, H) = o(n2−1/r).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
21
References
18
Citations
NaN
KQI