Bounds on Linear Turán Number for Trees

Rajat Adak, Pragya Verma · 2026

Read Bounds on Linear Turán Number for Trees by Rajat Adak, Pragya Verma (2026) 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-2601-17325.txt.

Introduction

Rajat Adak and Pragya Verma set bounds in hypergraph theory. A hypergraph lets one edge hold many vertices at once. It is linear when each pair of vertices shares at most one edge. The Turán number asks how many edges such a graph can hold while it avoids a banned family. The authors study that count when the host is linear.

They focus on trees as the banned shapes. Sharp bounds sort sparse from dense in a clean way. Such results guide network and code design, where hypergraphs model group links. They also test proof tools in extremal combinatorics. Each new bound trims the space of graphs that builders must check.

Catalog record

CREATORRajat Adak, Pragya Verma
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-17325

Browse the full library · About the Tower of Babel

Full text

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

Bounds on Linear Turán Number for Trees Rajat Adak, Pragya Verma Abstract A hypergraph H H is said to be linear if every pair of vertices lies in at most one hyperedge. Given a family ℱ \mathcal{F} of r r -uniform hypergraphs, an r r -uniform hypergraph H H is ℱ \mathcal{F} -free if it contains no member of ℱ \mathcal{F} as a subhypergraph. The linear Turán number e ​ x r lin ​ ( n , ℱ ) ex_{r}^{\mathrm{lin}}(n,\mathcal{F}) denotes the maximum number of hyperedges in an ℱ \mathcal{F} -free linear r r -uniform hypergraph on n n vertices. Gyárfás, Ruszinkó, and Sárközy [ Linear Turán numbers of acyclic triple systems , European J. Combin. (2022)] initiated the study of bounds on the linear Turán number for acyclic 3 3 -uniform linear hypergraphs. In this paper, we extend the study of linear Turán number for acyclic systems to higher uniformity. We first give a construction for any linear r r -uniform tree with k k edges that yields the lower bound e ​ x r lin ​ ( n , T k r ) ≥ n ⁡ ( k − 1 ) / r , ex_{r}^{\mathrm{lin}}(n,T_{k}^{r})\geq{n(k-1)}/{r}, under mild divisibility and existence assumptions. Next, we study hypertrees with four edges. We prove the exact bound e ​ x r lin ​ ( n , B 4 r ) ≤ ( r + 1 ) ​ n / r ex_{r}^{\mathrm{lin}}(n,B_{4}^{r})\leq{(r+1)n}/{r} and characterize the extremal hypergraph class, where B 4 r B_{4}^{r} is formed from S 3 r S_{3}^{r} by appending a hyperedge incident to a degree-one vertex. We also prove the bound e ​ x r lin ​ ( n , E 4 r ) ≤ ( 2 ​ r − 1 ) ​ n / r ex_{r}^{\mathrm{lin}}(n,E_{4}^{r})\leq{(2r-1)n}/{r} for the crown E 4 r E_{4}^{r} . Finally, we give a construction showing e ​ x r lin ​ ( n , P 4 r ) ≥ ( r + 1 ) ​ n / r ex_{r}^{\mathrm{lin}}(n,P_{4}^{r})\geq{(r+1)n}/{r} under suitable assumptions and conclude with a conjecture on sharp upper bound for P 4 r P_{4}^{r} . 1 Introduction Extremal graph theory is largely concerned with Turán-type problems, which ask for the maximum number of edges in a graph or hypergraph that avoids a prescribed forbidden substructure. In this work, we focus on a more recent line of research, namely the study of linear Turán numbers. The Turán problem for hypergraphs has been investigated extensively; see, for instance, the surveys [ 9 , 8 , 13 ] and the book [ 10 ] . The study of Turán numbers has a long history, beginning with the classical result of Turán (1941) for cliques. Theorem 1.1 (Turán [ 18 ] ) For n\geq r\geq 1 , ex(n,K_{r+1})\leq|E(T(n,r)| , where T(n,r) denotes the Turán graph on n vertices and r parts. Equality holds if and only if G\cong T(n,r) . In the hypergraph setting, Turán type problems become significantly more complex due to the added structural conditions and various notions of the missing substructure (e.g., Berge, Loose, Linear). The extension of the Turán problem to hypergraphs has been studied under several of these notions. Turán-type results for loose paths were obtained by Mubayi and Verstraëte [ 15 ] , for linear paths by Füredi, Jiang, and Seiver [ 7 ] , and for Berge paths by Győri, Katona, and Lemons [ 12 ] . In this paper, we focus exclusively on the linear framework. 1.1 Preliminaries In a hypergraph H=(V(H),E(H)) , V(H) denotes the set of vertices, and E(H) is the set of hyperedges in H . For v\in V(H) , d(v) denotes the degree of the vertex in H . that is, the number of hyperedges incident on v . For v\in V(H) , E_{v}(H) denotes the set of hyperedges in E(H) containing the vertex v . H is called r -uniform is each e\in E(H) contains r vertices. A hypergraph is linear when any two distinct hyperedges intersect in at most one vertex. 1.2 Linear Turán Number For a family \mathcal{F} of linear r -uniform hypergraphs, the linear Turán number ex_{r}^{lin}(n,\mathcal{F}) captures the largest number of hyperedges an n -vertex linear r -uniform hypergraph may have while avoiding all members of \mathcal{F} . A key construction in this framework is the expansion of a graph. Given a graph G , its expansion G^{r} is obtained by inflating each graph edge into an r -element hyperedge using r-2 fresh vertices (kept disjoint across edges). The result is automatically a linear r -uniform hypergraph. The phrase linear Turán number was introduced by Collier-Cartaino, Graber, and Jiang [ 3 ] , who established foundational bounds for linear cycles. Yet the phenomenon predates the terminology: the celebrated work of Ruzsa and Szemerédi [ 16 ] can be stated as n^{2-\frac{c}{\sqrt{\log{n}}}}\leq ex^{\mathrm{lin}}_{3}(n,C^{3}_{3})=o(n^{2}), where c>0 and C_{3}^{3} denotes the 3 -uniform expansion of the C_{3} ( 3 -edge cycle). The systematic study of acyclic structures in this context was initiated by Gyárfás, Ruszinkó, and Sárközy [ 11 ] , who investigated acyclic triple systems and obtained several bounds for 3 -uniform linear expansions. Zhang and Wang [ 21 ] extended this direction to the 4 -uniform setting and proved corresponding bounds for a variety of forbidden configurations. The current picture continues to rapidly develop. Zhou and Yuan [ 22 ] derived general r -uniform bounds, including for P_{k}^{r} , showing ex^{\mathrm{lin}}_{r}(n,P_{k}^{r})\leq\frac{(2r-3)kn}{2} for r\geq 3,k\geq 4 . Complementing this line, Khormali and Palmer [ 14 ] and Zhang et al. [ 20 ] investigated star-forests, establishing bounds for sufficiently large n . For linear hypertrees on four hyperedges, the setting already becomes rich. Expansions of trees yield several distinct configurations. For k=2 , the only possibility is P_{2}^{r} (where P_{k} denotes a path on k edges). It is easy to check that ex_{r}^{\mathrm{lin}}(n,P_{2}^{r})=\lfloor\frac{n}{r}\rfloor . For k=3 , we obtain precisely P_{3}^{r} and S_{3}^{r} (where S_{k} denotes a star on k edges). In [ 21 ] , it was shown that ex_{r}^{\mathrm{lin}}(n,P_{3}^{r})\leq n . When k=4 , there are three expansions: P_{4}^{r} , S_{4}^{r} , and B_{4}^{r} , where B_{4} is the tree obtained by attaching an extra edge to a leaf of S_{3} . Figure 1: Configurations of B_{4}^{r} and E_{4}^{r} (in the figure r=5 ). Alongside these expansions, there is a notable non-expansion configuration known as the crown E_{4}^{r} , consisting of three pairwise disjoint hyperedges together with a fourth hyperedge, called the base , that intersects each of the other three. Crowns have been studied in a variety of settings in [ 1 ] , [ 2 ] , [ 17 ] , and [ 19 ] . In a related direction, Fletcher [ 6 ] obtained the bound ex_{3}^{\mathrm{lin}}(n,E_{4}^{3})<\frac{5n}{3} for the 3 -uniform case. Finding upper bounds on the Turán number of trees is already very difficult even in the graph setting (see the Erdős–Sós conjecture [ 4 ] , 1963). Therefore, we focus on small trees. 1.3 Steiner Systems A Steiner system S(t,r,n) comprises an n -vertex set together with blocks of size r such that every t -subset lies in exactly one block. In particular, S(2,r,n) repeatedly emerges in linear Turán extremal problems: its block count

Read the complete text