16
Percolation
Mots-clés. Percolation ; phénomène de seuil ; graphe aléatoire ; arbre aléatoire ; arbre de Bethe ; réseau euclidien ; graphe complet ; graphe aléatoire de
Erdős-Rényi.
Outils. Couplage ; lemme de sous-additivité de Fekete ; loi du zéro-un
de Kolmogorov ; marche aléatoire ; processus de Galton-Watson ; martingale ;
théorème d’arrêt ; inégalité de Markov ; transformée de Laplace.
Difficulté. **
La percolation désigne initialement le passage d’un fluide à travers un milieu perméable, comme l’eau dans le café ou le pétrole dans la roche. Signalons
qu’une des motivations de l’étude mathématique de ce phénomène était la modélisation d’un filtre de masque à gaz. On peut également utiliser la notion
de percolation pour modéliser la propagation d’une information au sein d’un
réseau social par exemple : chaque individu est connecté directement à plusieurs autres et l’on cherche à comprendre à qui il est relié dans la population
globale via ces connections locales.
Nous commençons par introduire la notion de percolation sur un graphe général. Nous abordons ensuite le cas plutôt simple du graphe de Bethe (arbre),
puis celui plus physique du graphe euclidien. Nous terminons par quelques
mots sur un modèle de graphe complet. Ces trois cadres peuvent modéliser la
transmission d’information dans une entreprise à très fort sens de la hiérarchie
(pour le premier) ou dans un réseau social (pour le troisième) ou encore la
circulation d’un fluide dans une roche perméable (pour le deuxième).
16.1 Percolation dans un graphe
Un graphe (non-orienté) est un couple G = (V, E) où V est un ensemble
non-vide fini ou infini dénombrable, et où E ⊂ P 2 (V ), où P 2 (V ) est l’ensemble
215
© Springer-Verlag Berlin Heidelberg 2016
D. Chafaï and F. Malrieu, Recueil de Modèles Aléatoires,
Mathématiques et Applications 78, DOI 10.1007/978-3-662-49768-5_16
Percolation
Mots-clés. Percolation ; phénomène de seuil ; graphe aléatoire ; arbre aléatoire ; arbre de Bethe ; réseau euclidien ; graphe complet ; graphe aléatoire de
Erdős-Rényi.
Outils. Couplage ; lemme de sous-additivité de Fekete ; loi du zéro-un
de Kolmogorov ; marche aléatoire ; processus de Galton-Watson ; martingale ;
théorème d’arrêt ; inégalité de Markov ; transformée de Laplace.
Difficulté. **
La percolation désigne initialement le passage d’un fluide à travers un milieu perméable, comme l’eau dans le café ou le pétrole dans la roche. Signalons
qu’une des motivations de l’étude mathématique de ce phénomène était la modélisation d’un filtre de masque à gaz. On peut également utiliser la notion
de percolation pour modéliser la propagation d’une information au sein d’un
réseau social par exemple : chaque individu est connecté directement à plusieurs autres et l’on cherche à comprendre à qui il est relié dans la population
globale via ces connections locales.
Nous commençons par introduire la notion de percolation sur un graphe général. Nous abordons ensuite le cas plutôt simple du graphe de Bethe (arbre),
puis celui plus physique du graphe euclidien. Nous terminons par quelques
mots sur un modèle de graphe complet. Ces trois cadres peuvent modéliser la
transmission d’information dans une entreprise à très fort sens de la hiérarchie
(pour le premier) ou dans un réseau social (pour le troisième) ou encore la
circulation d’un fluide dans une roche perméable (pour le deuxième).
16.1 Percolation dans un graphe
Un graphe (non-orienté) est un couple G = (V, E) où V est un ensemble
non-vide fini ou infini dénombrable, et où E ⊂ P 2 (V ), où P 2 (V ) est l’ensemble
215
© Springer-Verlag Berlin Heidelberg 2016
D. Chafaï and F. Malrieu, Recueil de Modèles Aléatoires,
Mathématiques et Applications 78, DOI 10.1007/978-3-662-49768-5_16