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. It is well known that { forb} (n, H) =2^ (1+o (1) ) {ex (n, H) } for k -uniform hypergraphs that are not k -partite. In a recent breakthrough, Ferber, McKinley, and Samotij proved that for many k -partite (or 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 sharp estimate of { forb} (n, C^ (k) _) =2^ ({ -12 +o (1) ) nk-1} for the k -uniform linear -cycle, for all pairs k 5, 3, thus settling a question of Balogh, Narayanan, and Skokan affirmatively for all k 5, 3. Our methods also lead to some sharp results on the related random Turán 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.