Derivación de ruedas en la expresión que implique coeficiente binomial de Erdős y Rényi 1959

Question

Estoy en el proceso de trabajo a través de Erdős y Rényi de 1959 artículo "Sobre Grafos Aleatorios yo". En la prueba de la primera Lema, la ecuación 14 da un salto en una expresión con varios coeficientes binomiales:

$$\binom{n}{s}\frac{\binom{\binom{n}{2}-s(n-s)}{N_c}}{\binom{\binom{n}{2}}{N_c}} \le \frac{e^{(3-2c)s}}{s!}$$

donde $N_c = [\frac{1}{2}n\log{n} + c n]$, $s\le n/2$ y $n > n_0$ algunos $n_0$, e $[x]$ denota el mayor entero menor o igual a $x$. (Ecuación 15 da una expresión correspondiente para el caso de $s \ge n/2$.)

Después de pasar algún tiempo jugando con Stirling aproximación y límites como $\left(\frac{n}{k}\right)^k \le \binom{n}{k} \le \frac{n^k}{k!} \le \left(\frac{n \cdot e}{k}\right)^k$, no me siento que estoy más cerca de entender donde esta obligado viene.

Parece que debería ser bastante sencillo procedimiento para la obtención de tales límites, dado que los autores no siento la necesidad de elaborar. Yo estaría muy agradecido por cualquier consejos sobre cómo proceder!

Answer 1

Si $s$ no es demasiado grande, la desigualdad es correcta. Esto es debido a que el cociente de los coeficientes binomiales es $$ \prod_{0\le i<N_c} \frac{{n\elegir 2}-s(n-s)-i}{{n\elegir 2}-i} = \prod_{0\le i<N_c} \left(1-\frac{s(n-s)}{{n\elegir 2}-i}\right) \le \exp -\frac{2s(n-s)}{n^2} N_c, $$ por lo que es suficiente para tener $$ n^s \exp -\frac{2s(n-s)}{n^2} N_c \le e^{(3-2c)s}, $$ o, tomando logaritmos, $$ - \frac{2s(n-s)}{n^2} N_c +s\log n\le (3-2c)s. $$ Ahora, $N_c=\frac{1}{2}n\log n+cn-\theta$, para algunas de las $0\le\theta<1$, y la inserción de esta en esta última desigualdad se cancela los términos de $s\log n$$-2cs$, dejando $$ \frac{2s(n-s)}{n^2}\theta +\frac{2s^2}{n^2}(\frac{1}{2}n\log n+cn)\le 3s, $$ lo cual es cierto si se requiere que el $s\le n/\log n$ y $n$ ser lo suficientemente grande.

Si $s=\Omega(n)$, la desigualdad no se puede sostener. Set $s:=\lfloor n\delta \rfloor$, fix$\delta\in(0,\frac{1}{2}]$$c$, y deje $n$ llegan a ser grandes. Mira los logaritmos de cada lado. El cociente de los coeficientes binomiales en el lado izquierdo va a dar $$N_c \log(1-s(n-s){n\choose 2}^{-1})+O((\log n)^2)=\frac{1}{2}(n\log n) \log(1-2\delta(1-\delta)) + O(n),$$ while $\registro {n\elegir s}=O(n)$. On the right-hand side, the logarithm of $1/s!$ is $-\delta n \log n + O(n)$, and $\log e^{(3-2c)s}$ is $O(n)$. Por lo tanto, si la desigualdad fuera cierto, tendríamos $$ \frac{1}{2}( n\log n) \log(1-2\delta(1-\delta))+O(n)\le -\delta n\log n+O(n), $$ pero desde $\frac{1}{2}\log (1-2\delta(1-\delta))>-\delta$ todos los $\delta$$(0,\frac{1}{2}]$, esto es falso, por lo suficientemente grande como $n$.

El fracaso de la desigualdad de la gran $s$ no es un problema para el Erdős-Rényi de papel. Esto es debido a que el uso de esta desigualdad (numeradas (14) en el papel) es obligada la suma del lado izquierdo de (14) como $s$ varía entre algunos de límite inferior y $n/2$. Sin embargo, el cociente de los coeficientes binomiales está disminuyendo en la $0\le s\le n/2$, por lo que si establecemos $s_0:=n/\log n$ y suma el lado izquierdo de (14)$s_0\le s\le n/2$, el resultado no será más de $$ 2^n \left.\binom{\binom{n}{2}-\lceil s_0\rceil(n-\lceil s_0\rceil)}{N_c}\right/\binom{\binom{n}{2}}{N_c} \le 2^n \exp -\frac{2s_0(n-s_0)}{n^2} N_c, $$ y tomando el logaritmo de la mano derecha da $$ n\log 2 - \frac{2s_0(n-s_0)}{n^2} (\frac{1}{2}n\log n+cn-\theta). $$ Sin embargo, si fijamos $c$, esto es $-n(1-\log 2)+O(n/\log n)$, que se aproxima $-\infty$ $n$ se hace más grande. Por lo tanto, el lado derecho de la desigualdad (13) en el papel puede ser dividida en cuatro piezas: (1) $M<s<n/\log n$, (2) $n/\log n\le s\le n/2$, (3) $n/2< s\le n-(n/\log n)$, y (4) $n-(n/\log n)<s<n-2N_c/n$. Piezas (1) y (4) puede ser demostrado ser pequeño por (14) y (15), (2) es pequeño por la estimación inmediatamente anterior, y (3) también puede ser demostrado ser pequeño por el cálculo anterior como la suma del lado izquierdo de (14) no cambia al $s$ es reemplazado por $n-s$.