The number of hypergraphs without linear cycles

Abstract

The $r$-uniform linear $k$-cycle $C_k^r$ is the $r$-uniform hypergraph on $k(r-1)$ vertices whose edges are sets of $r$ consecutive vertices in a cyclic ordering of the vertex set chosen in such a way that every pair of consecutive edges share exactly one vertex. Here, we prove a balanced supersaturation result for linear cycles which we then use in conjunction with the method of hypergraph containers to show that for any fixed pair of integers $r,k\ge 3$, the number of $C_k^r$-free $r$-uniform hypergraphs on $n$ vertices is $2^{\Theta (n^{r-1})}$, thereby settling a conjecture due to Mubayi and Wang.

15 pages, submitted