Bipartite Turán number of trees

Abstract

We start a systematic investigation concerning bipartite Turán number for trees. For a graph $F$ and integers $1\le a\le b$ we define: $(i)$\quad $e{x}_b(a,b,F)$ is the largest number of edges that an $F$-free bipartite graph can have with part sizes $a$ and $b$. We write $e{x}_b(n,F)$ for $e{x}_b(n,n,F)$. $(ii)$\quad $e{x}_{b,c}(a,b,F)$ is the largest number of edges that an $F$-free connected, bipartite graph can have with part sizes $a$ and $b$. We write $e{x}_{b,c}(n,F)$ for $exb,c(n,n,F)$. Both definitions are similar for a family $\mathcal{F}$ of graphs. We prove general lower bounds depending on the maximum degree of $F$, as well as on the cardinalities of the two vertex classes of $F$. We derive upper and lower bounds for $e{x}_b(n,F)$ in terms of $ex(2n,F)$ and $ex(n,F)$, the corresponding classical (not bipartite) Turán numbers. We solve both problems for various classes of graphs, including all trees up to six vertices for any $n$, for double stars $D_{s,t}$ if $a\ge f(s,t)$, for some families of spiders, and more. We use these results to supply an answer to a problem raised by L. T. Yuan and X. D. Zhang [{\it Graphs and Combinatorics}, 2017] concerning $e{x}_b(n,{\mathcal{T}}_{k,\ell })$, where ${\mathcal{T}}_{k,\ell }$ is the family of all trees with vertex classes of respective cardinalities $k$ and $\ell$. The asymptotic worst-case ratios between Turán-type functions are also inverstigated.