Answers are grounded in this paper and cite their sources.
Let G be a finite simple graph on n vertices with minimum degree m≥3 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². Hence the conjecture of Alon and Peres, that a non-backtracking walk of length C(ε)√ n self-intersects with probability at least 1-ε, holds with C(ε) depending only on ε and a bound for $M/m$; for regular graphs of degree at least three one may take C(ε)=31ε-1/2 for every degree. The expected self-intersection time is at most 32√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.
No takes yet. Share an insight, caveat, or question.
Yitzchak Shmalo (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: