Organisation du cours

Séances: mercredis de 14:00 à 17:00 en 16-26.113 Détails ici.

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


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.

Déroulement des cours (et prévision pour les cours futurs)

  • Cours 1 - 1 février 2023 : Introduction générale, Arbres Discrets et représentations, arbres de Galton--Watson. Simulations, arbres uniformes, graphes aléatoires, transition de phase, arbre couvrant minimum, processus de coalescence/fragmentation remarquables. Arbres Discrets et représentations. Représentation des arbres par des ensembles de mots finis. Encodages: Processus des hauteurs, marche de Lukasiewicz, processus de contour. Arbre associé à une famille de nombre d'enfants, arbres de Galton--Watson, loi. Lien classes combinatoire / arbres de Galton--Watson: exemples des arbres plans enracinés uniformes, arbres de Cayley.
  • Cours 2 - 8 février 2023 :
  • Cours 3 - 15 février 2023 :
  • Cours 4 - 22 février 2023 :
  • Cours 5 - 1 mars 2023 :
  • Cours 6 - 8 mars 2023 :
  • Cours 7 - 15 mars 2023 :
  • Cours 8 - 22 mars 2023 :

References

  • D. Aldous. The continuum random tree. I. Ann. Probab. vol. 19, pp. 1--28, 1991.
  • D. Aldous. The continuum random tree. III. Ann. Probab. vol. 21, pp. 248--289, 1993.
  • D. Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. vol. 25, pp. 812--854, 1997.
  • 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.
  • 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.
  • 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.
  • N. Broutin and J.-F. Marckert. A new encoding of coalescent processses. Applications to the additive and multiplicative cases. Probability and Related Fields, vol. 166, pp. 515--552, 2016.
  • T. Duquesne and J.-F. Le Gall. Random trees, Levy processes and spacial branching processes. Asterique, vol. 281, 2002.
  • S. Evans. Probability and Real Trees. Lecture Notes in Mathematics, vol. 1920, Springer, Berlin, 2005.
  • J.-F. Le Gall. Spatial Branching Processes, Random Snakes, and Partial Differential Equations. Birkhauser, Basel, 1999.
  • J.-F. Le Gall. Random trees and applications. Probability Surveys, vol. 2, pp. 245--311, 2005.
  • 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.
  • J. Pitman. Combinatorial Stochastic Processes. Lecture Notes in Mathematics, vol. 1975, Springer, Berlin, 2006.