Local Limit Theorems and the Number of Connected Hypergraphs
Please always quote using this URN:urn:nbn:de:0296-matheon-3711
- Let H_d(n, p) signify a random d-uniform hypergraph with n vertices in which each of the possible edges is present with probability p = p(n) independently, and let H_d(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of H_d(n, p) and H_d(n,m). As an application, we obtain an asymptotic formula for the probability that H_d(n, p) is connected, and a corresponding formula for H_d(n,m). In addition, we infer a local limit theorem for the conditional distribution of the number of edges in H_d(n, p) given that H_d(n, p) is connected. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.
Author: | Michael Behrisch, Amin Coja-Oghlan, Mihuyn Kang |
---|---|
URN: | urn:nbn:de:0296-matheon-3711 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2007/07/01 |
Release Date: | 2007/05/01 |
Tag: | |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 365 |