Cours introductif (Pro)

Introduction aux graphes aléatoires

Bénédicte Haas

Contact : haas à math.univ-paris13.fr

Pas de notes de cours prévues.

Langue du cours : Français

Présentation

Ce cours est une introduction à la théorie des graphes aléatoires et à l'étude de leurs structures asymptotiques. Le sujet est vaste et nous nous concentrerons essentiellement sur deux modèles classiques -- les arbres de Galton-Watson et le graphe d'Erdös-Rényi -- afin d'illustrer des résultats et techniques variés. On abordera notamment dans ce contexte les notions de transition de phase, limite locale, construction algorithmique et limite d'échelle.

Contenu

• Boîte à outils : Rappels et compléments de probabilités
• Arbres de Galton-Watson : transition de phase, limite locale
• Arbres de Galton-Watson : exemples de construction algorithmique, notion de limite d'échelle et un premier pas vers l'arbre brownien
• Graphe d'Erdös-Renyi : limite locale, transition de phase
• Graphe d'Erdös-Renyi : composantes connexes à grande échelle et connectivité
• Pour aller plus loin : quelques autres modèles de graphes aléatoires

Prérequis

Bibliographie

• Alan Frieze and Michal Karonski. Introduction to Random Graphs.
• Christina Goldschmidt. Scaling limits of random trees and critical random graphs.
• Jean-Francois Le Gall. Random Trees and Applications.
• Russell Lyons and Yuval Peres. Probability on trees and networks.
• Remco van der Hofstad. Random Graphs and Complex Networks.