Resumen de Poisson cloning model for random graphs

Jeong Han Kim

• 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 GPC(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 newmodel is equivalent to the classical model G(n, p) in an asymptotic sense. Next, we introduce a useful algorithm to generate the random graph GPC(n, p), called the cut-off line algorithm. Then GPC(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 t-core problem for random hypergraphs.