Counting dense connected hypergraphs via the probabilistic method. Issue 2 (13th February 2018) - Bollobás, Béla; Riordan, Oliver
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.