Umbrales para conjuntos contagiosos en grafos aleatorios

Información Básica

• ID del artículo: 1611.10167
• Título: Thresholds for contagious sets in random graphs
• Autores: Omer Angel, Brett Kolesnik
• Clasificación: math.PR (Teoría de Probabilidades), math.CO (Matemática Combinatoria)
• Fecha de publicación: 30 de noviembre de 2016 (envío a arXiv)
• Enlace del artículo: https://arxiv.org/abs/1611.10167

Resumen

Este artículo estudia el proceso de percolación bootstrap con umbral $r$ en grafos aleatorios de Erdős-Rényi $G_{n,p}$. Para un $r \geq 2$ fijo, los autores identifican con precisión el umbral de la probabilidad de arista $p$, más allá del cual existe con alta probabilidad un conjunto de tamaño $r$ que puede infectar el grafo completo. Este resultado mejora el trabajo de Feige, Krivelevich y Reichman, elevando el umbral desde cotas a nivel de constante multiplicativa hasta resultados asintóticamente exactos. Como aplicación, los autores también obtienen cotas superiores para el umbral de percolación bootstrap $K_4$, y conjeturan que esta cota es asintóticamente óptima. Estos umbrales están estrechamente relacionados con la probabilidad de supervivencia de ciertos procesos de ramificación dependientes del tiempo, para los cuales los autores derivan fórmulas asintóticas.

Contexto de investigación y motivación

Problema de investigación

La percolación bootstrap es un proceso de propagación dinámica: dado un grafo $G=(V,E)$ y un conjunto inicial infectado $V_0 \subset V$, en cada paso temporal, cualquier vértice con al menos $r$ vecinos infectados también se infecta y permanece infectado. Las preguntas centrales son:

1. Problema del umbral de susceptibilidad: ¿Cuán grande debe ser la probabilidad de arista $p$ en el grafo aleatorio $G_{n,p}$ para garantizar con alta probabilidad la existencia de un conjunto de tamaño $r$ (conjunto mínimo contagioso) que pueda infectar el grafo completo?
2. Percolación bootstrap de grafos: ¿Cuál es el umbral para la percolación bootstrap $K_4$ (una regla de adición de aristas)?

Importancia del problema

• Significado teórico: La percolación bootstrap es un modelo importante en física estadística, ciencia de la computación, redes neuronales y sociología, utilizado para estudiar sistemas magnéticos desordenados, propagación de información, difusión de opiniones y otros fenómenos
• Desafío matemático: La percolación bootstrap en grafos aleatorios implica estructuras de dependencia complejas, y la determinación de umbrales exactos requiere técnicas profundas de combinatoria y teoría de probabilidades
• Fenómeno de transición de fase: Este problema exhibe un comportamiento claro de transición de fase—cerca del umbral crítico, el sistema cambia abruptamente de "casi imposible infectar globalmente" a "alta probabilidad de infección global"

Limitaciones de métodos existentes

Feige, Krivelevich y Reichman 24 proporcionaron cotas superior e inferior para el umbral de susceptibilidad, pero solo con precisión hasta constantes multiplicativas. Específicamente, no pudieron determinar el factor de constante exacto $\alpha_r$. La principal contribución de este artículo es identificar esta constante exacta.

Motivación de la investigación

Los autores descubren que el umbral de susceptibilidad está estrechamente relacionado con la probabilidad de supervivencia de una clase de procesos de ramificación no homogéneos. Al establecer esta conexión y analizar con precisión el proceso de ramificación, se pueden obtener expresiones asintóticas exactas para el umbral.

Contribuciones principales

1. Identificación del umbral exacto (Teorema 1.1): Para la percolación bootstrap $r$, se demuestra que la probabilidad de arista crítica es $p_c(n,r) = \left(\frac{\alpha_r}{n\log^{r-1}n}\right)^{1/r}(1+o(1))$ donde $\alpha_r = (r-1)!\left(\frac{r-1}{r}\right)^{2(r-1)}$
2. Cota superior para percolación bootstrap $K_4$ (Teorema 1.2): Se demuestra que $p_c(n,K_4) \leq \frac{1+o(1)}{\sqrt{3n\log n}}$ y se conjetura que esta cota es asintóticamente óptima
3. Umbral de arista semilla (Teorema 1.4): Para $p=\sqrt{\alpha/(n\log n)}$, se demuestra que cuando $\alpha > 1/3$, $G_{n,p}$ contiene con alta probabilidad una arista semilla (seed edge)
4. Probabilidad de supervivencia del proceso de ramificación (Teorema 1.5): Para el proceso de ramificación no homogéneo relacionado, se deriva la fórmula asintótica de la probabilidad de supervivencia $P(X_t > 0, \forall t) = \exp\left[-\frac{(r-1)^2}{r}k_r(1+o(1))\right]$ donde $k_r = \left(\frac{(r-1)!}{\varepsilon}\right)^{1/(r-1)}$
5. Innovación metodológica: Se introduce el concepto de "grafos susceptibles libres de triángulos" (triangle-free susceptible graphs), mediante la restricción a esta clase especial de grafos se establece la independencia aproximada de conjuntos contagiosos, haciendo viable el método del segundo momento

Explicación detallada de métodos

Definición de tareas

Percolación bootstrap $r$:

• Entrada: Grafo $G=(V,E)$, conjunto inicial infectado $V_0 \subset V$, umbral $r$
• Regla de evolución: $V_{t+1} = V_t \cup \{v : |N(v) \cap V_t| \geq r\}$
• Salida: Conjunto final infectado $V_\infty = \langle V_0, G \rangle_r$

Conjunto contagioso: Se dice que $I$ es un conjunto contagioso de $G$ si $\langle I, G \rangle_r = V$

Susceptibilidad: Se dice que un grafo $G$ es susceptible o $r$-permeable si contiene un conjunto contagioso de tamaño $r$ (conjunto mínimo contagioso)

Probabilidad crítica: $p_c(n,r) = \inf\{p > 0 : P(G_{n,p}\text{ es susceptible}) \geq 1/2\}$

Arquitectura general

La demostración del artículo se divide en dos partes principales:

1. Demostración de cota inferior (Sección 2): Demostración de no susceptibilidad cuando $\alpha < \alpha_r$

Idea central: Usar el método del primer momento (first moment method) para demostrar que cuando $p$ es pequeño, cualquier conjunto de tamaño $r$ solo puede infectar $O(\log n)$ vértices.

Pasos clave:

• Establecer relaciones de recurrencia para calcular el número de grafos mínimos susceptibles $m_r(k,i)$ (tamaño $k$, con $i$ vértices en la capa superior)
• Derivar cotas superiores para la cantidad normalizada $\sigma_r(k,i)$ (Lema 2.5)
• Definir el parámetro crítico $\beta^*(\alpha)$, que es la única raíz positiva de la ecuación: $r + \beta\log\left(\frac{\alpha\beta^{r-1}}{(r-1)!}\right) - \frac{\alpha\beta^r}{r!} - \beta(r-2) = 0$
• Demostrar que cuando $\alpha < \alpha_r$, cualquier $r$-percolación crece como máximo a $(\beta^*(\alpha)+\delta)\log n$ vértices (Proposición 2.1)

2. Demostración de cota superior (Sección 3): Demostración de susceptibilidad cuando $\alpha > \alpha_r$

Idea central: Usar el método del segundo momento para demostrar la existencia de conjuntos contagiosos. El desafío principal es la dependencia entre conjuntos contagiosos.

Estrategia innovadora:

• Introducir percolación $\hat{r}$: Restringirse a subgrafos susceptibles libres de triángulos, definir el proceso de percolación $\hat{r}$
• Independencia aproximada (Lema 3.12): Utilizar el teorema de Mantel (la densidad de aristas en grafos libres de triángulos es como máximo 1/2) para demostrar que diferentes percolaciones $\hat{r}$ son aproximadamente independientes
• Estimación de cota inferior: Demostrar que el número de grafos susceptibles libres de triángulos es asintóticamente igual al número de grafos susceptibles generales (Lema 3.5)
• Crecimiento supercrítico: Demostrar que las percolaciones que superan el tamaño crítico $\beta_r(\alpha)\log n$ continúan creciendo a escala lineal

Detalles técnicos

Relación de recurrencia (Ecuación 2.1)

Para el número de grafos mínimos susceptibles: $m_r(k,i) = \binom{k-r}{i}\sum_{j=1}^{k-r-i} a_r(k-i,j)^i m_r(k-i,j)$ donde $a_r(x,y) = \binom{x}{r} - \binom{x-y}{r}$ representa el número de formas en que los vértices de la capa superior pueden conectarse.

Transformación normalizada (Ecuación 2.3)

Se define $\sigma_r(k,i) = \frac{m_r(k,i)}{(k-r)!}\left(\frac{(r-1)!}{k^{r-1}}\right)^k$ lo que hace que la relación de recurrencia sea amigable para análisis espectral.

Recurrencia de grafos libres de triángulos (Ecuación 3.1)

$\hat{m}_r(k,i) \geq \binom{k-r}{i}\sum_{j=1}^{k-r-i} \hat{a}_r(k-i,j)^i \hat{m}_r(k-i,j)$ donde $\hat{a}_r(x,y) = \max\{0, a_r(x,y) - 2ryx^{r-2}\}$ el término restado corresponde a formas de conexión que podrían crear triángulos.

Independencia aproximada (Lema 3.12)

Para conjuntos disjuntos de tamaño $r$, $I \neq I'$, si $|I \cap I'| = m$: