PS : Anna Ben Hamou (Sorbonne Université) : Temps de mélange pour la marche aléatoire sans rebroussement sur des graphes aléatoires à communautés

Chargement Évènements

« Tous les Évènements

  • Cet évènement est passé

PS : Anna Ben Hamou (Sorbonne Université) : Temps de mélange pour la marche aléatoire sans rebroussement sur des graphes aléatoires à communautés

6 novembre 2018 / 11:30 - 12:30

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 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.

PS : Anna Ben Hamou (Sorbonne Université) : Temps de mélange pour la marche aléatoire sans rebroussement sur des graphes aléatoires à communautés

Détails

Date :
6 novembre 2018
Heure :
11:30 - 12:30
Catégorie d’évènement:

Lieu

Bâtiment Fermat, salle 2107

Organisateurs

Alexis Devulder
Julien Worms