Linear Turán Numbers of Uniform Hypertrees

Abstract

A hypergraph is \emph{linear} if every pair of vertices is contained in at most one hyperedge. For a family $\mathcal{F}$ of $r$-uniform hypergraphs, let $\operatorname{ex}^{\mathrm{lin}}_r(n,\mathcal{F})$ denote the maximum number of hyperedges in an $n$-vertex $\mathcal{F}$-free linear $r$-uniform hypergraph. Extending earlier work on acyclic triple systems, we study linear Turán numbers of uniform hypertrees in higher uniformity. For the linear star $S_k^r$, we prove \[ \operatorname{ex}^{\mathrm{lin}}_r(n,S_k^r)\leq \frac{n(k-1)}{r}, \] with equality precisely for $(k-1)$-regular linear $r$-uniform hypergraphs, whenever such hypergraphs exist. Under suitable divisibility and design-existence assumptions, we also construct $T_k^r$-free hypergraphs with $n(k-1)/r$ edges for every linear $r$-uniform hypertree $T_k^r$ with $k$ hyperedges. For the four-edge broom $B_4^r$, we prove \[ \operatorname{ex}^{\mathrm{lin}}_r(n,B_4^r)\leq \frac{(r+1)n}{r}, \] with equality exactly for disjoint unions of Steiner systems $S(2,r,r^2)$, whenever such systems exist. For the crown $E_4^r$, we establish a degree-sensitive upper bound implying \[ \operatorname{ex}^{\mathrm{lin}}_r(n,E_4^r)\leq \frac{(2r-1)n}{r}, \] and give a lower-bound construction leaving a constant-factor gap. Finally, we settle the linear Turán problem for the four-edge path $P_4^r$ in every uniformity: \[ \operatorname{ex}^{\mathrm{lin}}_r(n,P_4^r)\leq \frac{(r+1)n}{r}. \] Equality holds precisely for disjoint unions of Steiner systems $S(2,r,r^2)$. We also give counterexamples to a key structural claim used in a previously proposed proof of the $4$-uniform case.

Disclosure

“longer paths. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relation- ships that could have appeared to influence the work reported in this paper. Declaration of Generative AI and AI-Assisted Technologies During the preparation of this work, the authors used ChatGPT (OpenAI) as an auxiliary research tool to assist with computations related to the proof of Lemma 6.4 and with the construction and verification of t”

PDF page 22

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:57:28.244272Z

Structural counts