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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A birthday bound for non-backtracking walks on graphs of bounded degree ratio

Yitzchak Shmalo
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

A birthday bound for non-backtracking walks on graphs of bounded degree ratio

Yitzchak Shmalo
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Hebrew University of Jerusalem (IL)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon