13
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Mar 23, 2014 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$ Mar 23, 2014 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, 2014 at 11:18
  • 2
    $\begingroup$ If $e\gt3v-6$, the graph is not planar. $\endgroup$ Mar 30, 2014 at 11:31

1 Answer 1

11
+25
$\begingroup$

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.

$\endgroup$
2
  • 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$ Apr 1, 2014 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$ Apr 6, 2014 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.