Counting dense connected hypergraphs via the probabilistic method

Journal article

In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on [n] = {1, 2, . . . , n} with m edges, whenever n → ∞ and n − 1 ≤ m = m(n) ≤ (  ⁿ₂). We give an asymptotic formula for the number C_r(n, m) of connected r-uniform hypergraphs on [n] with m edges, whenever r ≥ 3 is fixed and m = m(n) with m/n → ∞, i.e., the average degree tends to infinity. This complements recent results of Behrisch, Coja-Oghlan and Kang (the case m = n/(r − 1) + Θ(n)) and the present authors (the case m = n/(r − 1) + o(n), i.e., ‘nullity’ or ‘excess’ o(n)). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use ‘smoothing’ techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem.

Authors: Bollobás, B; Riordan, O

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: John Wiley & Sons
• Journal: Random Structures & Algorithms
• Volume: 53
• Issue: 2
• Pages: 185-220
• Publication date: 2018-02-13
• Acceptance date: 2017-07-22
• DOI: 10.1002/rsa.20762
• EISSN: 1098-2418
• ISSN: 1042-9832
• Keywords: random hypergraphs; hypergraph enumeration; local limit theorems