Large hypergraphs without tight cycles

Abstract: An

r

-uniform tight cycle of length

e l l > r

is a hypergraph with vertices

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

and edges

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

(for all

i

), with the indices taken modulo

e l l

. It was shown by Sudakov and Tomon that for each fixed

r g e q 3

, an

r

-uniform hypergraph on

n

vertices which does not contain a tight cycle of any length has at most

n^{r - 1 + o (1)}

hyperedges, but the best known construction (with the largest number of edges) only gives

O m e g a (n^{r - 1})

edges. In this note we prove that, for each fixed

r g e q 3

, there are

r

-uniform hypergraphs with

O m e g a (n^{r - 1} l o g n / l o g l o g n)

edges which contain no tight cycles, showing that the

o (1)

term in the exponent of the upper bound is necessary.

Recommendations

Cites Work

Cited In (14)

This page was built for publication: Large hypergraphs without tight cycles