Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper resolves the long-standing question of whether the number of $C_k^{(r)}$-free $r$-graphs on $n$ labeled vertices is $2^{(1+o(1))\operatorname{ex}_{r}(n,C_{k}^{(r)})}$. For $(r,k)\neq(3,3)$, the authors establish balanced supersaturation for linear cycles and leverage the hypergraph container method. For the $(r,k)=(3,3)$ case, a novel approach involving decomposition by pair-codegrees and an entropy theorem is employed.
The exact number of hypergraphs free of specific cycle structures is finally characterized, settling a fundamental open problem in extremal hypergraph theory.
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 $\operatorname{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\geq5$. In this paper, we completely resolve the problem by proving that the answer is affirmative for every pair of integers $r,k\geq3$. When $(r,k)\neq(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.