100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Louis Funar

Diameter and mixing time for random walks on planar graphs

Vendredi, 26 Octobre, 2012 - 12:30
Prénom de l'orateur : 
Juan
Nom de l'orateur : 
Souto
Résumé : 

he mixing time of an (irreducible) random walk on a finite graph measures how much time does it take to approximate the unique stationary measure. I will first give a lower bound in terms of the diameter for the mixing time of the simple random walk on a finite planar graph. Then I will construct examples showing that this bound is basically sharp. Both parts are based on the relation between the mixing time, the first eigenvalue of the Laplacian, and geometric considerations on surfaces homeomorphic to the sphere.
This is joint work with Lars Louder.

Institution de l'orateur : 
University of British Columbia, Vancouver
Thème de recherche : 
Topologie
Salle : 
04
logo uga logo cnrs