Paper Info
Title
Local Limit Theorems for the Giant Component of Random Hypergraphs.
Abstract
Let Hd(n,p) signify a random d-uniform hypergraph with nvertices in which each of the ${n}\choose{d}$ possible edges is present with probability p= p(n) independently, and let Hd(n,m) denote a uniformly distributed d-uniform hypergraph with nvertices and medges. We establish a local limit theoremfor the number of vertices and edges in the largest component of Hd(n,p) in the regime , thereby determining the joint distribution of these parameters precisely. As an application, we derive an asymptotic formula for the probability that Hd(n,m) is connected, thus obtaining a formula for the asymptotic number of connected hypergraphs with a given number of vertices and edges. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.
Year
DOI
Venue
2007
10.1007/978-3-540-74208-1_25
Combinatorics, Probability & Computing
Keywords
DocType
Volume
asymptotic formula,largest component,random hypergraphs,local limit theorems,asymptotic number,random d-uniform hypergraph,joint distribution,giant component,d-uniform hypergraph,enumerative combinatorics,local limit theoremfor,probability p,connected hypergraphs
Conference
23
Issue
ISSN
Citations 
3
0963-5483
2
PageRank 
References 
Authors
0.41
17
3
Name
Order
Citations
PageRank
Michael Behrisch1498.77
Amin Coja-Oghlan254347.25
Mihyun Kang316329.18