Counting dense connected hypergraphs via the probabilistic method. Issue 2 (13th February 2018)

• Record Type: Journal Article
• Authors: Bollobás, Béla; Riordan, Oliver
• Is Part Of: Random structures & algorithms. Volume 53:Issue 2(2018)
• Page Start: 185
• Page End: 220
• Publication Date: 2018-02-13
• Subjects: random hypergraphs -- hypergraph enumeration -- local limit theorems; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20762
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 ) ⩽ ( n 2 ) . 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 → ∞, that is, 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 ), ie, "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.