On the number of H-free hypergraphs

Abstract

Two central problems in extremal combinatorics are concerned with estimating the number $ex(n,H)$, the size of the largest $H$-free hypergraph on $n$ vertices, and the number $forb(n,H)$ of $H$-free hypergraph on $n$ vertices. While it is known that $forb(n,H)=2^{(1+o(1))ex(n,H)}$ for $k$-uniform hypergraphs that are not $k$-partite, estimates for hypergraphs that are $k$-partite (or degenerate) are not nearly as tight. In a recent breakthrough, Ferber, McKinley, and Samotij proved that for many degenerate hypergraphs $H$, $forb(n,H)=2^{O(ex(n,H))}$. However, there are few known instances of degenerate hypergraphs $H$ for which $forb(n,H)=2^{(1+o(1))ex(n,H)}$ holds. In this paper, we show that $forb(n,H)=2^{(1+o(1))ex(n,H)}$ holds for a wide class of degenerate hypergraphs known as $2$-contractible hypertrees. This is the first known infinite family of degenerate hypergraphs $H$ for which $forb(n,H)=2^{(1+o(1))ex(n,H)}$ holds. As a corollary of our main results, we obtain a surprisingly sharp estimate of $forb(n,C_{\ell }^{(k)})=2^{(\lfloor \frac{\ell -1}{2}\rfloor +o(1))(\genfrac{}{}{0ex}{}{n}{k-1})}$ for the $k$-uniform linear $\ell$-cycle, for all pairs $k\ge 5,\ell \ge 3$, thus settling a question of Balogh, Narayanan, and Skokan affirmatively for all $k\ge 5,\ell \ge 3$. Our methods also lead to some related sharp results on the corresponding random Turan problem. As a key ingredient of our proofs, we develop a novel supersaturation variant of the delta systems method for set systems, which may be of independent interest.

final version. appeared in Forum of Math, Sigma, vol 14, e20, 2026

References in corpus (5)

• Hypergraph containers
• Extremal results for random discrete structures
• Extremal results in random graphs
• The number of hypergraphs without linear cycles
• The number of triple systems without even cycles