6
$\begingroup$

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}~has~property~\mathcal{P})=0$$ if $p<<t(n)$ and $$\lim_{n \rightarrow \infty }P(G_{n,p}~has~property~\mathcal{P})=1$$ if $p>>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}~has~property~\mathcal{P})=0$$ if $m<<t^*(n)$ and $$\lim_{n \rightarrow \infty }P(G_{n,m}~has~property~\mathcal{P})=1$$ if $m>>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)$?

$\endgroup$

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ An interesting subsequent article is dmtcs.episciences.org/2343 of Noy, Ravelomanana and Rué, where they obtain an exact expression for the function $f$. $\endgroup$ Jun 15 at 9:21
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.