2011/08/05 by Zoltán Füredi, Tao Jiang, Furedi, Zoltan +3
Computer Science · Mathematics · #05C35 #05C65 #05D05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1108.1247
openalex publication_date 2011/08/05 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
A k-uniform linear path of length ℓ, denoted by P(k)_ℓ, is a family of k-sets \F1,..., F_ℓ\ such that |Fi∩ Fi+1|=1 for each i and Fi∩ Fj=∅ whenever |i-j|>1. Given a k-uniform hypergraph H and a positive integer n, the \it k-uniform hypergraph Turán number of H, denoted by \exk(n,H), is the maximum number of edges in a k-uniform hypergraph \cF on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine \exk(n,P(k)_ℓ) exactly for all fixed ℓ≥ 1, k≥ 4, and sufficiently large n. We show that \exk(n,P(k)2t+1)=n-1\choose k-1+n-2\choose k-1+...+n-t\choose k-1. The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that \ex(n, P(k)2t+2)=n-1\choose k-1+n-2\choose k-1+...+n-t\choose k-1+n-t-2\choose k-2, and describe the unique extremal family. Stability results on these bounds and some related results are also established.