Premium
Counting hypergraphs with large girth
Author(s) -
Spiro Sam,
Verstraëte Jacques
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22794
Subject(s) - combinatorics , mathematics , hypergraph , girth (graph theory) , vertex (graph theory) , exponent , generalization , upper and lower bounds , discrete mathematics , graph , mathematical analysis , philosophy , linguistics
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.