Two critical periods in the evolution of random planar graphs

Details Two critical periods in the evolution of random planar graphs Two critical periods in the evolution of random planar graphs

2010-06-02

arxiv.org/abs/1006.0444v2

Mathematics

Combinatorics

30 pages, 1 figure

Scientific paper

Let $P(n,M)$ be a graph chosen uniformly at random from the family of all labeled planar graphs with $n$ vertices and $M$ edges. In the paper we study the component structure of $P(n,M)$. Combining counting arguments with analytic techniques, we show that there are two critical periods in the evolution of $P(n,M)$. The first one, of width $\Theta(n^{2/3})$, is analogous to the phase transition observed in the standard random graph models and takes place for $M=n/2+O(n^{2/3})$, when the largest complex component is formed. Then, for $M=n+O(n^{3/5})$, when the complex components cover nearly all vertices, the second critical period of width $n^{3/5}$ occurs. Starting from that moment increasing of $M$ mostly affects the density of the complex components, not its size.

Affiliated with

Also associated with

No associations

Rating

Two critical periods in the evolution of random planar 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 Two critical periods in the evolution of random planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two critical periods in the evolution of random planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-513361