Counting hypergraphs with large girth. Issue 3 (12th January 2022) - Spiro, Sam; Verstraëte, Jacques
Abstract: 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 v 1, …, v ℓ and hyperedges e 1, …, e ℓ with v i, v i + 1 ∈ e i for all 1 ≤ i ≤ ℓ . Letting N m r ( n, ℓ ) denote the number of n ‐vertex r ‐uniform hypergraphs with m edges and girth larger than ℓ and defining λ = ⌈ ( r − 2 ) ∕ ( ℓ − 2 ) ⌉, we show N m r ( n, ℓ ) ≤ N m 2 ( 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.