Seminar series
Date
Tue, 03 Mar 2026
Time
15:30 -
16:30
Location
Online
Speaker
Boris Bukh
Organisation
Carnegie Mellon Univeristy
Random walks on graphs can mix slowly. To speed it up, imagine that at each step instead of choosing the neighbor at random, there is a small probability $\varepsilon > 0$ that we can choose it. We show that in this case, at least for graphs of bounded degree, there is a way to steer the walk so that we visit every vertex in $n^{1+o(1)}$ many steps. The key to this result is a way to decompose arbitrary graphs into small-diameter pieces.
Further Information
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.