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₄^r, we prove ex^lin_r(n,P₄^r)≤ (r+1)n/r, with equality precisely for disjoint unions of Steiner systems S(2,r,r²), 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₄^r. For the crown E₄^r, writing B={v:d(v)≤ r} and C={v:r+1≤ d(v)≤2r−1}, we prove |E(H)|≤ r|B|/(r−1)+(2r−1)|C|/r, and hence ex^lin_r(n,E₄^r)≤(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 ex^lin_r(n,S_k^r)≤ 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.

Turán Numbers of Linear Stars and Expanded Trees
Xinmin Hou, Anyao Wang
arXiv11 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Linear Tur'an Numbers of Four-Edge Uniform Paths via Incidence Rank
Mahesh Ramani
arXiv1 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
The uniform Turán density of the tetrahedron
Matija Bucić
arXiv23 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Turán numbers for suspensions of bipartite 2-regular graphs
Haoxing Wu, Junxue Zhang
arXiv29 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
On the structure of uniform Turán densities
Heng Li, Xizhi Liu
arXiv5 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{adak2026linear,
  title = {{Linear Turán Numbers of Uniform Hypertrees}},
  author = {Rajat Adak and Pragya Verma},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2607.16854},
  eprint = {2607.16854},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.16854},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Linear Turán Numbers of Uniform Hypertrees
AU  - Rajat Adak
AU  - Pragya Verma
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2607.16854
UR  - https://arxiv.org/abs/2607.16854
AB  - 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 ex^lin_r(n,P_4^r)≤ (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)≤ r} and C={v:r+1≤ d(v)≤2r−1}, we prove |E(H)|≤ r|B|/(r−1)+(2r−1)|C|/r, and hence ex^lin_r(n,E_4^r)≤(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 ex^lin_r(n,S_k^r)≤ 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.
ER  -

Abstract

Related

Cite