Estoy tratando de hacer mi camino a través de Bollobás "libro" Modelos de Grafos Aleatorios', y por desgracia he llegado completamente despegados en uno de sus típicos 2-línea "y, por supuesto, esto es totalmente trivial"al estilo de las pruebas. A pesar de pasar muchas horas mirando en vano, he progresado precisamente la nada y estaba esperando que alguien podría explicar lo que está pasando a mí con tanto detalle como los que pueden invocar la energía para dar, para que yo pudiera terminar de comprender. El libro del teorema (Teorema 2.2) es de alrededor de conmutación entre el $\mathcal{G}(n,p)$ $\mathcal{G}(n,m)$ modelos de grafos aleatorios, y va como sigue:
Teorema: (i) Vamos Q ser cualquier gráfico de la propiedad y supongamos $pqN \to \infty$ (donde tenemos $n$ vértices y $N={n \choose 2}$ posible de los bordes). A continuación, los 2 siguientes afirmaciones son equivalentes (mis comentarios en cursiva):
a) Casi cada gráfico en $\mathcal{G}(n,p)$ P. (Aquí $\mathcal{G}(n,p)$ representa la probabilidad en el espacio de grafos aleatorios en $n$ vértices con bordes distribuidos al azar con una probabilidad de $p$, es decir, de borde número binomial distribuidas $\operatorname{Bin} (N,p)$)
b) Dada la $x>0$ $\epsilon > 0$ si $n$ es lo suficientemente grande, hay $l \geq (1- \epsilon) 2x(pqN)^{1/2}$ enteros $M_1,\ldots,\,M_l$ $pN-x(pqN)^{1/2}<M_1<M_2<\ldots < M_l<pN + x(pqN)^{1/2}$ tal que $P_{M_i}(Q)>1-\epsilon$ por cada $1 \leq i \leq l$.
Prueba: (i) Por De Moivre-Laplace teorema, para todos los fijos $x > 0$, $\mathbb{P}_p(|e(G)-pN|<x(pqN)^{-1/2})\sim \Phi(x) - \Phi(-x).$ Ya que también se $\mathbb{P}_p(e(G)=M) = b(M;N,p) < (pqN)^{-1/2}$ para cada M, la equivalencia de la siguiente manera.
Así, por dónde empezar. Con respecto a lo que él hizo decir, creo que la declaración de $\Phi$ que obtenemos de De Moivre-Laplace teorema; estoy feliz con eso. No puedo sin embargo por qué probabilty declarado es $< (pqN)^{1/2}$ - puedo creer que sea verdad, pero no veo la manera más obvia para demostrarlo.
Con respecto a la prueba de (i) como un todo: supongo que la idea intuitiva de esta parte del teorema es ser capaz de decir 'Esta propiedad contiene el fib tiene para un montón de gráficos cerca de la media del número de bordes', es decir, podemos centrarnos en el comportamiento cerca de la media. Entonces, hacemos lo que es obvio y aproximar por una distribución normal, y desde entonces se puede decir muchas cosas buenas en términos del número de desviaciones lejos de la media'. Tristemente, ni siquiera puedo averiguar en qué dirección está tratando de lidiar con su prueba, vamos solo rellenar los huecos. Sabemos más o menos cómo es probable estamos a la tierra dentro de las $x(Npq)^{1/2}$ de la media, y sabemos que una cota superior para la probabilidad de contraer $M$ bordes: es que realmente suficiente para decir "resultado de la siguiente manera"?
Así que creo que eso es todo - lo siento por la considerable longitud de esta pregunta, si hay algo que creo que le puede quitar por razones de brevedad, a continuación, voy a ser feliz. Como en el anterior, me he pasado horas y horas y no llegar a ninguna parte con lo que debiera ser un bastante sencillo teorema de aquí, el material es nuevo para mí, así que tal vez por eso, pero lo que me gustaría ser extremadamente agradecidos, es un muy completo (y bastante básico si es posible) la explicación de lo que está pasando aquí, lo que me falta en la prueba y por qué es cierto. Las más sinceras gracias por su ayuda de antemano.
(Edit: se ha quitado la segunda mitad del teorema debido a malentendidos)
