{"id":"arxiv/2608.26321","url":"https://arxiv.org/abs/2608.26321","tags":["math.CO","math.DS","math.PR"],"score":0,"title":"The Birthday Paradox for non-backtracking walks on regular graphs","domain":"math.CO","source":"arxiv","authors":["Benjamin Dozier"],"reviews":0,"subject":"math.CO","summary":"We show a birthday paradox for random non-backtracking walk on regular graphs of degree at least $3$: such a walk of length $k$ has high probability of self-intersecting when $k$ is significantly greater than $\\sqrt n$, where $n$ is the number of vertices of the graph. This resolves a conjecture of Noga Alon and Yuval Peres for the fixed degree case.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-26","reactions":{}}