Counting dense connected hypergraphs via the probabilistic method

<p>In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on [<em>n</em>] = {1, 2, . . . , <em>n</em>} with <em>m</em> edges, whenever <em>n</em> → ∞ and <em>n</em> − 1 ≤ <em>m</em> = <em>m</em>(<em>n</em>) ≤ (  ^<em>n</em><sub style="position: relative; left: -.5em;">2</sub>). We give an asymptotic formula for the number <em>C_r</em>(<em>n</em>, <em>m</em>) of connected <em>r</em>-uniform hypergraphs on [<em>n</em>] with <em>m</em> edges, whenever <em>r</em> ≥ 3 is fixed and <em>m</em> = <em>m</em>(<em>n</em>) with <em>m</em>/<em>n</em> → ∞, i.e., the average degree tends to infinity. This complements recent results of Behrisch, Coja-Oghlan and Kang (the case <em>m</em> = <em>n</em>/(<em>r</em> − 1) + Θ(<em>n</em>)) and the present authors (the case <em>m</em> = <em>n</em>/(<em>r</em> − 1) + <em>o</em>(<em>n</em>), i.e., ‘nullity’ or ‘excess’ <em>o</em>(<em>n</em>)). 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.</p>