Poisson Cloning Model for Random Graphs

Details Poisson Cloning Model for Random Graphs Poisson Cloning Model for Random Graphs

2008-05-27

arxiv.org/abs/0805.4133v1

Mathematics

Combinatorics

Scientific paper

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 $\gl:= 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 $\gl$. 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 $G_{PC} (n,p)$. The Poisson cloning model $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 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.

Affiliated with

Also associated with

No associations

Rating

Poisson Cloning Model for Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Poisson Cloning Model for Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Poisson Cloning Model for Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-273869