On the universality of fluctuations for the cover time

ESB 4127

What is the structure of the set of the last few points visited by a random walk on a graph? We show that on vertex-transitive graphs of bounded degree, this set is decorrelated (it is close to a product measure in total variation) if and only if a simple geometric condition on the diameter of the graph holds. In this case, the cover time has universal fluctuations: properly scaled, this time converges to a Gumbel distribution. To prove this result we rely on recent progress in geometric group theory (about quantitative versions of Gromov's Theorem for finite vertex-transitive graphs) and we prove refined quantitative estimates showing that the hitting time of a small set of vertices is typically approximately an exponential random variable. This talk is based on joint work with Nathanaël Berestycki and Lucas Teyssier.