For every fixed pair of integers r,k≥ 3, let C_k^(r) denote the r-uniform linear cycle with k hyperedges, and let operatornameex_r(n,C_k^(r)) be the maximum number of hyperedges in an n-vertex C_k^(r)-free r-uniform hypergraph. The conjecture is that, as n→∞, the number of labelled n-vertex C_k^(r)-free r-uniform hypergraphs is 2^(1+o(1))operatornameex_r(n,C_k^(r)); equivalently, |operatornameForb_r(n,C_k^(r))|=2^(1+o(1))operatornameex_r(n,C_k^(r)), where operatornameForb_r(n,C_k^(r)) is the family of such hypergraphs.

Balogh–Narayanan–Skokan counting conjecture for linear-cycle-free hypergraphs

For every fixed pair of integers $r,k\ge 3$ , let $C_k^{(r)}$ denote the $r$ -uniform linear cycle with $k$ hyperedges, and let $\operatorname{ex}_r(n,C_k^{(r)})$ be the maximum number of hyperedges in an $n$ -vertex $C_k^{(r)}$ -free $r$ -uniform hypergraph. The conjecture is that, as $n\to\infty$ , the number of labelled $n$ -vertex $C_k^{(r)}$ -free $r$ -uniform hypergraphs is $2^{(1+o(1))\operatorname{ex}_r(n,C_k^{(r)})}$ ; equivalently, $\left|\operatorname{Forb}_r(n,C_k^{(r)})\right|=2^{(1+o(1))\operatorname{ex}_r(n,C_k^{(r)})}$ , where $\operatorname{Forb}_r(n,C_k^{(r)})$ is the family of such hypergraphs.

References

Primary source

arXiv

Additional references

Counting hypergraphs without linear cycles of fixed length — arXiv — József Balogh, Ramon I. Garcia, Abhishek Methuku

enumerative-combinatorics extremal-combinatorics hypergraph-theory

Posted 6 days ago · edited 6 days ago

Progress summary

Refreshed 6 days ago

Claimed solved

A new unrefereed paper claims to settle the counting conjecture in every uniformity and cycle length, including the hardest known case, but the claim has not been independently checked.

The conjecture asks whether the number of hypergraphs avoiding a fixed linear cycle is asymptotically governed by the extremal number. Balogh, Narayanan, and Skokan established the correct exponential order in 2019 but left the sharper asymptotic open.

Known results

Balogh, Narayanan, and Skokan (2019): $2^{\Theta(n^{r-1})}$ hypergraphs for every fixed $r,k\ge3$ .
Their paper leaves open $|\operatorname{Forb}_r(n,C_k^{(r)})|=2^{(1+o(1))\operatorname{ex}_r(n,C_k^{(r)})}$ .
Jiang and Longbrake (2024): the sharper formula for $k\ge5$ , covering a broad class and settling those parameters.

September 30, 2026 claimed resolution

Balogh, Garcia, and Methuku claim the sharper formula for all fixed $r,k\ge3$ , including $(r,k)=(3,3)$ , in Counting hypergraphs without linear cycles. The retrieved evidence is an unrefereed preprint and contains no independent assessment.

Current status (as of October 2026): The cases $k\ge5$ are supported by prior work, while the claimed all- $r,k\ge3$ resolution, including $(3,3)$ , remains unverified.

Sources

No solutions have been posted yet.