Non-Backtracking Walks Reach Collisions Near the Square-Root Scale
Expected self-intersection time is O(√n log n) on bounded-degree graphs and O(√n) for regular graphs with a uniform spectral gap.
Aug 11, 20263 min2608.09729
2 articles on SOTA Papers
Expected self-intersection time is O(√n log n) on bounded-degree graphs and O(√n) for regular graphs with a uniform spectral gap.
A regularity-and-entropy proof shows dense graphs with minimum degree 2n/3 keep triangle factors when p ≥ C(log n)^(1/3)n^(-2/3).
