Linear Turán Numbers of Uniform Hypertrees

Abstract

A hypergraph is linear if every pair of vertices is contained in at most one hyperedge. We study linear Turán numbers of acyclic $r$-uniform hypergraphs, extending earlier work of Gyárfás, Ruszinkó, and Sárközy from uniformity $3$ to general $r$, with emphasis on hypertrees with four hyperedges. For the linear path $P_4^r$, we prove ${\mathrm{ex}}_r^{\mathrm{lin}}(n,P_4^r)\le (r+1)n/r$, with equality precisely for disjoint unions of Steiner systems $S(2,r,r^2)$, whenever such systems exist. We also give counterexamples to a structural claim used in a previously proposed proof for $r=4$. The same bound and equality characterization hold for the broom $B_4^r$. For the crown $E_4^r$, writing $B=\{v:d(v)\le r\}$ and $C=\{v:r+1\le d(v)\le 2r-1\}$, we prove $|E(H)|\le r|B|/(r-1)+(2r-1)|C|/r$, and hence ${\mathrm{ex}}_r^{\mathrm{lin}}(n,E_4^r)\le (2r-1)n/r$. We also give a lower-bound construction and formulate a sharper conjecture. Finally, for the linear star $S_k^r$, we prove ${\mathrm{ex}}_r^{\mathrm{lin}}(n,S_k^r)\le n(k-1)/r$, with equality precisely for $(k-1)$-regular linear $r$-uniform hypergraphs, whenever such hypergraphs exist. Under suitable divisibility and existence assumptions, we also construct $T_k^r$-free examples with $n(k-1)/r$ edges for every linear $r$-uniform hypertree $T_k^r$ with $k$ hyperedges.

arXiv commentA preliminary version of this work appeared in the proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2026) http://link.springer.com/chapter/10.1007/978-3-032-27732-9_2. This paper is a substantially extended version of the conference paper