The phase transition in random graphs - a simple proof

Details The phase transition in random graphs - a simple proof The phase transition in random graphs - a simple proof

2012-01-31

arxiv.org/abs/1201.6529v2

Mathematics

Combinatorics

Scientific paper

The classical result of Erdos and Renyi shows that the random graph G(n,p) experiences sharp phase transition around p=1/n - for any \epsilon>0 and p=(1-\epsilon)/n, all connected components of G(n,p) are typically of size O(log n), while for p=(1+\epsilon)/n, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime p=(1+\epsilon)/n, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games.

Affiliated with

Also associated with

No associations

Rating

The phase transition in random graphs - a simple proof 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 The phase transition in random graphs - a simple proof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The phase transition in random graphs - a simple proof will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56978