Conectividad del gráfico aleatorio Erdős – Rényi

Question

Es bien sabido que si $\omega=\omega(n)$ es cualquier función tal que $\omega \to \infty$ as $n \to \infty$, y si $p \ge (\log{n}+\omega) / n$, entonces la Erdős–Rényi azar gráfico de $G(n,p)$ es asintóticamente casi seguramente conectado. La forma en que sé cómo probar que esto es (1) en primer lugar contar el número esperado de los componentes de la orden de $2, 3, \dots, \lfloor n/2 \rfloor$, y viendo que el número esperado tiende a cero. Entonces (2) muestra el número esperado de aislado de los vértices es también tiende a cero.

Este enfoque también permite obtener unos resultados más precisos, tales como: si $p = (\log{n}+c) / n$ con $c \in \mathbb{R}$ constante, entonces Pr$[G(n,p)$ está conectado] $\to e^{-e^{-c}}$ as $n \to \infty$, que sigue una vez que sabemos que en este régimen el número de vértices aislados se aproxima a una distribución de Poisson con una media de $e^{-c}$.

Me pregunto si es posible dar más fáciles de la prueba (de un resultado más rústico) a lo largo de la siguientes líneas. Hay $n^{n-2}$ árboles de expansión en el gráfico completo, y $G$ está conectado si y sólo si uno de estos árboles aparece. Por lo que el espera que el número de árboles de expansión es $n^{n-2}p^{n-1}$. Uno podría esperar que, si este la función está creciendo lo suficientemente rápido, a continuación, con alta probabilidad de $G(n,p)$ está conectado.

Creo recordar haber leído que este enfoque no funciona --- por ejemplo, la varianza es demasiado grande para aplicar la desigualdad de Chebyshev. Lo que me pregunto es si hay alguna manera de arreglar esto si estamos dispuestos a realizar, $p$ un poco más grande. En particular, ¿qué acerca de la $p = C \log{n} / n$ para algunos lo suficientemente grande como constante $C > 1$, o incluso el $p = n^{-1 + \epsilon}$ para la renta fija, pero arbitrariamente pequeño $\epsilon >0$?

Answer 1

Una buena pregunta. He aquí una estrategia que se me ocurre, a pesar de que podría fallar miserablemente.

El problema de fondo parece ser que lo que usted dijo acerca de la varianza: la apariencia de los diferentes árboles de expansión están muy lejos de ser independiente, ya que es posible hacer modificaciones locales a un árbol de expansión y conseguir otro. (Por ejemplo, si x es una hoja se unió a la y, que es sólo sumó a la z, entonces podemos reemplazar la ruta de acceso zyx por el camino zxy.)

Una manera podríamos intentar derrotar este es elegir un conjunto aleatorio $\Sigma$ de los árboles de expansión, donde cada árbol de expansión es elegido de forma independiente con una probabilidad de $\alpha^{n-1}$ para algunos elegidos cuidadosamente $\alpha$ (que me imagino como una pequeña potencia negativa de $n$). A continuación, el número esperado de árboles de $\Sigma$ en $p$-aleatorio gráfico es $(\alpha p)^{n-1}n^{n-2}$, que es bastante grande, incluso cuando $p$ está muy cerca de la $n^{-1}$. Pero ahora se podría esperar que cualquiera de los dos árboles en $\Sigma$ están bastante bien separados, así que tal vez es posible obtener un buen estimado de la varianza.

En realidad, no es claro para mí lo que pasa a la aleatorios realmente logra aquí: tal vez el método más sencillo (pero no totalmente simple) es calcular el número esperado de pares de árboles de expansión por medio de una cuidadosa clasificación de lo que puede parecer. La esperanza sería que si tienes que elegir un árbol al azar, entonces la proporción de árboles que se superponen con las que en gran medida es por lo general tan pequeña que el número esperado de pares no es significativamente más grande que el cuadrado del número esperado de árboles de expansión. Con $p=n^{-1+\epsilon}$ algo como esto podría funcionar, pero es probable que ya hayas pensado en esto.

Answer 2

Aquí es una sencilla prueba para $C>2$, y de una manera bastante fácil la prueba de $C>1$.

Definir un corte de un gráfico de $G$ a ser una partición de los vértices de $G$ en dos sets en los que se cruzan sin bordes. Así que una gráfica tiene un trivial de corte, si y sólo si está desconectado. Vamos a mostrar que el número esperado de cortes de $G$ va a las $0$, por lo que, con una probabilidad de $1$, el gráfico está conectado.

Para cualquier partición de los vértices de $G$ en dos conjuntos, de tamaño $k$ e $n-k$, la probabilidad de que esta partición es un corte es $(1-p)^{k(n-k)} \binom{n}{k}$. Por lo que el número esperado de recortes es $$\sum_{k=1}^{n/2} (1-p)^{k(n-k)} \binom{n}{k}.$$ Sólo tenemos que ir hasta la mitad del camino, porque siempre podemos tomar $k$ a ser el menor de la mitad de la corte. (Voy a ser descuidado y escribir no entero de los límites para mi sumatorias, como he hecho aquí. Usted puede arreglar, si así lo desea).

Para $C>2$, tenemos los siguientes crudo obligado $$\sum_{k=1}^{n/2} (1-p)^{k(n-k)} \binom{n}{k} \leq \sum_{k=1}^{n/2} e^{-p k(n-k)} n^k.$$

El $\log$ de los sumando es $$-k (n-k) \frac{C \log n}{n} + k \log n = k \log n \left( 1-C(1-k/n) \right) \leq k \log n (1-C/2)$$

Por lo tanto, si $C>2$, nos están delimitadas por $\sum_{k=1}^{n/2} e^{(1-C/2) k \log n}$. Esta es una serie geométrica, cuya suma es fácilmente visto a estar acotada por una constante de varios de sus líderes plazo; es decir $n^{(1-C/2)}$. Por lo que la suma va a $0$ y hemos terminado.

---

Ahora, ¿qué pasa si $C>1$, pero no tan grande como el $2$? Deje $a$ ser un número real tal que $1-C(1-a) < 0$. El anterior argumento muestra que la contribución de los términos con $k<an$ es insignificante. (Si $C\leq 1$, no existe tal número, y esta prueba se rompe.)

Consideremos ahora el resto de los términos, y el uso de diferentes crudo obligado: $$\sum_{k=an}^{n/2} (1-p)^{k(n-k)} \binom{n}{k} \leq \sum_{k=an}^{n/2} e^{-pk(n-k)} 2^n$$

De nuevo, el registro de los sumando es $$-k(n-k) \frac{C \log n}{n} + n \log 2 = -(k/n) (1-k/n) C n \log n + n \log 2 \leq - a (1-a) C n \log n + n \log 2$$ Este es el registro de un individuo sumando; tenemos que agregar para arriba $(1/2 -a) n < n$ de ellos. Por lo que la suma es delimitada por $$n e^{-a(1-a) C n \log n + n \log 2} =e^{-a(1-a) C n \log n + n (\log 2+1)}.$$

El $n \log n$ supera el $n$, por lo que estamos por hacer.

Answer 3

Estimado Mateo, esto no es realmente una respuesta a su pregunta, pero sólo un asunto relacionado. Como usted señala, la previsión del número de árboles en un azar gráfico 1 ya cuando p=c/n y es muy grande cuando p=logn/n por lo que la esperanza es que esto puede ser usado para mostrar que con una gran probabilidad de que el azar gráfico contiene un árbol. Hay una colección de conjeturado por Jeff Kahn y yo tratando de sugerir un general de conexión de este tipo. Estas conjeturas se presentan en el pape de los Umbrales y la expectativa de los umbrales por Kahn y a mí, y se mencionan en este MO pregunta. Si es cierto, estas conjeturas se implica que el umbral para la conectividad será inferior a logn/n (claro que no se necesita para este caso...), y la prueba será probablemente en el mejor ser mucho más complicado que existían pruebas.

Debo mencionar que el fuerte umbral de la propiedad que fue demostrado por Erdos y Renyi para la conectividad puede ser demostrado (con más dura de las pruebas) a partir de principios más generales: Uno es el Margulis-Talagrand teorema que se aplica el umbral en el que el azar subdiagramas de muy borde conectado gráficos y uno es Friedgut del resultado que identificar propiedades de gráfico con el grueso de los umbrales.

Answer 4

Creo que tal vez el problema con la varianza no es la superposición de las diferentes árboles, pero el hecho de que el número de árboles de expansión puede ser mucho mayor que 1, pero no mucho menos.

Con $p=\frac{c}{n}$ el número esperado de la distribución de los árboles de hecho, puede crecer de manera exponencial (aunque tal vez no tan rápido como $\frac{c^{n-1}}{2n}$ ), mientras que la probabilidad de estar conectado va exponencialmente a $0$.

Tal vez con $p=\frac{\log n-\log \log n}{n}$ la oportunidad de estar conectados disminuye como $e^{-n}$, pero el número de árboles de expansión de la única gran componente crece algo como $(\log n)^{n}$. A continuación, las raras ocasiones en que el gigante componente es el conjunto de la gráfica (es decir, la gráfica está conectado) podría hacer que el número esperado de árboles de expansión crecer algo como $(\frac{\log n}{e})^n$ que es superexponential.