The Birthday Paradox for non-backtracking walks on regular graphs

Abstract

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.

arXiv comment9 pages, 1 figure, 2 ancillary Lean files