Laboratoire de Mathématiques Raphaël Salem

UMR 6085 CNRS - University of Rouen Normandy

Le temps de mélange d’une marche aléatoire sur un graphe connexe fini est intimement lié à la présence 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 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.