On the self-intersection time of non-backtracking random walks

Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen, Mark Jerrum, Gabor Pete, Guus Regts, Yitong Yin

arXivarxiv/2608.09729Aug 10, 2026math.PRscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.09729
curl -X POST /api/v1/records/arxiv/2608.09729/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.09729/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'