Soy muy nuevo en la teoría de grafos y estoy atascado en el concepto de umbrales para el modelo aleatorio de Erdos-Renyi. En concreto, me gustaría calcular el umbral de aparición de triángulos y el umbral de aparición de componentes con tres aristas. Sé que el primero es 1/n porque lo he leído en todas partes en Internet. No encuentro ninguna explicación clara para ese resultado. No sé si debo utilizar la desigualdad de Markov o la de Chebyshev, o ninguna de las dos. Siento molestar aquí, pero estoy muy confundido.
Respuesta
¿Demasiados anuncios?
Hay dos pasos: demostrar que el umbral no es demasiado bajo y demostrar que no es demasiado alto.
Cuando $p$ está por debajo del umbral
Si pensamos que el umbral de los triángulos es $\frac1n$ nuestro primer paso debería ser demostrar que cuando $p \ll \frac1n$ entonces, con la condición de que no haya triángulos en $G_{n,p}$ . Esto se hace utilizando la desigualdad de Markov.
Dejemos que $X$ sea el número de triángulos en $G_{n,p}$ . Podemos escribir $X$ como la suma de las variables indicadoras $X_{\{i,j,k\}}$ , donde $X_{\{i,j,k\}}=1$ si los vértices $i,j,k$ forman un triángulo y $X_{\{i,j,k\}}=0$ de lo contrario. Dado que $\Pr[X_{\{i,j,k\}}=1] = p^3$ (las tres aristas deben estar presentes), tenemos $\mathbb E[X_{\{i,j,k\}}] = p^3$ también. Hay $\binom n3$ opciones de $\{i,j,k\}$ Así que $X$ es la suma de $\binom n3$ variables con valor esperado $p^3$ . Por linealidad de la expectativa, $\mathbb E[X] = \binom n3 p^3$ .
Si $p \ll \frac1n$ entonces $n^3 p^3 \to 0$ como $n \to \infty$ Así que $\mathbb E[X] \to 0$ como $n \to \infty$ y por tanto (por la desigualdad de Markov) $\Pr[X \ge 1] \to 0$ como $n \to \infty$ . Esto significa que, con alta probabilidad, no hay triángulos.
Cuando $p$ está por encima del umbral
Si $p \gg \frac1n$ entonces el mismo argumento dice que $\mathbb E[X] \to \infty$ como $n \to \infty$ lo que significa que el número medio de triángulos es grande, pero eso no significa que el número de triángulos sea grande por término medio. Podríamos imaginar una variable aleatoria $Y$ con $\Pr[Y=n^2] = \frac1n$ y $\Pr[Y=0] =1 - \frac1n$ Entonces $\mathbb E[Y] \to \infty$ como $n \to \infty$ y sin embargo $Y=0$ con alta probabilidad.
Para evitarlo, debemos utilizar el método del segundo momento. Su forma más sencilla es la desigualdad $$\Pr[X \ne 0] \ge \frac{\mathbb E[X]^2}{\mathbb E[X^2]}.$$ (Esta es la desigualdad de Cauchy-Schwarz con respecto al producto interior $\langle X,Y\rangle = \mathbb E[XY]$ aplicada a $X$ y la variable aleatoria $Y$ que es $1$ cuando $X \ne 0$ y $0$ en caso contrario). La igualdad de Chebyshev también funcionaría, y los cálculos serían muy similares.
Ya hemos calculado $\mathbb E[X]$ para los triángulos, por lo que sabemos $\mathbb E[X]^2$ . Para calcular $\mathbb E[X^2]$ cuadrar nuestra suma anterior: $$ X^2 = \left(\sum_{\text{triples }\{i,j,k\}} X_{\{i,j,k\}}\right)^2 = \sum_{\text{triples }\{a,b,c\}} \sum_{\text{triples }\{d,e,f\}} X_{\{a,b,c\}} X_{\{d,e,f\}}. $$ Podemos sustituir $X_{\{a,b,c\}} X_{\{d,e,f\}}$ por $\mathbb E[X_{\{a,b,c\}} X_{\{d,e,f\}}]$ para encontrar $\mathbb E[X^2]$ .
La mayor contribución a esta suma proviene, con mucho, de los términos $\mathbb E[X_{\{a,b,c\}} X_{\{d,e,f\}}]$ donde $\{a,b,c\} \cap \{d,e,f\} = \varnothing$ . Hay $\binom n3 \binom{n-3}{3}$ dichos términos, y $\mathbb E[X_{\{a,b,c\}} X_{\{d,e,f\}}] = p^6$ , por lo que obtenemos $\binom n3 \binom{n-3}{3} p^6 = (1- o(1)) \binom n3^2 p^6 = (1- o(1)) \mathbb E[X]^2$ .
Cuando $p \gg \frac1n$ Otros términos contribuyen mucho menos:
- Cuando $|\{a,b,c\} \cap \{d,e,f\}| = 1$ Sólo hay $O(n^5)$ tales pares de triples, pero siguen teniendo una probabilidad de $p^6$ de ocurrir: los dos triángulos forman un gráfico de mariposas con $6$ bordes. Así que la contribución total es $O(n^5 p^6) = o(\mathbb E[X^2])$ .
- Cuando $|\{a,b,c\} \cap \{d,e,f\}| = 2$ Hay $O(n^4)$ tales pares de triples y tienen una probabilidad de $p^5$ de ocurrir: los dos triángulos forman un gráfico de diamante con $5$ bordes. Así que la contribución total es $O(n^4 p^5) = o(\mathbb E[X^2])$ (porque $np \to \infty$ ).
- Cuando $|\{a,b,c\} \cap \{d,e,f\}| = 3$ o en otras palabras $\{a,b,c\} = \{d,e,f\}$ Hay $\binom n3$ tales pares de triples y tienen una probabilidad de $p^3$ de ocurrir, por lo que la contribución total es $O(n^3 p^3) = o(\mathbb E[X^2])$ .
Esto nos dice que $$\Pr[X \ne 0] \ge \frac{\binom n3^2 p^6}{\binom n3 \binom{n-3}{3} p^6 + o(n^6p^6)} = 1 - o(1)$$ y por lo tanto $X \ne 0$ con alta probabilidad.
Otros casos
La clave para aplicar este método a los umbrales de los subgráficos es pensar en las formas en que dos copias del subgráfico pueden intersecarse. En el caso de los triángulos, todas las intersecciones terminaron siendo menos frecuentes que los casos con dos triángulos disjuntos. Aplicar el método del segundo momento no funciona (y el umbral que obtenemos con el método del primer momento podría incluso no ser correcto) en los casos en los que algunas intersecciones aparecen con mayor frecuencia.
Esto suele ocurrir si el gráfico que estamos viendo tiene un subgrafo más denso que el gráfico original. Por ejemplo, consideremos el $(4,1)$ -Gráfico de la piruleta . Aquí, el método del primer momento nos dice que este gráfico no aparece cuando $p \ll n^{-5/7}$ pero en realidad la copia de $K_4$ dentro de este gráfico es más limitante: el umbral de $K_4$ es $n^{-2/3}$ que es mayor. Para el grafo de la piruleta, el método del segundo momento fallaría cuando consideramos pares de piruletas que comparten sus copias de $K_4$ .
