9
$\begingroup$

Let $r(n,n)=r(n)$ be the usual Ramsey number of a graph. It is known that $\frac{1}{e\sqrt{2}}n2^{n/2} as a lower bound for $r(n).$

Now, in the proof given in the book Erdős on Graphs by Graham and Chung, as an intermediate step this is given:

$2^{\binom{m}{2}}>\binom{m}{n}2^{\binom{m}{2}-\binom{n}{2}+1}\;,\tag{*}$ and that this implies that $m\ge\frac{1}{e\sqrt{2}}n2^{n/2}\;.\tag{**}$

I cannot figure out how $(*)$ implies $(**)$. Can someone please explain this?

  • 0
    A couple of the pieces in that bound make me think [Stirling's Approximation of $n!$](http://en.wikipedia.org/wiki/Stirling's_approximation) was involved.2012-02-07

1 Answers 1

5

In fact, the inequality $(**)$ should be the other way around.

As Austin Mohr noted, Stirling's formula comes in handy here. The form that I will use is $n! \sim \biggl(\dfrac{n}{e}\biggr)^n \sqrt{2\pi n}. \tag{1}$ Also, I assume that $m \to \infty$ and that $m - n \to \infty$.

We start by observing that the inequality $(**)$ is equivalent to $\dbinom{m}{n} < 2^{\binom{n}{2} - 1}. \tag{2}$ Since $\dbinom{m}{n} \geq \dfrac{(m - n)^n}{n!},$ we have from $(2)$ that $(m - n)^n < n! 2^{\binom{n}{2} - 1}.$ Plugging in Stirling's formula $(1)$, we have $m^n \biggl(1 - \dfrac{n}{m}\biggr)^n < \biggl(\dfrac{n}{e}\biggr)^n \sqrt{\dfrac{\pi n}{2}} 2^{\binom{n}{2}}.$ Taking $n$th roots, we get $m \biggl(1 - \dfrac{n}{m}\biggr) < \dfrac{n}{e} 2^{\frac{n - 1}{2}} \biggl(\dfrac{\pi n}{2}\biggr)^{1/2n}.$ Finally, observing that $(\frac{\pi n}{2})^{1/2n} / (1 - \frac{n}{m}) \to 1$ as $m$, $n \to \infty$, we end up with $m < \dfrac{1}{e\sqrt{2}} n 2^{n/2},$ as desired.