16.5 Pour aller plus loin
227
sont orientées), percolation de premier passage, de dernier passage, percolation
par sommets (ce sont les sommets et non les arêtes qui sont déclarés ouverts ou
fermés), etc. Une bonne partie de ce chapitre est inspirée des notes de cours de
Thierry Lévy [Lé08]. La théorie mathématique de la percolation, développée
depuis le milieu du vingtième siècle par John Hammersley et Harry Kesten
notamment, constitue depuis lors un domaine très actif des probabilités. Un
panorama sur le sujet se trouve dans les livres [Gri99, Gri10] de Geoffrey
Grimmett, dont la thèse soutenue en 1974 sous la direction de Hammersley et
Dominic Welsh (ancien élève de Hammersley également) portait déjà sur les
champs et graphes aléatoires ! Le théorème 16.14 date des travaux du milieu
du vingtième siècle de Paul Erdős et Alfréd Rényi [ER59, ER61b] et de Edgar
Gilbert [Gil59]. La preuve du théorème 16.14 est inspirée des notes de cours de
Charles Bordenave [Bor14a]. Plus généralement, on peut établir ce qui suit :
Condition sur (n, p) Comportement p.s. du graphe aléatoire G(n, p) quand n → ∞
np < (1 − ε) log(n) existence de sommets isolés (donc graphe non connexe)
np > (1 + ε) log(n) graphe connexe (donc np ∼ log(n) est un seuil de connectivité)
np < 1 pas de composante connexe de taille > O(log(n))
np = 1 plus grande composante connexe de taille ≈ n
2/3
np → λ > 1 unique composante connexe géante (fraction > 0 des sommets)
aucune autre composante connexe n’est > O(log(n)).
On renvoie à ce sujet à [Bor14a] et au livre de Remco van der Hofstad
[vdH14]. On y trouvera la démonstration du second point du théorème 16.14.
Le lemme 16.8 sur la constante de connectivité du graphe euclidien est
l’une des clés de la démonstration du théorème 16.7. Toutefois, la valeur exacte
de cette constante κ(d) est inconnue pour tout d 2. Hugo Duminil-Copin
et Stanislav Smirnov ont montré dans [DCS12] qu’elle vaut
2 +
√
2 pour
le graphe hexagonal sur Z
2 . La démonstration du théorème 16.13, tirée de
l’article de synthèse [HJ06], est due à Theodore Harris [Har60]. Dans ce travail, Harris établit également que θ 2 (1/2) = 0 c’est-à-dire que p c (2) 1/2.
Il faudra attendre le travail de Kesten [Kes80] pour que l’égalité p c (2) = 1/2
soit démontrée. Pour les autres valeurs de d, la valeur de la probabilité critique n’est pas connue. On peut toutefois établir que θ d est de classe C
∞ sur
l’intervalle ]p c (d), 1[.
227
sont orientées), percolation de premier passage, de dernier passage, percolation
par sommets (ce sont les sommets et non les arêtes qui sont déclarés ouverts ou
fermés), etc. Une bonne partie de ce chapitre est inspirée des notes de cours de
Thierry Lévy [Lé08]. La théorie mathématique de la percolation, développée
depuis le milieu du vingtième siècle par John Hammersley et Harry Kesten
notamment, constitue depuis lors un domaine très actif des probabilités. Un
panorama sur le sujet se trouve dans les livres [Gri99, Gri10] de Geoffrey
Grimmett, dont la thèse soutenue en 1974 sous la direction de Hammersley et
Dominic Welsh (ancien élève de Hammersley également) portait déjà sur les
champs et graphes aléatoires ! Le théorème 16.14 date des travaux du milieu
du vingtième siècle de Paul Erdős et Alfréd Rényi [ER59, ER61b] et de Edgar
Gilbert [Gil59]. La preuve du théorème 16.14 est inspirée des notes de cours de
Charles Bordenave [Bor14a]. Plus généralement, on peut établir ce qui suit :
Condition sur (n, p) Comportement p.s. du graphe aléatoire G(n, p) quand n → ∞
np < (1 − ε) log(n) existence de sommets isolés (donc graphe non connexe)
np > (1 + ε) log(n) graphe connexe (donc np ∼ log(n) est un seuil de connectivité)
np < 1 pas de composante connexe de taille > O(log(n))
np = 1 plus grande composante connexe de taille ≈ n
2/3
np → λ > 1 unique composante connexe géante (fraction > 0 des sommets)
aucune autre composante connexe n’est > O(log(n)).
On renvoie à ce sujet à [Bor14a] et au livre de Remco van der Hofstad
[vdH14]. On y trouvera la démonstration du second point du théorème 16.14.
Le lemme 16.8 sur la constante de connectivité du graphe euclidien est
l’une des clés de la démonstration du théorème 16.7. Toutefois, la valeur exacte
de cette constante κ(d) est inconnue pour tout d 2. Hugo Duminil-Copin
et Stanislav Smirnov ont montré dans [DCS12] qu’elle vaut
2 +
√
2 pour
le graphe hexagonal sur Z
2 . La démonstration du théorème 16.13, tirée de
l’article de synthèse [HJ06], est due à Theodore Harris [Har60]. Dans ce travail, Harris établit également que θ 2 (1/2) = 0 c’est-à-dire que p c (2) 1/2.
Il faudra attendre le travail de Kesten [Kes80] pour que l’égalité p c (2) = 1/2
soit démontrée. Pour les autres valeurs de d, la valeur de la probabilité critique n’est pas connue. On peut toutefois établir que θ d est de classe C
∞ sur
l’intervalle ]p c (d), 1[.