Turan numbers of bipartite subdivisions

Abstract

Given a graph $H$, the Turán number $ex(n,H)$ is the largest number of edges in an $H$-free graph on $n$ vertices. We make progress on a recent conjecture of Conlon, Janzer, and Lee on the Turán numbers of bipartite graphs, which in turn yields further progress on a conjecture of Erdős and Simonovits. Let $s,t,k\ge 2$ be integers. Let $K_{s,t}^k$ denote the graph obtained from the complete bipartite graph $K_{s,t}$ by replacing each edge $uv$ in it with a path of length $k$ between $u$ and $v$ such that the $st$ replacing paths are internally disjoint. It follows from a general theorem of Bukh and Conlon that $ex(n,K_{s,t}^k)=\Omega (n^{1+\frac{1}{k}-\frac{1}{sk}})$. Conlon, Janzer, and Lee recently conjectured that for any integers $s,t,k\ge 2$, $ex(n,K_{s,t}^k)=O(n^{1+\frac{1}{k}-\frac{1}{sk}})$. Among many other things, they settled the $k=2$ case of their conjecture. As the main result of this paper, we prove their conjecture for $k=3,4$. Our main results also yield infinitely many new so-called Turán exponents: rationals $r\in (1,2)$ for which there exists a bipartite graph $H$ with $ex(n,H)=\Theta (n^r)$, adding to the lists recently obtained by Jiang, Ma, Yepremyan, by Kang, Kim, Liu, and by Conlon, Janzer, Lee. Our method builds on an extension of the Conlon-Janzer-Lee method. We also note that the extended method also gives a weaker version of the Conlon-Janzer-Lee conjecture for all $k\ge 2$.

arXiv comment18 pages, revised Lemma 3.10, replacing it with Lemma 3.10 and Lemma 3.11. Revised the corresponding part in the proof of Lemma 3.12 that uses Lemma 3.10

References in corpus (1)

• Graphs with few paths of prescribed length between any two vertices

Cited by in corpus (1)

• Negligible obstructions and Turán exponents