8
$\begingroup$

Can you come up with a simple proof that $\exists n_0\in\mathbb{N}$ such that $\forall n\in\mathbb{N}, \:n\ge n_0$ there are more bipartite graphs on $n$ vertices than planar graphs on $5n$ vertices?

(Or the other way round, I am actually trying to find out the order, this is just what I think is true.)

This is a homework, so I am looking for advice rather than solutions. So far, I have come with the following:

  • From Euler's formula, it follows that for every planar graph $G=(V,\:E)$, it is true that $|E| \le3|V|$. Therefore, I assume, there is at most ${n^2\choose3n}$ different planar graphs on $n$ vertices.
  • There is at least $2^{n^2/4}$ different bipartite graphs on $n$ vertices (if we choose the size of each "part" to be $n/2$).

Are these thoughts worth anything? It feels like I should choose a different approach to this exercise, but cannot think of anything else.

David

Close-up: As EuYu pointed out, my original bound for planar graphs is not correct as it only takes graphs with 3n edges into account. However, the proof as proposed by Ross Milikan holds.

Thanks for everyone's help!

$\endgroup$
8
  • 2
    $\begingroup$ @David Would you mind elaborating how you got the upper bound for the planar graphs? Did you mean to choose $3n$ edges from the $n(n-1)/2$ edges as the upper bound? Wouldn't that just be an upper bound on the number of planar graphs with $3n$ edge? $\endgroup$
    – EuYu
    Apr 22 '13 at 15:16
  • 1
    $\begingroup$ I think it's no big deal, I just wanted to be sure. You can always just multiply by $3n$ to compensate for the other choices. The order of magnitude remains the same. $\endgroup$
    – EuYu
    Apr 22 '13 at 15:25
  • 1
    $\begingroup$ For $n\geq 6$, $\binom{n^2}{k}\leq \binom{n^2}{3n}$ when $k=0,\dots,3n$. So you still get an upper bound of $(3n+1)\binom{n^2}{3n}$ which is still bounded by $2^{n^2/4}$ for $n$ large. $\endgroup$
    – Thomas Andrews
    Apr 22 '13 at 15:28
  • 1
    $\begingroup$ Your figure ${n^2 \choose 3n}$ only counts graphs with exactly $3n$ edges. You need to count graphs with less edges as well, which adds the factor Thomas Andrews shows. That will require a small update to the argument. In fact, the number of pairs of vertices is $\frac 12n(n-1)$ so you could use that as the upper value. $\endgroup$
    – Ross Millikan
    Apr 22 '13 at 15:47
  • 1
    $\begingroup$ I found this article with a tighter bound if you are interested. $\endgroup$
    – Ross Millikan
    Apr 22 '13 at 15:48
2
$\begingroup$

This is a good approach. You can bound ${n^2 \choose 3n} \lt (n^2)^{3n}=n^{6n}$ by considering the factors in the numerator are $n^2(n^2-1)(n^2-2)\ldots (n^2-3n+1)$, rounding them all up to $n^2$ and ignoring the $(3n)!$ in the denominator. This will be less than $2^{n^2/2}$ for $n$ large enough. To find how large $n$ needs to be, take logs. Of course you could get a tighter bound, but if you just want to prove that eventually there are more bipartite graphs this is sufficient.

$\endgroup$
2
  • $\begingroup$ His count for planar graphs on $n$ nodes need to then have $5n$ replaced for $n$. You still get eventual inequality in the same direction. $\endgroup$
    – Thomas Andrews
    Apr 22 '13 at 15:32
  • $\begingroup$ Thank you for helping out! $\endgroup$
    – David
    Apr 24 '13 at 11:20

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.