Local limit theorems and the number of connected hypergraphs
By Michael Behrisch and Amin Coja-Oghlan and Mihyun KangSubmitted
Abstract
Let Hd(n,p) denote 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 Hd(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 Hd(n,p) and Hd(n,m). As an application, we obtain an asymptotic formula for the probability that Hd(n,p) is connected, and a corresponding formula for Hd(n,m). In addition, we infer a local limit theorem for the conditional distribution of the number of edges in Hd(n,p) given that Hd(n,p) is connected. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.
