Poisson Cloning Model for Random Graphs

By Jeong Han Kim. 2008

89 citations recorded by the source corpus.

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 GP C(n, p) for random graphs in which the degrees are i.i.d Poisson random variables with mean λ. Then, we first establish a theorem that shows the new model is equivalent to the classical model G(n, p) in an asymptotic sense. Next, we introduce a useful algorithm, called the cut-off line algorithm, to generate the random graph GP C(n, p). The Poisson cloning model GP C(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 to the problems yields not only elegant proofs but also improved bounds that are essentially best possible. We also consider the Poisson cloning models for random hypergraphs and random k-SAT problems. Then, the t-core problem for random hypergraphs and the pure literal algorithm for random k-SAT problems are analyzed.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/f8935ad9f7c3580da43463bc4cfdcf4e58a09e36

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Discrete Mathematics and Combinatorics

Citations in the corpus

On the phase transition in random simplicial complexes (2014, background): “The d -tree is also the local weak limit of the bipartite incidence graph between vertices and hyperedges in random ( d + 1)- uniform hypergraphs in which every hyperedge is chosen independently with probability c/ [18], [19].”
Asymptotic normality of the k-core in random graphs (2006, methodology): “Further, related models of random graphs have been studied by Kim [20], Darling and Norris [7] and Cain and Wormald [5].”