Anna Ben-Hamou.Temps de mélange de marches aléatoires sur des graphes aléatoires à communautés

schedule le mardi 27 novembre 2018 de 14h00 à 15h00

Organisé par : LPSM

Intervenant : Anna Ben-Hamou (LPSM -Sorbonne Université.)
Lieu : Campus Jussieu, Tours-16-26, 2ème, Salle 209.

Sujet : A. Ben-Hamou: Temps de mélange de marches aléatoires sur des graphes aléatoires à communautés

Résumé :

Le temps de mélange d’une marche aléatoire sur un graphe connexe fini est intimement lié à l’existence de goulots d’étranglement (« bottlenecks ») dans le graphe: intuitivement, plus il est difficile pour la marche de s’échapper de certaines régions du graphe, plus le mélange est lent. De plus, la présence de goulots d’étranglement étroits empêche souvent le phénomène de cutoff, qui décrit une convergence abrupte à l’équilibre. Dans cet exposé, nous nous intéresserons au comportement de mélange de la marche aléatoire sans rebroussement sur des graphes aléatoires à degrés prescrits et avec une structure en deux communautés. De tels graphes possèdent un goulot d’étranglement dont l’étroitesse peut être mesurée par la fraction des arêtes qui vont d’une communauté à l’autre. Sous certaines conditions de degrés, nous montrerons que si cette fraction décroit moins vite que 1/log(N) (où N est la taille du graphe), alors la marche présente le cutoff, et la distance à l’équilibre peut être décrite très précisément. Inversement, si cette fraction décroit plus vite que 1/log(N), alors il n’y a pas cutoff.