Counting hypergraphs with large girth.

Morris and Saxton used the method of containers to bound the number of n‐vertex graphs with m edges containing no ℓ‐cycles, and hence graphs of girth more than ℓ. We consider a generalization to r‐uniform hypergraphs. The girth of a hypergraph H is the minimum ℓ≥2 such that there exist distinct vertices v1,...,vℓ and hyperedges e1,...,eℓ with vi,vi+1∈ei for all 1≤i≤ℓ. Letting Nmr(n,ℓ) denote the number of n‐vertex r‐uniform hypergraphs with m edges and girth larger than ℓ and defining λ=⌈(r−2)∕(ℓ−2)⌉, we show Nmr(n,ℓ)≤Nm2(n,ℓ)r−1+λ, which is tight when ℓ−2 divides r−2 up to a 1+o(1) term in the exponent. This result is used to address the extremal problem for subgraphs of girth more than ℓ in random r‐uniform hypergraphs. [ABSTRACT FROM AUTHOR]