Threshold function for a graph not being planar

Question

A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.

It is well-known that every monotone increasing graph property has a threshold $t(n)$, i.e,

$$\lim_{n \rightarrow \infty }P(G_{n,p} \text{ has property }\mathcal{P})=0$$

if $p\ll t(n)$ and

$$\lim_{n \rightarrow \infty }P(G_{n,p}\text{ has property }\mathcal{P})=1$$

if $p\gg t(n)$. Here $G_{n,p}$ is a random graph with $n$ vertices where each edge in the graph is added independently with probability $p$.

Property of a graph NOT being planar is monotone increasing. So the first question is what the threshold $t(n)$ for such a property $\mathcal{P}$ is. Does anyone know such a result?

There is another model for random graph, say $G_{n,m}$, which describes a random graph with $n$ vertices and $m$ edges. Similarly we can define a threshold $t^*(n)$ for a given property $\mathcal{P}$ concerning this model, i.e., $$\lim_{n \rightarrow \infty }P(G_{n,m}\text{ has property }\mathcal{P})=0$$ if $m\ll t^*(n)$ and $$\lim_{n \rightarrow \infty }P(G_{n,m}\text{ has property }\mathcal{P})=1$$ if $m\gg t^*(n)$.

It is well-known that if $m\geq 3n-5$, then $G_{n,m}$ is not planar and thus $G_{n,m}$ has propery $\mathcal{P}$. However, is there any result for the exact value of $t^*(n)$?

Answer 1

In the Erdős–Rényi model, the threshold for the planarity is know to be $t(n) = 1/n$. Perhaps one of the easiest ways to see this is the following.

If $p=o(1/n)$, then a straightforward union bound implies that the expected number of cycles in $G(n,p)$ is $$ \sum_{k=3}^n \binom{n}{k}\cdot \frac{(k-1)!}{2} \cdot p^k < \sum_{k=3}^n (pn)^k = \frac{(pn)^3}{1-pn} \to 0. $$ So, $G(n,p)$ has no cycles with high probability, and thus it is planar.

On the other hand, if $p=\omega(1/n)$, then one can easily check (again, via a straightforward union bound) that $$P\big(\alpha(G(n,p))> n/7\big) \le \binom{n}{n/7} \cdot (1-p)^{\binom{n/7}{2}}< 2^ne^{-pn^2/100} \to 0.$$ Thus, $\chi(G(n,p)) \ge n/\alpha(G(n,p)) \ge 7$ with high probability. In particular, this implies that $G(n,p)$ is not planar.

Try to check out some classic books on the topic (e.g. Béla Bollobás, Random Graphs, which has already been mentioned by Brendan McKay) if you want to investigate some stronger properties like sharp thresholds.

Answer 2

Consider the model where a random graph is made by adding one edge at a time chosen uniformly at random from edges not yet present.

Łuczak, Pittel and Wierman (1994) showed that there is a function $f(c)$ such that when the number of edges is $\frac12 n +cn^{2/3}$ the probability of being nonplanar tends to $f(c)$. Also $f(-\infty)=0$ and $f(\infty)=1$.

I got this from Béla Bollobás, Random Graphs, p151. His reference is "The structure of a random graph near the point of the phase transition", Trans. Amer. Math. Soc. 341, 721-748.