# Counting dense connected hypergraphs via the probabilistic method

Bollobás, B
Riordan, O

13 February 2018

## Journal:

Random Structures & Algorithms

## Last Updated:

2020-07-03T14:48:29.293+01:00

2

53

## DOI:

10.1002/rsa.20762

185-220

## abstract:

<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>) ≤ (  <sup><em>n</em></sup><sub style="position: relative; left: -.5em;">2</sub>). We give an asymptotic formula for the number <em>C<sub>r</sub></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>

730244

Submitted

Journal Article