On The Cover Time of Random Walks on Graphs

How long does it take for a random walk to cover all the vertices of a graph?

And what is the structure of the uncovered set (the set of points not yet visited by the walk) close to the cover time?

We completely characterize the vertex-transitive graphs of bounded degree for which the cover time is in the Gumbel universality class. Surprisingly our characterization is in terms of a simple global geometric condition; this is furthermore equivalent to the decorrelation of the uncovered set at a time (in the sense that it is close to a product measure).

To prove this result we rely on recent breakthroughs in geometric group theory which give a quantitative form of Gromov's theorem on groups of polynomial growth. We also prove along the way optimal quantitative estimates giving an exponential approximation for hitting time of sets of vertices (irrespective of their geometry).

Joint work with Jonathan Hermon (UBC) and Lucas Teyssier (Vienna).