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$?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
2
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.
answered Dec 24 '19 at 10:51
-
$\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
