On the probability of planarity of a random graph near the critical point

Details On the probability of planarity of a random graph near the critical point On the probability of planarity of a random graph near the critical point

2012-04-16

arxiv.org/abs/1204.3376v1

Mathematics

Combinatorics

10 pages, 1 figure

Scientific paper

Consider the uniform random graph $G(n,M)$ with $n$ vertices and $M$ edges. Erd\H{o}s and R\'enyi (1960) conjectured that the limit $$ \lim_{n \to \infty} \Pr\{G(n,\textstyle{n\over 2}) is planar}} $$ exists and is a constant strictly between 0 and 1. \L uczak, Pittel and Wierman (1994) proved this conjecture and Janson, \L uczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact probability of a random graph being planar near the critical point $M=n/2$. For each $\lambda$, we find an exact analytic expression for $$ p(\lambda) = \lim_{n \to \infty} \Pr{G(n,\textstyle{n\over 2}(1+\lambda n^{-1/3})) is planar}.$$ In particular, we obtain $p(0) \approx 0.99780$. We extend these results to classes of graphs closed under taking minors. As an example, we show that the probability of $G(n,\textstyle{n\over 2})$ being series-parallel converges to 0.98003. For the sake of completeness and exposition we reprove in a concise way several basic properties we need of a random graph near the critical point.

Affiliated with

Also associated with

No associations

Rating

On the probability of planarity of a random graph near the critical point 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 On the probability of planarity of a random graph near the critical point, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the probability of planarity of a random graph near the critical point will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-5986