Motivation et simulations

A quoi ressemble un grand arbre choisi au hasard ? Et un graphe ? Peut-on justifier formellement l'impression que donne les simulations, à savoir que les `objets limites', si on peut les définir, sont fractals ?

random graph
Les grandes composantes connexes d'un graphe aléatoire critique
random graph
Isolation d'une grande composante connexe d'un graphe aléatoire critique
random MST tree
Un grand arbre aléatoire uniforme


Si on regarde la simulation suivante et qu'on considère la suite ordonnée des longueurs des paliers (temps de vie des excursions au dessus du processus infimum) pourquoi donc le processus est-il markovien !? Mieux encore: pourquoi donc a-t-il une dynamique remarquable où les paires de paliers coalescent indépendamment à une vitesse proportionnelle au produit de leurs longueurs ? Comment peut-on montrer ça ?

coalescent multiplicatif
Un processus de coalescence: étant donné $(W_t)_{t\ge 0}$ un mouvement brownien on pose $B^\lambda_t = \lambda t - t^2/2 + W_t$, $I^\lambda_t = \inf\{B^\lambda_s: s\le t\}$ et on considère la suite des longueurs $\mathbf \gamma^\lambda:=(\gamma^\lambda_n)_{n\ge 1}$ d'excursions de $B^\lambda_t$ au dessus de son processus infimum $I^\lambda_t$, triées dans l'ordre décroissant. Alors le processus $\lambda \mapsto \mathbf \gamma^\lambda$ est un processus de markov(!) remarquable, le coalescent multiplicatif.

Description du cours

L'objet du cours est de tenter de répondre à ces questions et de présenter certaines limites de graphes aléatoires considérés en temps qu'espaces métriques. Il s'agira à la fois (a) d'introduire des objets centraux intimement liés au mouvement brownien, (b) de présenter un ensemble de techniques qui sont basées sur des représentations combinatoires explicites et (c) d'étudier les applications aux graphes aléatoires dans le régime dit critique. En particulier, les relations entre objets discrets et continus seront au centre de nos préoccupations.

Le cours comportera deux parties: dans un premier temps, nous considérerons des arbres aléatoires de type Galton--Watson et leurs limites. Nous parlerons en particulier des différents encodages des arbres, de leur convergences, ainsi que tu point de vue `objectif' qui consiste à les considérer comme des espaces métriques (mesurés); ca sera l'occasion de parler de la topologie de Gromov-Hausdorff sur les classes d'isométries d'espaces métriques compacts. Cela nous permettra d'introduire l'arbre continu brownien de plusieurs manières (en particulier comme métrique aléatoire sur $[0,1]$, ou encore par découpage de $\mathbb R_+$ et reorganisation/recollage des morceaux), et d'étudier certaines de ses propriétés. Nous verrons en particulier qu'il s'agit d'un objet fractal qui est au coeur de la construction de nombreux objets limites de structures combinatoires (de la même manière que le mouvement brownien est central pour les convergences fonctionnelles).

Nous verrons ensuite comment, à partir des techniques d'explorations, il est possible d'obtenir la limites de certains graphes aléatoires dans le régime dit `critique' qui précède l'émergence d'une composante connexe macroscopique. En particulier, nous construirons les objets limites à partir de l'arbre brownien continu. Là encore, nous nous efforcerons de développer plusieurs points de vue complémentaires. Nous parlerons aussi de processus de coalescence (en particulier le coalescent multiplicatif) que l'on peut définir comme le processus qui régit la dynamique des tailles des compososantes connexes d'un graphe aléatoire lorsque l'on ajoute des arêtes à la bonne vitesse.

Nous aborderons ensuite certains ces thèmes choisis parmi les suivants: universalité de l'arbre continu brownien, universalité des limites de graphes aléatoires, processus de fragmentation sur l'arbre continu brownien, généalogie de la fragmentation de l'arbre continu et arbre des coupes, constructions explicites des coalescents additifs et multiplicatifs standards.

Déroulement des cours

  • Cours 1 - 13 février 2019: Introduction/simulation : où va-t-on ? qu'est-ce qu'on veut montrer ? quels modèles: arbres uniformes de Cayley, graphes aléatoires de Erdos-Rényi, arbre couvrant (de poids) minimal; exemples de résultats informels: quelle limite pour les arbres ? quelle limite pour les graphes (critiques?) ? quelle limite pour l'arbre couvrant minimal ? Théorème de Frieze sur le poids de l'arbre couvrant minimal. Une limite pour le processus d'aggrégation des composantes connexes des graphes aléatoires ? Une limite pour la fragmentation des arbres uniformes de Cayley ? Une limite pour la généalogie de cette fragmentation. Début des processus de Galton-Watson: transition de phase, taille des arbres.
  • Cours 2 - 20 février 2019 : Arbres discrets : représentation canonique dans $\cup_{n\ge 0}(\mathbb N\setminus \{0\})^n$; relations d'ordres: généalogie, ordre lexicographique, parcours en profondeur, parcours en largeur; encodages: chemin de Lukasiewicz, processus de hauteur, processus de contour; arbre de Galton-Watson critique, théorème local limite, lemme cyclique, distribution de la taille (fini p.s., espérance infinie), lien Lukasiewicz/processus des hauteur; marche renversée et déconditionnement.
  • Cours 3 - 27 février 2019 : Convergence d'arbres de Galton--Watson I : Les encodages. Temps de montée d'échelle, variables d'échelle et leur lois. Concentration des sommes de variables aléatoires iid (avec des moments exponentiels): méthode de Chernoff, inégalité de Doob. Processus browniens conditionnés: pont brownien et excursion brownienne. Convergence jointe de la marche de Lukasiewicz et du processus de hauteur vers la paire $(e,e)$, où $e$ est une excursion brownienne. Arguments rapides pour convergence de la marche de Lukasiewicz (marche aléatoire conditonnée en passant par convergence vers un pont, plus transformation cyclique continue)
  • Cours 4 - 5 mars 2019 : L'arbre continu brownien I: Exemples de classes combinatoires réalisables par des arbres de Galton-Watson conditionnés à la taille (plan/géometrique, étiquetés/Poisson). Espace métrique $\cal T_f$ encodé par une excursion continue $f$. Arbres réels. L'espace $\cal T_f$ est un arbre réel compact. Arbres réduits. Distance de Hausdorff, distance de Gromov--Hausdorff. L'ensemble des classes d'équivalence d'arbres réels compacts est un espace métrique polonais. L'application $f\mapsto \cal T_f$ est continue. Algorithme d'Aldous-Broder; chaine de Markov sur $\mathbb T_n^L$ associée.
  • Cours 5 - 13 mars 2019 : L'arbre continu brownien II: Aldous-Broder 2.0; chaîne inverse; Lemme de Kelly; limite d'échelle: construction ``stick breaking''; loi des arbres obtenus par les $k$ premières branches. Arbre binaire plantés planaires et algorithme de Rémy. L'objet limite est bien l'arbre brownien. Au passage: mesure de masse (mesure image de la mesure de Lebesgue dans l'arbre), notion de feuille, la masse des feuille est 1.
  • Cours 6 - 20 mars 2019 :
  • Cours 7 - 27 mars 2019 :
  • 3 avril 2019 : pas de cours
  • Cours 8 - 10 avril 2019 :
  • Cours 9 - 17 avril 2019 :
  • Cours 10 - 24 avril 2019 :
  • Cours 11 - 1 mai 2019 : !!!
  • Cours 12 - 8 mai 2019 : !!!

References

  1. D. Aldous. The continuum random tree. I. Ann. Probab. vol. 19, pp. 1--28, 1991.
  2. D. Aldous. The continuum random tree. III. Ann. Probab. vol. 21, pp. 248--289, 1993.
  3. D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. vol. 25, pp. 812--854, 1997.
  4. L. Addario-Berry, N. Broutin, and C. Goldschmidt. The continuum limit of critical random graphs. Probability Theory and Related Fields. vol. 152, pp. 367--406, 2012.
  5. L. Addario-Berry, N. Broutin, and C. Goldschmidt. Critical random graphs: limiting constructions and distributional properties. Electron. J. Probab.. vol. 15, pp. 741--774, 2010.
  6. N. Broutin and J.-F. Marckert. Asymptotics of trees with a prescribed degree sequence and applications. Random Structures and Algorithms, vol. 44, pp. 290--316, 2014.
  7. N. Broutin and J.-F. Marckert. A new encoding of coalescent processse. Applications to the additive and multiplicative cases. Probability and Related Fields, vol. 166, pp. 515--552, 2016.
  8. T. Duquesne and J.-F. Le Gall. Random trees, Levy processes and spacial branching processes. Asterique, vol. 281, 2002.
  9. S. Evans. Probability and Real Trees. Lecture Notes in Mathematics, vol. 1920, Springer, Berlin, 2005.
  10. J.-F. Le Gall. Spatial Branching Processes, Random Snakes, and Partial Differential Equations. Birkhauser, Basel, 1999.
  11. J.-F. Le Gall. Random trees and applications. Probability Surveys, vol. 2, pp. 245--311, 2005.
  12. J.-F. Marckert and A. Mokkadem. The depth first processes of Galton--Watson trees converge to the same Brownian excursion. The Annals of Probability, vol. 31, pp. 1655--1678, 2003.
  13. J. Pitman. Combinatorial Stochastic Processes. Lecture Notes in Mathematics, vol. 1975, Springer, Berlin, 2006.