The Extremal Number of Tight Cycles

Abstract: A tight cycle in an

r

-uniform hypergraph

m a t h c a l H

is a sequence of

e l l g e q r + 1

vertices

x_{1}, d o t s, x_{e l l}

such that all

r

-tuples

x_{i}, x_{i + 1}, d o t s, x_{i + r - 1}

(with subscripts modulo

e l l

) are edges of

m a t h c a l H

. An old problem of V. S'os, also posed independently by J. Verstra"ete, 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 g e q 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

m a t h c a l H

together with certain density increment type arguments.

Recommendations

Cited in

(16)

This page was built for publication: The Extremal Number of Tight Cycles