Bipartite Turán number of trees

Yair Caro, Balázs Patkós, Zsolt Tuza · 2025

Read Bipartite Turán number of trees by Yair Caro, Balázs Patkós, Zsolt Tuza (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09052.txt.

Introduction

Yair Caro, Balázs Patkós, and Zsolt Tuza open in 2025 a planned study of bipartite Turán numbers for trees. The classic question asks how many edges a graph can hold with no copy of a banned shape. The bipartite form splits vertices into two sides of set sizes.

Two forms are defined, one free and one requiring the graph to stay connected. Broad lower bounds rest on the top degree of the banned tree and its side sizes. Upper and lower bounds tie the new numbers to classic ones. Exact answers come for small trees, double stars, and spider forms, plus a past open problem.

Catalog record

CREATORYair Caro, Balázs Patkós, Zsolt Tuza
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09052

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Bipartite Turán number of trees Yair Caro, Balázs Patkós, Zsolt Tuza Abstract . We start a systematic investigation concerning bipartite Turán number for trees. For a graph F F and integers 1 ≤ a ≤ b 1\leq a\leq b we define: ( i ) (i) ⁡ ex b ​ ( a , b , F ) \mathop{}\!\mathrm{ex}_{\mathrm{b}}(a,b,F) is the largest number of edges that an F F -free bipartite graph can have with part sizes a a and b b . We write ⁡ ex b ​ ( n , F ) \mathop{}\!\mathrm{ex}_{\mathrm{b}}(n,F) for ⁡ ex b ​ ( n , n , F ) \mathop{}\!\mathrm{ex}_{\mathrm{b}}(n,n,F) . ( i ​ i ) (ii) ⁡ ex b , c ​ ( a , b , F ) \mathop{}\!\mathrm{ex}_{\mathrm{b,c}}(a,b,F) is the largest number of edges that an F F -free connected, bipartite graph can have with part sizes a a and b b . We write ⁡ ex b , c ​ ( n , F ) \mathop{}\!\mathrm{ex}_{\mathrm{b,c}}(n,F) for ⁡ ex b , c ​ ( n , n , F ) \mathop{}\!\mathrm{ex}_{\mathrm{b,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 F , as well as on the cardinalities of the two vertex classes of F F . We derive upper and lower bounds for ⁡ ex b ​ ( n , F ) \mathop{}\!\mathrm{ex}_{\mathrm{b}}(n,F) in terms of ⁡ ex ⁡ ( 2 ​ n , F ) \mathop{}\!\mathrm{ex}(2n,F) and ⁡ ex ⁡ ( n , F ) \mathop{}\!\mathrm{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 n , for double stars D s , t D_{s,t} if a ≥ f ⁡ ( s , t ) a\geq 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 [ Graphs and Combinatorics , 2017] concerning ⁡ ex b ​ ( n , 𝒯 k , ℓ ) \mathop{}\!\mathrm{ex}_{\mathrm{b}}(n,{\mathcal{T}}_{k,\ell}) , where 𝒯 k , ℓ {\mathcal{T}}_{k,\ell} is the family of all trees with vertex classes of respective cardinalities k k and ℓ \ell . The asymptotic worst-case ratios between Turán-type functions are also inverstigated. Keywords: Turán number, Bipartite Turán number, Extremal combinatorics. Mathematics Subject Classification 2020: 05C05, 05C35. 1. Introduction and results In this paper we initiate a systematic study of Turán numbers of trees in the bipartite setting. Namely, we raise the analogous problem with restriction to the bipartite universe, i.e., where the extremal graphs are subgraphs of the complete bipartite graphs K_{a,b} , mostly of K_{n,n} . Moreover, we also consider the situation where the extremal graph is required to be connected. Part of our motivation is to complement the recent research concerning connected Turán numbers of trees without the bipartite restriction started in [ 3 ] and continued in [ 11 ] . Another part of the motivation comes from successfully extending and answering extremal results explicitly raised in [ 15 , Question 1.5] concerning {\mathcal{T}}_{k,l} , the family of all trees T(k,l) with vertex classes of respective cardinalities k and l . Sporadic results concerning both problems, in the bipartite setting or the non-bipartite connected version already appeared; we refer to [ 5 ] , [ 8 ] , [ 13 ] , [ 14 ] , [ 15 ] , [ 16 ] . Later we shall say more about these papers, as well as on the progress we made concerning some questions raised in [ 15 ] . Before proceeding with the main results of this paper, we introduce a necessary definition and notation which will be used in the sequel. Definition. Let F be a given “forbidden” graph. • \mathop{}\!\mathrm{ex}(n,F) is the largest number of edges that an n -vertex graph can have without any subgraph isomorphic to F . (Such graphs are called F -free ). • \mathop{}\!\mathrm{ex}_{c}(n,F) is the largest number of edges that an n -vertex connected F -free graph can have. • \mathop{}\!\mathrm{ex}_{\mathrm{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 \mathop{}\!\mathrm{ex}_{\mathrm{b}}(n,F) for \mathop{}\!\mathrm{ex}_{\mathrm{b}}(n,n,F) . • \mathop{}\!\mathrm{ex}_{\mathrm{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 \mathop{}\!\mathrm{ex}_{\mathrm{b,c}}(n,F) for \mathop{}\!\mathrm{ex}_{\mathrm{b,c}}(n,n,F) . All parameters can be defined analogously when we forbid copies of all graphs of a family {\mathcal{F}} . Then we use the notation \mathop{}\!\mathrm{ex}(n,{\mathcal{F}}) , \mathop{}\!\mathrm{ex}_{\mathrm{c}}(n,{\mathcal{F}}) , \mathop{}\!\mathrm{ex}_{\mathrm{b}}(n,{\mathcal{F}}) , \mathop{}\!\mathrm{ex}_{\mathrm{b,c}}(n,{\mathcal{F}}) . Notation . We use the standard notation \delta=\delta(G) , \Delta=\Delta(G) , and e(G) , respectively, for the minimum degree, maximum degree, and the number of edges of a given graph G . The vertex-disjoint union of two graphs G and H is denoted by G\cup H . For a graph H and a positive integer k , kH denotes the pairwise vertex-disjoint union of k copies of H . We denote by S_{k} the star with k leaves; P_{k} and C_{k} denote the path and the cycle on k vertices, respectively. The complete bipartite graph with parts of size a and b is denoted by K_{a,b} . We write D_{a,b} to denote the double star on a+b+2 vertices such that the two non-leaf vertices have degree a+1 and b+1 . The spider S_{a_{1},a_{2},\dots,a_{j}} with j\geq 3 is the graph obtained from j paths with a_{1},a_{2},\dots,a_{j} edges by identifying one endpoint of all paths. So S_{a_{1},a_{2},\dots,a_{j}} has 1+\sum_{i=1}^{j}a_{i} vertices and maximum degree j . The only vertex of degree at least 3 is the center of the spider, and the maximal paths starting at the center are its legs . If a spider has h legs of length \ell , and other legs of length a_{1},\dots,a_{j} , then we use the notation S_{a_{1},\dots,a_{j},h*\ell} . Finally, P_{r,s,t} denotes the tree on r+s+t+3 vertices u,u_{1},\dots,u_{r} , v,v_{1},\dots,v_{s} , w,w_{1}\dots,w_{t} with uvw being a path and zz_{i} forming an edge for all z\in\{u,v,w\} and all feasible values of i ; hence, P_{r,s,t} is a caterpillar whose spine is the path P_{3} . The following list covers the references relevant to this paper, including the sporadic publications of recent years concerning the connected Turán numbers in the general case, and Turán numbers in the bipartite setting. For a general survey on Turán numbers see [ 7 ] , though in some sections it is a bit outdated. The exact determination of Turán numbers for paths, also including the connected version, was done long ago in [ 8 ] and [ 13 ] . Results concerning cycles in bipartite graphs were considered several times; see [ 1 ] , [ 9 ] , [ 10 ] , [ 12 ] , [ 14 ] . Turán numbers of linear forests in bipartite graphs were considered in [ 4 ] , [ 5 ] , [ 16 ] . Connected Turán number for trees is systematically studied in [ 3 ] , [ 11 ] ]. The famous Erdős–Sós conjecture on trees appeared first

Read the complete text