Id: arxiv/2608.09729 Url: https://arxiv.org/abs/2608.09729 Tags: math.PR, cs.DS, math.CO Score: 0 Title: On the self-intersection time of non-backtracking random walks Domain: math.PR Source: arxiv Authors: Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen, Mark Jerrum, Gabor Pete, Guus Regts, Yitong Yin Reviews: 0 Subject: math.PR Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-10 Page: https://delphi.science/r/arxiv/2608.09729 We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $Δ\geq 3$ we show that the expected self-intersection time is $O(\sqrt{n} \log n)$ on $n$-vertex graphs with minimum degree at least $3$ and maximum degree at most $Δ$. For regular graphs with a uniform spectral gap, we improve this to $O(\sqrt{n})$. We also show an $Ω(\sqrt{n})$ lower bound on a class of regular expanders. Our upper bound on the expected self-intersection time implies an improved mixing time bound on Glauber dynamics for the Ising model on $Δ$-regular…