216
16 Percolation
des parties de V à deux éléments. Les éléments de V et E sont respectivement
appelés
1 sommets et arêtes du graphe G. Si l’arête {x, y} appartient à E, on
dit que x et y sont voisins et on note x ∼ y. L’exemple le plus immédiat est
celui du graphe euclidien E d = (V, E) pour lequel V = Z
d et
E = {{x, y} : x, y ∈ Z
d , |x − y| 1 := |x 1 − y 1 | + · · · + |x d − y d | = 1}.
Un chemin de longueur n dans le graphe (V, E) reliant un sommet x à un
sommet y est une suite finie x = x 0 ∼ · · · ∼ x n = y. S’il existe un chemin
reliant x à y, on dit que x et y communiquent (ou sont connectés) et on
note x ↔ y. On n’a jamais x ∼ x, mais on convient que x ↔ x pour tout
x ∈ V . La relation binaire ↔ sur V est une relation d’équivalence et la classe
d’équivalence (ou composante connexe) du point x est notée C(x). Un chemin
est dit auto-évitant si tous les sommets qui le composent sont distincts. Si
x ↔ y et x = y alors il existe un chemin auto-évitant de x à y, construit à
partir d’un chemin quelconque en effaçant les boucles. Un chemin reliant un
sommet à lui-même est appelée cycle. On dit que (V, E) est un arbre lorsqu’il
est connexe et n’a pas de cycles, ou de manière équivalente lorsque deux
sommets distincts sont toujours reliés par un unique chemin auto-évitant.
Dans la suite V est, sauf mention du contraire, infini dénombrable. Soit
F ⊂ E. On dit qu’il y a percolation en x ∈ V (pour F ) si la classe C(x) de
x dans le graphe (V, F ) est de taille infinie (|C(x)| = ∞), et on note x ↔ ∞.
On identifie l’ensemble des parties de E à l’ensemble
Ω := {0, 1}
E .
Dans la suite, on choisit F de manière aléatoire dans Ω, et ainsi (V, F ) est un
graphe aléatoire. On décide de fabriquer F à partir de E en tirant à pile ou
face pour savoir si on conserve ou si on efface chaque arête de E. Cela revient
à introduire la loi de probabilité
P p =
e∈E
Ber(p)
sur Ω muni de sa tribu cylindrique F, où p ∈ [0, 1] est un paramètre fixé. On
note E p l’espérance sous P p . Pour étudier l’influence du paramètre p sur le
phénomène de percolation sous P p , on distingue un sommet particulier ∅ ∈ V ,
que nous appelons racine – on dit qu’on enracine (V, E) en ∅ – et on définit
la probabilité de percolation sous P p pour ∅ par
θ(p) := P p (∅ ↔ ∞) = P p (|C(∅)| = ∞).
Lemme 16.1 (Monotonie). La fonction p ∈ [0, 1] → θ(p) est croissante, et
θ(0) = 0 et θ(1) = 1.
1. On dit «vertices» et «edges» en anglais, d’où la notation.
16 Percolation
des parties de V à deux éléments. Les éléments de V et E sont respectivement
appelés
1 sommets et arêtes du graphe G. Si l’arête {x, y} appartient à E, on
dit que x et y sont voisins et on note x ∼ y. L’exemple le plus immédiat est
celui du graphe euclidien E d = (V, E) pour lequel V = Z
d et
E = {{x, y} : x, y ∈ Z
d , |x − y| 1 := |x 1 − y 1 | + · · · + |x d − y d | = 1}.
Un chemin de longueur n dans le graphe (V, E) reliant un sommet x à un
sommet y est une suite finie x = x 0 ∼ · · · ∼ x n = y. S’il existe un chemin
reliant x à y, on dit que x et y communiquent (ou sont connectés) et on
note x ↔ y. On n’a jamais x ∼ x, mais on convient que x ↔ x pour tout
x ∈ V . La relation binaire ↔ sur V est une relation d’équivalence et la classe
d’équivalence (ou composante connexe) du point x est notée C(x). Un chemin
est dit auto-évitant si tous les sommets qui le composent sont distincts. Si
x ↔ y et x = y alors il existe un chemin auto-évitant de x à y, construit à
partir d’un chemin quelconque en effaçant les boucles. Un chemin reliant un
sommet à lui-même est appelée cycle. On dit que (V, E) est un arbre lorsqu’il
est connexe et n’a pas de cycles, ou de manière équivalente lorsque deux
sommets distincts sont toujours reliés par un unique chemin auto-évitant.
Dans la suite V est, sauf mention du contraire, infini dénombrable. Soit
F ⊂ E. On dit qu’il y a percolation en x ∈ V (pour F ) si la classe C(x) de
x dans le graphe (V, F ) est de taille infinie (|C(x)| = ∞), et on note x ↔ ∞.
On identifie l’ensemble des parties de E à l’ensemble
Ω := {0, 1}
E .
Dans la suite, on choisit F de manière aléatoire dans Ω, et ainsi (V, F ) est un
graphe aléatoire. On décide de fabriquer F à partir de E en tirant à pile ou
face pour savoir si on conserve ou si on efface chaque arête de E. Cela revient
à introduire la loi de probabilité
P p =
e∈E
Ber(p)
sur Ω muni de sa tribu cylindrique F, où p ∈ [0, 1] est un paramètre fixé. On
note E p l’espérance sous P p . Pour étudier l’influence du paramètre p sur le
phénomène de percolation sous P p , on distingue un sommet particulier ∅ ∈ V ,
que nous appelons racine – on dit qu’on enracine (V, E) en ∅ – et on définit
la probabilité de percolation sous P p pour ∅ par
θ(p) := P p (∅ ↔ ∞) = P p (|C(∅)| = ∞).
Lemme 16.1 (Monotonie). La fonction p ∈ [0, 1] → θ(p) est croissante, et
θ(0) = 0 et θ(1) = 1.
1. On dit «vertices» et «edges» en anglais, d’où la notation.