1
$\begingroup$

In one of my lectures we derive the inequality $k \geq \frac{{n \choose 6}}{{n \choose 3}}$, where $k$ is a variable and $n$ the number of vertices in a graph. The lecturer then proceeds to state that "for $n$ large enough, we have $k \geq n^3$". I can see that $\frac{{n \choose 6}}{{n \choose 3}} = \frac{(n-3)(n-4)(n-5)}{6\cdot 5\cdot 4}$, and as $n$ grows large, $n^3 \approx (n-3)(n-4)(n-5)$. But the RHS never grows bigger than the LHS. So how can we make that claim about $k$?

$\endgroup$
2
$\begingroup$

You can't. What you can say, and what the lecturer probably meant, is that for $n$ large enough we have $k\geq cn^3$ where $c>0$ is some absolute constant. Presumably this is good enough for whatever you actually use the bound to prove.

$\endgroup$
2
  • $\begingroup$ Yes, the question is actually about the existence of the constant $c$ and the integer $n^*$ such that for $n \geq n^*$, certain condition involved $k$ is satisfied. I was thinking along the line of "finding $c$", but it seems more like $c$ is something we would specify, and then we find the appropriate $n^*$ to satisfy the condition on $k$? $\endgroup$ – ensbana Dec 24 '19 at 10:59
  • $\begingroup$ @ensbana yes, you could choose any value of $c$ which is strictly less than $1/120$ and then calculate an explicit $n^*$ if you wanted to. (For example, if you pick $c=1/200$ then $n^*$ works out to be $26$.) $\endgroup$ – Especially Lime Dec 24 '19 at 11:11

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.