|
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}<r(n)$$ 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? |
|||||
|
|
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{*}$$ 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{**}$$ Since $$\dbinom{m}{n} \geq \dfrac{(m - n)^n}{n!},$$ we have from $(**)$ that $$(m - n)^n < n! 2^{\binom{n}{2} - 1}.$$ Plugging in Stirling's formula $(*)$, 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. |
||||
|
|
