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

Abstract

Let $G(n,M)$ be the uniform random graph with $n$ vertices and $M$ edges. Erdős and Rényi (1960) conjectured that the limiting probability \[ \lim _{n \to \infty } \mathrm {Pr}\{G(n,\textstyle {n\over 2}) \hbox { is planar}\} \] exists and is a constant strictly between $0$ and $1$. Łuczak, Pittel and Wierman (1994) proved this conjecture, and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact limiting 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 } \mathrm {Pr} \left \{G\left (n,\textstyle {n\over 2}(1+\lambda n^{-1/3})\right ) \hbox { is planar} \right \}.\] 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.