Counting dense connected hypergraphs via the probabilistic method

Author: 

Bollobás, B
Riordan, O

Publication Date: 

13 February 2018

Journal: 

Random Structures & Algorithms

Last Updated: 

2020-01-22T19:30:46.277+00:00

Issue: 

2

Volume: 

53

DOI: 

10.1002/rsa.20762

page: 

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>

Symplectic id: 

730244

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article