# Poisson cloning model for random graphs

### Jeong Han Kim

Theory Group, Redmond, USA

A subscription is required to access this book chapter.

## 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 ﬁrst 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.