Date/heure
5 novembre 2020
10:45 - 11:45
Oratrice ou orateur
Anna Ben-Hamou
Catégorie d'évènement Séminaire Probabilités et Statistique
Résumé
Le temps de mélange d’une marche aléatoire sur un graphe est étroitement lié à l’existence de « goulots d’étranglement » dans le graphe : intuitivement, plus il est difficile pour la marche de s’échapper de certains sous-ensembles, plus la marche met du temps à mélanger. Plusieurs résultats montrent que, sur des graphes aléatoires qui sont presque sà»rement des expanseurs et donc n’ont typiquement pas de goulots d’étranglement (par exemple, sur des graphes réguliers uniformes), la marche aléatoire mélange non seulement vite mais de façon très abrupte (on dit qu’elle présente le phénomène de cutoff). Dans cet exposé, nous verrons que l’on peut aussi obtenir des résultats similaires sur des graphes qui ne sont typiquement pas des expanseurs. Nous considérerons des graphes aléatoires munis d’une structure à deux communautés et montrerons qu’il existe un seuil pour la fraction d’arêtes inter-blocs autour duquel la marche bascule d’un régime de mélange rapide avec cutoff à un régime de mélange lent sans cutoff.