Bounds on Linear Turán Number for Trees

Abstract

A hypergraph $H$ is said to be \emph{linear} if every pair of vertices lies in at most one hyperedge. Given a family $\mathcal{F}$ of $r$-uniform hypergraphs, an $r$-uniform hypergraph $H$ is said to be \emph{$\mathcal{F}$-free} if it contains no member of $\mathcal{F}$ as a subhypergraph. The \emph{linear Turán number} $e{x}_r^{\mathrm{lin}}(n,\mathcal{F})$ denotes the maximum number of hyperedges in an $\mathcal{F}$-free linear $r$-uniform hypergraph on $n$ vertices. Gyárfás, Ruszinkó, and Sárközy~[\emph{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$-uniform linear hypergraphs. In this paper, we extend the study of linear Turán numbers for acyclic systems to higher uniformity. We first give a construction for linear $r$-uniform trees with $k$ edges that yields the lower bound $e{x}_r^{\mathrm{lin}}(n,T_k^r)\ge 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^{\mathrm{lin}}(n,B_4^r)\le (r+1)n/r$ and characterize the extremal hypergraph class, where $B_4^r$ is formed from $S_3^r$ by appending a hyperedge incident to a degree-one vertex. We also prove the bound $e{x}_r^{\mathrm{lin}}(n,E_4^r)\le (2r-1)n/r$ for the crown $E_4^r$. Finally, we give a construction showing $e{x}_r^{\mathrm{lin}}(n,P_4^r)\ge (r+1)n/r$ under suitable assumptions and conclude with a conjecture on sharp upper bound for $P_4^r$.

Appeared in the proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2026) doi.org/10.1007/978-3-032-27732-9_2

Topics & keywords