More on the extremal number of subdivisions

Abstract

Given a graph $H$, the extremal number $\mathrm{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 $K_{s,t}$, we show that $\mathrm{ex}(n,K_{s,t}^{\prime })=O(n^{3/2-\frac{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\ge 1$, we show that $\mathrm{ex}(n,L)=\hat{I}˜(n^{1+\frac{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\in (1,2)$ is realisable in the sense that $\mathrm{ex}(n,H)=\hat{I}˜(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\ge 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 $\hat{I}´>0$ such that $\mathrm{ex}(n,H^{k-1})=O(n^{1+1/k-\hat{I}´})$, 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 $\mathrm{ex}(n,H)=o(n^{2-1/r})$.

21 pages