2026/07/18 by Rajat Adak, Pragya Verma
#math.CO #cs.DM
A hypergraph is linear if every pair of vertices is contained in at most one hyperedge. For a family F of r-uniform hypergraphs, the linear Tur'an number exlinr(n,F) is the maximum number of hyperedges in an n-vertex F-free linear r-uniform hypergraph. Extending the work of Gy'arf'as, Ruszink'o, and S'ark"ozy on 3-uniform linear hypertrees, we study linear Tur'an numbers for higher uniformity. We determine the linear Tur'an number of the r-uniform linear star Skr, proving [exlinr(n,Skr)≤ (n(k-1))/(r),] with equality exactly for (k-1)-regular linear r-uniform hypergraphs, whenever they exist. We also construct dense Tkr-free hypergraphs showing that, under suitable divisibility and design-existence assumptions, [exlinr(n,Tkr)≥ (n(k-1))/(r)] for every linear r-uniform hypertree Tkr with k hyperedges. We then study all linear hypertrees with four hyperedges. For the broom B4r, we prove [exlinr(n,B4r)≤ ((r+1)n)/(r),] and characterize the extremal hypergraphs as disjoint unions of Steiner systems S(2,r,r2), whenever such systems exist. For the crown E4r, we establish [exlinr(n,E4r)≤ ((2r-1)n)/(r),] together with a lower-bound construction leaving only a constant-factor gap. For the linear path P4r, we construct P4r-free hypergraphs with (r+1)n/r hyperedges and conjecture this is the optimal general bound. We verify the conjecture for connected hypergraphs under suitable degree conditions. Finally, for r=4, we identify counterexamples to a key structural claim in a previous proof of Zhang and Wang, give a new proof that [exlin4(n,P44)≤ (5n)/(4),] and show that equality holds precisely for disjoint unions of Steiner systems S(2,4,16).