paso intermedio en la demostración de edad Ramsey límite inferior

Question

Deje $r(n,n)=r(n)$ será el habitual de Ramsey número de un gráfico. Se sabe que $$\frac{1}{e\sqrt{2}}n2^{n/2}<r(n)$$ as a lower bound for $r(n).$

Ahora, en la prueba dada en el libro de Erdős en los Gráficos por Graham y Chung, como un paso intermedio, esto es:

$$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{**}$$

No puedo entender cómo $(*)$ implica $(**)$. Por favor alguien puede explicar esto?

Answer 1

De hecho, la desigualdad de $(**)$ debería ser al revés.

Como Austin Mohr señaló, Stirling, la fórmula es muy útil aquí. La forma que voy a utilizar es $$n! \sim \biggl(\dfrac{n}{e}\biggr)^n \sqrt{2\pi n}. \tag{*}$$ También, supongo que $m \to \infty$ y $m - n \to \infty$.

Empezamos por observar que la desigualdad de $(**)$ es equivalente a $$\dbinom{m}{n} < 2^{\binom{n}{2} - 1}. \tag{**}$$ Desde $$\dbinom{m}{n} \geq \dfrac{(m - n)^n}{n!},$$ hemos de $(**)$ que $$(m - n)^n < n! 2^{\binom{n}{2} - 1}.$$ Conectar la fórmula de Stirling $(*)$, tenemos $$m^n \biggl(1 - \dfrac{n}{m}\biggr)^n < \biggl(\dfrac{n}{e}\biggr)^n \sqrt{\dfrac{\pi n}{2}} 2^{\binom{n}{2}}.$$ Tomando $n$th raíces, obtenemos $$m \biggl(1 - \dfrac{n}{m}\biggr) < \dfrac{n}{e} 2^{\frac{n - 1}{2}} \biggl(\dfrac{\pi n}{2}\biggr)^{1/2n}.$$ Finalmente, la observación de que $(\frac{\pi n}{2})^{1/2n} / (1 - \frac{n}{m}) \to 1$ $m$, $n \to \infty$, terminamos con $$m < \dfrac{1}{e\sqrt{2}} n 2^{n/2},$$ como se desee.