218
16 Percolation
16.2 Graphe de Bethe (arbre régulier)
On considère dans cette section le cas où (V, E) est le graphe de Bethe
B r de degré r 2, c’est-à-dire l’arbre infini dont chaque sommet a r voisins
sauf un qui n’en a que r − 1, noté 0 et appelé racine de l’arbre (voir la
figure 16.2). Pour tout p ∈ [0, 1], sous P p , le graphe aléatoire (V, F ) est un
ensemble d’arbres qu’on appelle parfois forêt. La probabilité de percolation
et la probabilité critique pour le sommet racine ∅ = 0 dans B r sous P p sont
respectivement notées
θ r (p) := P p (0 ↔ ∞) = P p (|C(0)| = ∞),
p c (r) := sup {p ∈ [0, 1] : θ r (p) = 0}.
Théorème 16.3 (Phénomène de seuil pour percolation sur graphe de Bethe).
Pour tout r 2 et tout p ∈ [0, 1] la quantité θ r (p) est la plus grande racine
en θ ∈ [0, 1] de l’équation
1 − θ = (1 − pθ)
r−1 ,
tandis que
p c (r) =
1
r − 1
.
De plus, la fonction θ r est continue, nulle sur [0, p c (r)], strictement croissante
sur [p c (r), 1], et pour r 3 on a
lim
p→pc(r) +
θ r (p)
p − p c (r)
=
2
p c (r)(1 − p c (r))
=
2(r − 1)
2
r − 2
.
Si r 3 alors 0 < p c (r) < 1 ce qui indique la présence d’un phénomène de
seuil pour la percolation sur le graphe de Bethe B r .
Démonstration. Le graphe de Bethe B r coïncide avec l’arbre de GaltonWatson de loi de reproduction δ r−1 . Sous P p on obtient un arbre aléatoire
dans lequel chaque sommet de l’arbre est relié à chacun de ses r − 1 enfants
avec une probabilité p. Le nombre de ces connexions est distribué selon la loi
de reproduction Bin(r − 1, p) de moyenne m = (r − 1)p. D’après le chapitre 3,
cet arbre est sous-critique si m < 1, critique si m = 1, et sur-critique si m > 1.
D’après le théorème 3.7 la probabilité d’extinction de la population est la plus
petite racine s p de l’équation g p (s) = s où g p est la fonction génératrice de
la loi de reproduction : g p (s) = (ps + 1 − p)
r−1 pour s ∈ [0, 1]. L’extinction
de la population est synonyme de la finitude de la composante connexe de la
racine. On a donc θ r (p) = 1 − s p et θ r (p) est ainsi la plus grande racine dans
[0, 1] de l’équation 1 − θ = (1 − pθ)
r−1 .
Soit h p la fonction définie sur [0, 1] par h p (θ) = (1 − pθ)
r−1
− 1 + θ. Elle
est nulle en 0, strictement positive en 1, strictement convexe si r 3 et affine
si r = 2. De plus h
p (0) a le signe de 1 − p(r − 1). Ainsi, pour p(r − 1) 1,
16 Percolation
16.2 Graphe de Bethe (arbre régulier)
On considère dans cette section le cas où (V, E) est le graphe de Bethe
B r de degré r 2, c’est-à-dire l’arbre infini dont chaque sommet a r voisins
sauf un qui n’en a que r − 1, noté 0 et appelé racine de l’arbre (voir la
figure 16.2). Pour tout p ∈ [0, 1], sous P p , le graphe aléatoire (V, F ) est un
ensemble d’arbres qu’on appelle parfois forêt. La probabilité de percolation
et la probabilité critique pour le sommet racine ∅ = 0 dans B r sous P p sont
respectivement notées
θ r (p) := P p (0 ↔ ∞) = P p (|C(0)| = ∞),
p c (r) := sup {p ∈ [0, 1] : θ r (p) = 0}.
Théorème 16.3 (Phénomène de seuil pour percolation sur graphe de Bethe).
Pour tout r 2 et tout p ∈ [0, 1] la quantité θ r (p) est la plus grande racine
en θ ∈ [0, 1] de l’équation
1 − θ = (1 − pθ)
r−1 ,
tandis que
p c (r) =
1
r − 1
.
De plus, la fonction θ r est continue, nulle sur [0, p c (r)], strictement croissante
sur [p c (r), 1], et pour r 3 on a
lim
p→pc(r) +
θ r (p)
p − p c (r)
=
2
p c (r)(1 − p c (r))
=
2(r − 1)
2
r − 2
.
Si r 3 alors 0 < p c (r) < 1 ce qui indique la présence d’un phénomène de
seuil pour la percolation sur le graphe de Bethe B r .
Démonstration. Le graphe de Bethe B r coïncide avec l’arbre de GaltonWatson de loi de reproduction δ r−1 . Sous P p on obtient un arbre aléatoire
dans lequel chaque sommet de l’arbre est relié à chacun de ses r − 1 enfants
avec une probabilité p. Le nombre de ces connexions est distribué selon la loi
de reproduction Bin(r − 1, p) de moyenne m = (r − 1)p. D’après le chapitre 3,
cet arbre est sous-critique si m < 1, critique si m = 1, et sur-critique si m > 1.
D’après le théorème 3.7 la probabilité d’extinction de la population est la plus
petite racine s p de l’équation g p (s) = s où g p est la fonction génératrice de
la loi de reproduction : g p (s) = (ps + 1 − p)
r−1 pour s ∈ [0, 1]. L’extinction
de la population est synonyme de la finitude de la composante connexe de la
racine. On a donc θ r (p) = 1 − s p et θ r (p) est ainsi la plus grande racine dans
[0, 1] de l’équation 1 − θ = (1 − pθ)
r−1 .
Soit h p la fonction définie sur [0, 1] par h p (θ) = (1 − pθ)
r−1
− 1 + θ. Elle
est nulle en 0, strictement positive en 1, strictement convexe si r 3 et affine
si r = 2. De plus h
p (0) a le signe de 1 − p(r − 1). Ainsi, pour p(r − 1) 1,