16.4 Graphe complet et modèle de Erdős-Rényi
225
lim
n→∞
P
max
v∈Vn
|G n (v)| c log(n)
= 0.
2. Si λ > 1 alors
max v∈Vn |G(v)|
n
p.s.
−→
n→∞
1 − ρ
où ρ ∈ ]0, 1[ est la probabilité d’extinction d’un processus de branchement de Galton-Watson de loi de reproduction Poi(λ). De plus, il existe
un réel c > 0 tel que presque sûrement la seconde composante connexe
(en taille) a une taille au plus c log(n).
En substance, si λ < 1 alors la connectivité du graphe aléatoire est si faible
qu’il ne comporte pas de composante connexe plus grande que O(log(n)). Le
graphe est émietté. Si λ > 1 alors la connectivité du graphe aléatoire est
si forte qu’il contient une unique composante connexe géante contenant une
fraction strictement positive des sommets tandis que les autres composantes
connexes ont une taille qui n’excède pas O(log(n)).
Démonstration. Par souci de simplicité, nous nous contentons d’établir la première propriété seulement. Pour ce faire, on explore G(v) en utilisant un algorithme de parcours en largeur
3 , qui consiste à explorer les voisins de v,
qui constituent la première génération, puis leurs voisins qui n’ont pas déjà
été visités, qui constituent la seconde génération, etc. Cela donne un arbre
fini couvrant
4 G(v), similaire à celui de la figure 3.2. En forçant l’absence
de cycles, cette approche fournit également un couplage avec un arbre aléatoire de Galton-Watson de loi de reproduction Bin(n − 1, p), sous-critique car
(n − 1)p λ < 1, dont la taille totale N vérifie N |G(v)| (l’arbre est plus
gros par absence de cycles). Or le théorème 3.17 affirme que
N
loi
= T où T := inf{k 1 : S k = −1}
est le temps d’atteinte de −1 d’une marche aléatoire (S k ) k0 sur Z issue de
S 0 = 0 et d’incréments (U i ) i1 i.i.d. tels que 1 + U i ∼ Bin(n − 1, p). Fixons
θ > 0 quelconque et posons
M k = e
θS k ϕ(θ)
−k
où ϕ(θ) = E(e
θU1 )
est la transformée de Laplace de la loi des incréments de (S k ) k0 . La suite
(M k ) k0 est une martingale positive pour la filtration naturelle de (S k ) k0 ,
et T est un temps d’arrêt fini p.s. On a lim n→∞ M T ∧n = M T p.s. de sorte que
grâce au lemme de Fatou et au théorème d’arrêt,
e
−θ
E(ϕ(θ)
−T ) = E(M T ) = E( lim
n→∞
M T ∧n ) lim
n→∞
E(M T ∧n ) = E(M 0 ) = 1.
3. «Breadth-First Search» en anglais (BFS).
4. «Spanning tree» en anglais et on parle de «Minimal Spanning Tree» (MST).
225
lim
n→∞
P
max
v∈Vn
|G n (v)| c log(n)
= 0.
2. Si λ > 1 alors
max v∈Vn |G(v)|
n
p.s.
−→
n→∞
1 − ρ
où ρ ∈ ]0, 1[ est la probabilité d’extinction d’un processus de branchement de Galton-Watson de loi de reproduction Poi(λ). De plus, il existe
un réel c > 0 tel que presque sûrement la seconde composante connexe
(en taille) a une taille au plus c log(n).
En substance, si λ < 1 alors la connectivité du graphe aléatoire est si faible
qu’il ne comporte pas de composante connexe plus grande que O(log(n)). Le
graphe est émietté. Si λ > 1 alors la connectivité du graphe aléatoire est
si forte qu’il contient une unique composante connexe géante contenant une
fraction strictement positive des sommets tandis que les autres composantes
connexes ont une taille qui n’excède pas O(log(n)).
Démonstration. Par souci de simplicité, nous nous contentons d’établir la première propriété seulement. Pour ce faire, on explore G(v) en utilisant un algorithme de parcours en largeur
3 , qui consiste à explorer les voisins de v,
qui constituent la première génération, puis leurs voisins qui n’ont pas déjà
été visités, qui constituent la seconde génération, etc. Cela donne un arbre
fini couvrant
4 G(v), similaire à celui de la figure 3.2. En forçant l’absence
de cycles, cette approche fournit également un couplage avec un arbre aléatoire de Galton-Watson de loi de reproduction Bin(n − 1, p), sous-critique car
(n − 1)p λ < 1, dont la taille totale N vérifie N |G(v)| (l’arbre est plus
gros par absence de cycles). Or le théorème 3.17 affirme que
N
loi
= T où T := inf{k 1 : S k = −1}
est le temps d’atteinte de −1 d’une marche aléatoire (S k ) k0 sur Z issue de
S 0 = 0 et d’incréments (U i ) i1 i.i.d. tels que 1 + U i ∼ Bin(n − 1, p). Fixons
θ > 0 quelconque et posons
M k = e
θS k ϕ(θ)
−k
où ϕ(θ) = E(e
θU1 )
est la transformée de Laplace de la loi des incréments de (S k ) k0 . La suite
(M k ) k0 est une martingale positive pour la filtration naturelle de (S k ) k0 ,
et T est un temps d’arrêt fini p.s. On a lim n→∞ M T ∧n = M T p.s. de sorte que
grâce au lemme de Fatou et au théorème d’arrêt,
e
−θ
E(ϕ(θ)
−T ) = E(M T ) = E( lim
n→∞
M T ∧n ) lim
n→∞
E(M T ∧n ) = E(M 0 ) = 1.
3. «Breadth-First Search» en anglais (BFS).
4. «Spanning tree» en anglais et on parle de «Minimal Spanning Tree» (MST).