Poisson cloning model for random graphs

Abstract

In the random graph G(n, p) with pn bounded, the degrees of the vertices are almost i.i.d. Poisson random variables with mean λ := p(n − 1). Motivated by this fact, we introduce the Poisson cloning model _G_PC(n, p) for random graphs in which the degrees are i.i.d. Poisson random variables with mean λ.

We first establish a theorem that shows that the new model is equivalent to the classical model G(n, p) in an asymptotic sense. Next, we introduce a useful algorithm to generate the random graph _G_PC(n, p), called the cut-off line algorithm. Then _G_PC(n, p) equipped with the cut-off line algorithm enables us to very precisely analyze the sizes of the largest component and the t-core of G(n, p). This new approach for the problems yields not only elegant proofs but also improved bounds that are essentially best possible.

We also consider the Poisson cloning model for random hypergraphs and the G(n, p)-core problem for random hypergraphs.