The extremal number of tight cycles

2020/09/01 by Sudakov, Benny, Tomon, István
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2009.00528

Abstract

A tight cycle in an r-uniform hypergraph H is a sequence of ℓ≥ r+1 vertices x₁,…,x_ℓ such that all r-tuples \x_i,x_i+1,…,x_i+r-1\ (with subscripts modulo ℓ) are edges of H. An old problem of V. Sós, also posed independently by J. Verstraëte, asks for the maximum number of edges in an r-uniform hypergraph on n vertices which has no tight cycle. Although this is a very basic question, until recently, no good upper bounds were known for this problem for r≥ 3. Here we prove that the answer is at most n^r-1+o(1), which is tight up to the o(1) error term. Our proof is based on finding robust expanders in the line graph of H together with certain density increment type arguments.

Related

• On tight cycles in hypergraphs
• Hypergraphs with no tight cycles
• Sparse hypergraphs: new bounds and constructions
• Counting Hypergraphs with Large Girth
• Tight cycles and regular slices in dense hypergraphs