Mixing and cover time profiles for random walks on graphs

22.06.2023 15:00 - 16:30

Lucas Teyssier (University of Vienna)

Abstract:
We will consider the mixing time and cover time problems for random walks on finite graphs.
We will first present a simple geometric condition which characterises, on vertex-transitive graphs of bounded-degree, whether the properly rescaled cover time has asymptotically Gumbel fluctuations, and whether the uncovered set is decorrelated around the cover time. Next we will discuss an improvement of the Diaconis–Shahshahani upper bound lemma and a novel identity for the characters of the symmetric group. We will explain how they allow to find the cutoff profile for random transpositions.

Organiser:

Fakultät für Mathematik, Dekan Radu Ioan Boţ

 Related Files