Counting hypergraphs without linear cycles of fixed length
Abstract
Let Ck(r) be the r-uniform linear cycle on k hyperedges. An r-graph is Ck(r)-free if it contains no copy of Ck(r). Let exr(n,Ck(r)) denote the maximum number of hyperedges in an n-vertex Ck(r)-free r-graph. Balogh, Narayanan and Skokan asked whether, for every pair of integers r,k≥ 3, the number of Ck(r)-free r-graphs on n labelled vertices is 2(1+o(1))exr(n,Ck(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≥5. In this paper, we completely resolve the problem by proving that the answer is affirmative for every pair of integers r,k≥3. When (r,k)≠(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.
Related
BibTeX
@misc{balogh2026counting,
title = {{Counting hypergraphs without linear cycles of fixed length}},
author = {József Balogh and Ramon I. Garcia and Abhishek Methuku},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.38772},
eprint = {2609.38772},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38772},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Counting hypergraphs without linear cycles of fixed length
AU - József Balogh
AU - Ramon I. Garcia
AU - Abhishek Methuku
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2609.38772
UR - https://arxiv.org/abs/2609.38772
AB - 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 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≥ 3, the number of C_k^(r)-free r-graphs on n labelled vertices is 2^(1+o(1))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≥5. In this paper, we completely resolve the problem by proving that the answer is affirmative for every pair of integers r,k≥3. When (r,k)≠(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.
ER -