224
16 Percolation
Toutefois, la situation est bien différente de celle du graphe de Bethe : on
peut établir que la classe infinie est unique ! Cette démonstration dépasse le
cadre de ce chapitre. Nous nous contentons d’une démonstration sur E 2 en
supposant connu le fait que θ 2 (1/2) = 0.
Théorème 16.13 (Unicité de la classe infinie). Supposons que d = 2 et que
θ 2 (1/2) = 0 sur le graphe E 2 . Alors, pour tout p > p c (2), il existe P p -p.s. une
unique classe infinie.
Démonstration. Reprenons les notations de la preuve du lemme 16.11.
Pour p = 1/2, la percolation sur le graphe E 2 et sur son graphe dual E
∗
2 sont
de même nature : P p -p.s. il n’y a pas de composante infinie car θ 2 (1/2) = 0.
Soit Λ(m) = [−m, m]
2 . Il existe une boucle γ ∗ auto-évitante dans E
∗
2 entourant
Λ(m) et dont les arêtes sont dans F
∗ (donc les arêtes duales dans E 2 ne sont pas
dans F ). Par le même argument, il existe une boucle γ dans E 2 qui contient
γ ∗ et donc Λ(m). Par couplage, ceci est encore vrai pour tout p > 1/2. Si
deux classes d’équivalence infinies intersectent Λ(m) alors elles intersectent
également γ et sont donc confondues ! Puisque ceci est vrai pour tout m, il ne
peut y avoir qu’une classe infinie.
16.4 Graphe complet et modèle de Erdős-Rényi
On considère dans cette section le cas où (V, E) est le graphe complet infini
K ∞ , c’est-à-dire que V est infini dénombrable et E = P 2 (V ). Ainsi x ∼ y pour
tous x = y dans V . Les sommets jouent tous le même rôle. Comme tous les
sommets sont voisins dans K ∞ , il n’y a donc pas de géométrie comme dans
B r ou dans E d . Sous P p le graphe aléatoire (V, F ) est appelé modèle de ErdősRényi infini. Pour tous p ∈]0, 1] et x ∈ V , le sommet x a un nombre infini de
voisins dans (V, F ) et P p (|C(x)| = ∞) = 1, d’où θ = 1 ]0,1] et p c = 0.
Pour rendre le modèle plus passionnant, on peut considérer le phénomène
de la percolation dans le graphe complet fini K n à n sommets V = {1, . . . , n}
et faire dépendre de n le paramètre p de P p . On note G(n, p) la loi du graphe
aléatoire (V, F ) sous P p . Dans ce modèle de Erdős-Rényi fini G(n, p), chaque
sommet x ∈ V possède un nombre aléatoire de voisins, qui suit la loi binomiale
Bin(n − 1, p) de moyenne (n − 1)p ∼ np. Lorsque n → ∞ avec np → λ > 0
alors p n ∼ λ/n → 0 et le nombre de voisins de chaque site converge en loi
vers la loi de Poisson Poi(λ) (loi des petits nombres).
Théorème 16.14 (Phénomène de seuil et composante connexe géante). Soit
λ > 0 un paramètre réel fixé, et α := λ − 1 − log(λ) > 0. Soit (G n ) n1 une
suite de graphes de Erdős-Rényi définis sur un même espace de probabilité,
avec G n = (V n , F n ) de loi de Erdős-Rényi G(n, p) avec p = λ/n. Pour tout
v ∈ V n , soit G n (v) la composante connexe du sommet v.
1. Si λ < 1 alors pour tout c > 1/α,
16 Percolation
Toutefois, la situation est bien différente de celle du graphe de Bethe : on
peut établir que la classe infinie est unique ! Cette démonstration dépasse le
cadre de ce chapitre. Nous nous contentons d’une démonstration sur E 2 en
supposant connu le fait que θ 2 (1/2) = 0.
Théorème 16.13 (Unicité de la classe infinie). Supposons que d = 2 et que
θ 2 (1/2) = 0 sur le graphe E 2 . Alors, pour tout p > p c (2), il existe P p -p.s. une
unique classe infinie.
Démonstration. Reprenons les notations de la preuve du lemme 16.11.
Pour p = 1/2, la percolation sur le graphe E 2 et sur son graphe dual E
∗
2 sont
de même nature : P p -p.s. il n’y a pas de composante infinie car θ 2 (1/2) = 0.
Soit Λ(m) = [−m, m]
2 . Il existe une boucle γ ∗ auto-évitante dans E
∗
2 entourant
Λ(m) et dont les arêtes sont dans F
∗ (donc les arêtes duales dans E 2 ne sont pas
dans F ). Par le même argument, il existe une boucle γ dans E 2 qui contient
γ ∗ et donc Λ(m). Par couplage, ceci est encore vrai pour tout p > 1/2. Si
deux classes d’équivalence infinies intersectent Λ(m) alors elles intersectent
également γ et sont donc confondues ! Puisque ceci est vrai pour tout m, il ne
peut y avoir qu’une classe infinie.
16.4 Graphe complet et modèle de Erdős-Rényi
On considère dans cette section le cas où (V, E) est le graphe complet infini
K ∞ , c’est-à-dire que V est infini dénombrable et E = P 2 (V ). Ainsi x ∼ y pour
tous x = y dans V . Les sommets jouent tous le même rôle. Comme tous les
sommets sont voisins dans K ∞ , il n’y a donc pas de géométrie comme dans
B r ou dans E d . Sous P p le graphe aléatoire (V, F ) est appelé modèle de ErdősRényi infini. Pour tous p ∈]0, 1] et x ∈ V , le sommet x a un nombre infini de
voisins dans (V, F ) et P p (|C(x)| = ∞) = 1, d’où θ = 1 ]0,1] et p c = 0.
Pour rendre le modèle plus passionnant, on peut considérer le phénomène
de la percolation dans le graphe complet fini K n à n sommets V = {1, . . . , n}
et faire dépendre de n le paramètre p de P p . On note G(n, p) la loi du graphe
aléatoire (V, F ) sous P p . Dans ce modèle de Erdős-Rényi fini G(n, p), chaque
sommet x ∈ V possède un nombre aléatoire de voisins, qui suit la loi binomiale
Bin(n − 1, p) de moyenne (n − 1)p ∼ np. Lorsque n → ∞ avec np → λ > 0
alors p n ∼ λ/n → 0 et le nombre de voisins de chaque site converge en loi
vers la loi de Poisson Poi(λ) (loi des petits nombres).
Théorème 16.14 (Phénomène de seuil et composante connexe géante). Soit
λ > 0 un paramètre réel fixé, et α := λ − 1 − log(λ) > 0. Soit (G n ) n1 une
suite de graphes de Erdős-Rényi définis sur un même espace de probabilité,
avec G n = (V n , F n ) de loi de Erdős-Rényi G(n, p) avec p = λ/n. Pour tout
v ∈ V n , soit G n (v) la composante connexe du sommet v.
1. Si λ < 1 alors pour tout c > 1/α,