A birthday bound for non-backtracking walks on graphs of bounded degree ratio
Let $G$ be a finite simple graph on $n$ vertices with minimum degree $m\ge3$ and maximum degree $M$, and put $Q=M/(m-1)$. A non-backtracking random walk of length $k$ on $G$, started along any directed edge, is vertex-simple with probability at most $256\,Q(1+Q)\,n/k^2$. Hence the conjecture of Alon and Peres, that a non-backtracking walk of length $C(\varepsilon)\sqrt n$ self-intersects with probability at least $1-\varepsilon$, holds with $C(\varepsilon)$ depending only on $\varepsilon$ and a bound for $M/m$; for regular graphs of degree at least three one may take $C(\varepsilon)=31\varepsilon^{-1/2}$ for every degree. The expected self-intersection time is at most $32\sqrt{Q(1+Q)n}+2$, which removes the logarithmic factor from the bound of Bencs et al.\ for graphs of minimum degree at least three and bounded maximum degree. The proof adapts Dozier's argument for regular graphs: departures are weighted by the inverse branching at their vertex, and the deviating local derangement is resampled.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24189685
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint