Seuils pour les ensembles contagieux dans les graphes aléatoires

Informations de base

• ID de l'article: 1611.10167
• Titre: Thresholds for contagious sets in random graphs
• Auteurs: Omer Angel, Brett Kolesnik
• Classification: math.PR (Théorie des probabilités), math.CO (Mathématiques combinatoires)
• Date de publication: 30 novembre 2016 (soumis à arXiv)
• Lien de l'article: https://arxiv.org/abs/1611.10167

Résumé

Cet article étudie le processus de percolation bootstrap avec seuil $r$ sur le graphe aléatoire d'Erdős-Rényi $G_{n,p}$. Pour un $r \geq 2$ fixé, les auteurs identifient précisément le seuil de la probabilité d'arête $p$ au-delà duquel existe, avec haute probabilité, un ensemble de taille $r$ capable d'infecter le graphe entier. Ce résultat améliore les travaux de Feige, Krivelevich et Reichman, en passant d'une borne à facteur constant multiplicatif à un résultat asymptotiquement exact. En application, les auteurs obtiennent également une borne supérieure pour le seuil de percolation bootstrap $K_4$, et conjecturent que cette borne est asymptotiquement optimale. Ces seuils sont étroitement liés à la probabilité de survie de certains processus de branchement non-homogènes, pour lesquels les auteurs déduisent des formules asymptotiques.

Contexte et motivation de la recherche

Problèmes de recherche

La percolation bootstrap est un processus de propagation dynamique : étant donné un graphe $G=(V,E)$ et un ensemble initial infecté $V_0 \subset V$, à chaque pas de temps, tout sommet ayant au moins $r$ voisins infectés devient infecté et le reste. Les questions centrales sont :

1. Problème du seuil de susceptibilité: Dans le graphe aléatoire $G_{n,p}$, quelle doit être la probabilité d'arête $p$ pour garantir avec haute probabilité l'existence d'un ensemble de taille $r$ (ensemble infectieux minimal) capable d'infecter le graphe entier ?
2. Percolation bootstrap de graphe: Pour la percolation bootstrap $K_4$ (une règle d'ajout d'arêtes), quel est le seuil ?

Importance du problème

• Signification théorique: La percolation bootstrap est un modèle important en physique statistique, informatique, réseaux de neurones et sociologie, utilisé pour étudier les systèmes magnétiques désordonnés, la propagation d'information, la diffusion d'opinions, etc.
• Défi mathématique: La percolation bootstrap sur graphes aléatoires implique des structures de dépendance complexes, et la détermination des seuils exacts nécessite des techniques sophistiquées en combinatoire et théorie des probabilités
• Phénomène de transition de phase: Ce problème exhibe un comportement de transition de phase clair — près du seuil critique, le système passe brutalement d'« infection globale presque impossible » à « infection globale avec haute probabilité »

Limitations des méthodes existantes

Feige, Krivelevich et Reichman 24 ont fourni des bornes supérieure et inférieure pour le seuil de susceptibilité, mais seulement à un facteur constant multiplicatif près. Spécifiquement, ils n'ont pas pu déterminer le facteur constant précis $\alpha_r$. La contribution principale de cet article est d'identifier cette constante précise.

Motivation de la recherche

Les auteurs découvrent que le seuil de susceptibilité est étroitement lié à la probabilité de survie d'une classe de processus de branchement non-homogènes. En établissant cette connexion et en analysant précisément le processus de branchement, on peut obtenir l'expression asymptotique précise du seuil.

Contributions principales

1. Identification du seuil exact (Théorème 1.1): Pour la percolation bootstrap $r$, on prouve que la probabilité d'arête critique est $p_c(n,r) = \left(\frac{\alpha_r}{n\log^{r-1}n}\right)^{1/r}(1+o(1))$ où $\alpha_r = (r-1)!\left(\frac{r-1}{r}\right)^{2(r-1)}$
2. Borne supérieure pour la percolation bootstrap $K_4$ (Théorème 1.2): On prouve que $p_c(n,K_4) \leq \frac{1+o(1)}{\sqrt{3n\log n}}$ et on conjecture que cette borne est asymptotiquement optimale
3. Seuil d'arête germe (Théorème 1.4): Pour $p=\sqrt{\alpha/(n\log n)}$, on prouve que $\alpha > 1/3$ implique que $G_{n,p}$ contient avec haute probabilité une arête germe
4. Probabilité de survie du processus de branchement (Théorème 1.5): Pour le processus de branchement non-homogène associé, on déduit la formule asymptotique $P(X_t > 0, \forall t) = \exp\left[-\frac{(r-1)^2}{r}k_r(1+o(1))\right]$ où $k_r = \left(\frac{(r-1)!}{\varepsilon}\right)^{1/(r-1)}$
5. Innovation méthodologique: Introduction du concept de « graphes susceptibles sans triangles » (triangle-free susceptible graphs), permettant de restreindre à cette classe spéciale pour établir une quasi-indépendance des ensembles infectieux, rendant ainsi la méthode du second moment viable

Explication détaillée de la méthode

Définition des tâches

Percolation bootstrap $r$:

• Entrée: Graphe $G=(V,E)$, ensemble initial infecté $V_0 \subset V$, seuil $r$
• Règle d'évolution: $V_{t+1} = V_t \cup \{v : |N(v) \cap V_t| \geq r\}$
• Sortie: Ensemble infecté final $V_\infty = \langle V_0, G \rangle_r$

Ensemble infectieux (Contagious set): Si $\langle I, G \rangle_r = V$, on dit que $I$ est un ensemble infectieux de $G$

Susceptibilité (Susceptibility): Si le graphe $G$ contient un ensemble infectieux de taille $r$ (ensemble infectieux minimal), on dit que $G$ est susceptible ou $r$-percolant

Probabilité critique: $p_c(n,r) = \inf\{p > 0 : P(G_{n,p}\text{ susceptible}) \geq 1/2\}$

Architecture générale

La preuve du théorème se divise en deux parties principales :

1. Preuve de la borne inférieure (Section 2): Preuve que $\alpha < \alpha_r$ implique non-susceptibilité

Idée centrale: Utiliser la méthode du premier moment (first moment method) pour prouver que lorsque $p$ est petit, tout ensemble de taille $r$ ne peut infecter que $O(\log n)$ sommets.

Étapes clés:

• Établir une relation de récurrence pour calculer le nombre de graphes susceptibles minimaux $m_r(k,i)$ (taille $k$, avec $i$ sommets au sommet)
• Déduire une borne supérieure pour la quantité normalisée $\sigma_r(k,i)$ (Lemme 2.5)
• Définir le paramètre critique $\beta^*(\alpha)$, racine positive unique de l'équation : $r + \beta\log\left(\frac{\alpha\beta^{r-1}}{(r-1)!}\right) - \frac{\alpha\beta^r}{r!} - \beta(r-2) = 0$
• Prouver que lorsque $\alpha < \alpha_r$, tout $r$-percolation croît au maximum jusqu'à $(\beta^*(\alpha)+\delta)\log n$ sommets (Proposition 2.1)

2. Preuve de la borne supérieure (Section 3): Preuve que $\alpha > \alpha_r$ implique susceptibilité

Idée centrale: Utiliser la méthode du second moment pour prouver l'existence d'un ensemble infectieux. Le défi principal est la dépendance entre les ensembles infectieux.

Stratégie innovante:

• Introduction de la percolation $\hat{r}$: Restriction aux sous-graphes susceptibles sans triangles, définition du processus de percolation $\hat{r}$
• Quasi-indépendance (Lemme 3.12): Utiliser le théorème de Mantel (densité d'arêtes des graphes sans triangles au plus 1/2) pour prouver la quasi-indépendance entre différentes percolations $\hat{r}$
• Estimation inférieure: Prouver que le nombre de graphes susceptibles sans triangles est asymptotiquement égal au nombre de graphes susceptibles généraux (Lemme 3.5)
• Croissance supercritique: Prouver que les percolations dépassant la taille critique $\beta_r(\alpha)\log n$ continuent de croître jusqu'à l'échelle linéaire

Détails techniques

Relation de récurrence (Équation 2.1)

Pour le nombre de graphes susceptibles minimaux : $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)$ où $a_r(x,y) = \binom{x}{r} - \binom{x-y}{r}$ représente le nombre de façons pour les sommets du sommet de se connecter.

Transformation de normalisation (Équation 2.3)

Définir $\sigma_r(k,i) = \frac{m_r(k,i)}{(k-r)!}\left(\frac{(r-1)!}{k^{r-1}}\right)^k$ ce qui rend la relation de récurrence favorable à l'analyse spectrale.

Récurrence pour graphes sans triangles (Équation 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)$ où $\hat{a}_r(x,y) = \max\{0, a_r(x,y) - 2ryx^{r-2}\}$ le terme soustrait représente les connexions pouvant créer des triangles.

Quasi-indépendance (Lemme 3.12)

Pour des ensembles disjoints de taille $r$, $I \neq I'$, si $|I \cap I'| = m$ :