{"id":"arxiv/2605.18712","url":"https://arxiv.org/abs/2605.18712","tags":["math.PR","math.CO"],"score":0,"title":"Faster random walks via infrequent steering","domain":"math.PR","source":"arxiv","authors":["Boris Bukh","Quentin Dubroff"],"reviews":0,"subject":"math.PR","summary":"Random walks on graphs can be slow. To speed them 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 it visits every vertex in $n^{1+o(1)}$ steps with high probability. The key to this result is a way to decompose arbitrary graphs into small-diameter pieces.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-18","reactions":{}}