I've been attempting to solve the following challenge problem from a combinatorics class but am getting absolutely nowhere.

Prove: For sufficiently large $n$, the probability a random graph $G=(V,E)$ with $n$ vertices is planar is less than $2^{-0.49n^2}$.

I've ruled out using Kuratowski's characterization of planarity for proving this (since I know it's hard to determine whether or not a subgraph $G' \subset G$ is a topological $K_{3,3}$ or $K_5$. The other characterization I'm aware of is if a graph is planar, then $\exists v \in V$ such that $deg[v] \leq 5$. So the probability a random graph is planar is equivalent to $1-\mathbb{P}$ ,where $\mathbb{P} = $ the probability that a random graph has no vertices of degree less than or equal to 5.

However, I can't see how to proceed from this observation. Solutions/hints would be appreciated.

  • $\begingroup$ It's disingenuous to say that "the probability a random graph is planar is ... $1-\mathbb{P}$"; you said that IF a graph is planar, then it has such a vertex -- not that the existence of such a vertex is equivalent to planarity. $\endgroup$ – Nick Peterson Mar 23 '14 at 3:46
  • $\begingroup$ What is your random model for the graph? Each of the $\binom{n}{2}$ is either present or not present, with equal probability $1/2$? $\endgroup$ – ShreevatsaR Mar 23 '14 at 7:04
  • $\begingroup$ Yes, @ShreevatsaR, each of the $\binom{n}{2}$ edges has a probability of $1/2$ of being included (or more generally probability $p$). Also Nicholas, it's a necessary but not sufficient condition if I'm not mistaken - the existence of such a vertex is not equivalent to planarity, but rather, if no such vertex exists then the graph is NOT planar (so if all vertices have degree 6 or more, then there is no way for it to be planar). $\endgroup$ – rm95 Mar 24 '14 at 11:18
  • 2
    $\begingroup$ If $e\gt3v-6$, the graph is not planar. $\endgroup$ – Gerry Myerson Mar 30 '14 at 11:31

A random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (that's a necessary condition for planarity) is $$2^{-n(n-1)/2}\sum_{k=0}^{3n-6}{n(n-1)/2\choose k}$$ There are standard ways to estimate the sum.

  • 2
    $\begingroup$ Vith a very crude bound, $$\sum_{k=0}^{3n-6}\binom{n(n-1)/2}{k}< e\cdot (n^2/2)^{3n} < e^{6n\log n} < 2^{9n\log n}.$$ $\endgroup$ – Jack D'Aurizio Apr 1 '14 at 23:35
  • 1
    $\begingroup$ @JackD'Aurizio: Just for completeness, that turns out to be sufficient to prove the claim: $\dfrac{2^{9n \log n}}{2^{n(n-1)/2}} = 2^{9n\log n - n(n-1)/2}$, and so we want to say that $9n\log n - n(n-1)/2 < -0.49n^2$ or that $9n\log n < n(n-1)/2 - 0.49n^2 = 0.01n^2 - n/2$ for sufficiently large $n$. And this is clearly the case, as the LHS grows as $\Theta(n \log n)$ but the RHS as $\Theta(n^2)$. $\endgroup$ – ShreevatsaR Apr 6 '14 at 7:16

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.