{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}