Bounded Cutoff Window for the Non-backtracking Random Walk on Ramanujan Graphs

Evita Nestoridi, Peter Sarnak

Type: Article

Publication Date: 2023-04-01

Citations: 0

DOI: https://doi.org/10.1007/s00493-023-00017-8

Abstract

We prove that the non-backtracking random walk on Ramanujan graphs with large girth exhibits the fastest possible cutoff with a bounded window.

Locations

COMBINATORICA - View
arXiv (Cornell University) - View - PDF
COMBINATORICA - View
arXiv (Cornell University) - View - PDF
COMBINATORICA - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Bounded cutoff window for the non-backtracking random walk on Ramanujan Graphs	2021	Evita Nestoridi Peter Sarnak
+ PDF Chat	Cutoff phenomena for random walks on random regular graphs	2010	Eyal Lubetzky Allan Sly
+	Kemeny's constant for non-backtracking random walks	2022	Jane Breen Nolan Faught Cory Glover Mark Kempton Adam Knudson Alice Oveson
+	An axiomatic approach to the cut-off phenomenon for random walks on large distance-regular graphs	2000	Akihito Hora
+	Universality of cutoff for random walks on random Cayley graphs	2020	Samuel Thomas
+ PDF	Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs	2018	Charles Bordenave Marc Lelarge Laurent Massoulié
+	Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs	2015	Charles Bordenave Marc Lelarge Laurent Massoulié
+ PDF Chat	Cutoff on all Ramanujan graphs	2016	Eyal Lubetzky Yuval Peres
+ PDF Chat	NON-BACKTRACKING RANDOM WALKS MIX FASTER	2007	Noga Alon Itaï Benjamini Eyal Lubetzky Sasha Sodin
+ PDF Chat	Universality of cutoff for graphs with an added random matching	2022	Jonathan Hermon Allan Sly Perla Sousi
+ PDF Chat	Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs	2015	Charles Bordenave Marc Lelarge Laurent Massoulié
+	Universality of cutoff for graphs with an added random matching	2020	Jonathan Hermon Allan Sly Perla Sousi
+ PDF Chat	Kemeny's constant for nonbacktracking random walks	2023	Jane Breen Nolan Faught Cory Glover Mark Kempton Adam Knudson Alice Oveson
+	Mixing Rates of Random Walks with Little Backtracking	2015	Sebastian M. Cioabă Peng Xu
+ PDF Chat	Mixing Rates of Random Walks with Little Backtracking	2015	Sebastian M. Cioabă Peng Xu
+	Cycle density in infinite Ramanujan graphs	2015	Russell Lyons Yuval Peres
+	A Note on the Trace Method for Random Regular Graphs	2020	Joel Friedman Doron Puder
+	A note on the trace method for random regular graphs	2023	Joel Friedman Doron Puder
+	Random Walks on Distance-Regular Graphs	1990	Michihiko Hashizume Koji Ichihara
+	Cutoff for random walks on graphs with bottlenecks	2016	Ioannis Papageorgiou

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (29)

Action	Title	Year	Authors
+ PDF	Zeta Functions of Finite Graphs and Representations of $p$-Adic Groups	2018	Ki-ichiro Hashimoto
+ PDF	Non-Backtracking Random Walks and Cogrowth of Graphs	2007	Ronald Ortner Wolfgang Woess
+ PDF	None	1992	Martin Hildebrand
+ PDF Chat	Cutoff phenomena for random walks on random regular graphs	2010	Eyal Lubetzky Allan Sly
+	The diameter of random regular graphs	1982	Béla Bollobás W. Fernandez de la Véga
+ PDF	Trailing the Dovetail Shuffle to its Lair	1992	Dave Bayer Persi Diaconis
+ PDF	An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian	1994	Fan Chung Vance Faber Thomas A. Manteuffel
+	Cutoff for Ramanujan graphs via degree inflation	2017	Jonathan Hermon
+ PDF	Cutoff on Ramanujan complexes and classical groups	2022	Michael Chapman Ori Parzanchevski
+	Cutoff on Graphs and the Sarnak-Xue Density of Eigenvalues.	2019	Konstantin Golubev Amitay Kamber