Counting hypergraphs without linear cycles of fixed length

Abstract

Let $C_k^{(r)}$ be the $r$-uniform linear cycle on $k$ hyperedges. An $r$-graph is $C_k^{(r)}$-free if it contains no copy of $C_k^{(r)}$. Let ${\mathrm{ex}}_r(n,C_k^{(r)})$ denote the maximum number of hyperedges in an $n$-vertex $C_k^{(r)}$-free $r$-graph. Balogh, Narayanan and Skokan asked whether, for every pair of integers $r,k\ge 3$, the number of $C_k^{(r)}$-free $r$-graphs on $n$ labelled vertices is \[ 2^{(1+o(1))\operatorname{ex}_{r}(n,C_{k}^{(r)})}. \] While the analogous statement is known to fail for graphs ($r=2$), by a construction of Morris and Saxton, the general question remained open for hypergraphs. Very recently, Jiang and Longbrake answered the question affirmatively when $r\ge 5$. In this paper, we completely resolve the problem by proving that the answer is affirmative for every pair of integers $r,k\ge 3$. When $(r,k)\ne (3,3)$, we establish balanced supersaturation results for linear cycles and combine them with the hypergraph container method. For $(r,k)=(3,3)$, we instead decompose $3$-graphs according to their pair-codegrees, encode the subhypergraph formed by the hyperedges that contain a large codegree pair as a directed graph, and apply a multicolour entropy theorem.

arXiv commentMinor changes made