Counting hypergraphs with large girth. Issue 3 (12th January 2022)

• Record Type: Journal Article
• Authors: Spiro, Sam; Verstraëte, Jacques
• Is Part Of: Journal of graph theory. Volume 100:Issue 3(2022)
• Page Start: 543
• Page End: 558
• Publication Date: 2022-01-12
• Subjects: Berge -- cycle -- hypergraph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22794
• Languages: English
• ISSNs: 0364-9024

Abstract

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.