Mixing Rates of Random Walks with Little Backtracking

Sebastian M. Cioabă, Peng Xu

Type: Other

Publication Date: 2015-01-01

Citations: 4

DOI: https://doi.org/10.1090/conm/655/13202

Abstract

Many regular graphs admit a natural partition of their edge set into cliques of the same order such that each vertex is contained in the same number of cliques. In this paper, we study the mixing rate of certain random walks on such graphs and we generalize previous results of Alon, Benjamini, Lubetzky and Sodin regarding the mixing rates of non-backtracking random walks on regular graphs.

Locations

Contemporary mathematics - American Mathematical Society - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Mixing Rates of Random Walks with Little Backtracking	2015	Sebastian M. Cioabă Peng Xu
+	Poisson approximation for non-backtracking random walks	2007	Noga Alon Eyal Lubetzky
+	Poisson approximation for non-backtracking random walks	2007	Noga Alon Eyal Lubetzky
+ PDF Chat	Non-Backtracking Random Walks and a Weighted Ihara’s Theorem	2016	Mark Kempton
+	Mixing time of random walks on graphs	2004	Min Chen Keith Briggs
+ PDF Chat	COMPARING MIXING TIMES ON SPARSE RANDOM GRAPHS	2017	Anna Ben-Hamou Eyal Lubetzky Yuval Peres
+	Comparing mixing times on sparse random graphs	2017	Anna Ben-Hamou Eyal Lubetzky Yuval Peres
+ PDF Chat	NON-BACKTRACKING RANDOM WALKS MIX FASTER	2007	Noga Alon Itaı Benjamini Eyal Lubetzky Sasha Sodin
+	Comparing mixing times on sparse random graphs	2018	Anna Ben-Hamou Eyal Lubetzky Yuval Peres
+ PDF Chat	Mixing times of random walks on dynamic configuration models	2018	Luca Avena Hakan Güldaş Remco van der Hofstad Frank den Hollander
+ PDF Chat	Poisson approximation for non-backtracking random walks	2009	Noga Alon Eyal Lubetzky
+	Cutoff for random walk on random graphs with a community structure	2022	Jonathan Hermon Anđela Šarković Perla Sousi
+	Non-backtracking random walks and a weighted Ihara's theorem	2016	Mark Kempton
+	Non-backtracking random walks and a weighted Ihara's theorem	2016	Mark Kempton
+ PDF Chat	Random walks on the random graph	2018	Nathanaël Berestycki Eyal Lubetzky Yuval Peres Allan Sly
+ PDF Chat	CUTOFF FOR NON-BACKTRACKING RANDOM WALKS ON SPARSE RANDOM GRAPHS	2015	Anna Ben-Hamou Justin Salez
+	Random walks on the random graph	2015	Nathanaël Berestycki Eyal Lubetzky Yuval Peres Allan Sly
+	Mixing times of random walks on dynamic configuration models	2016	Luca Avena Hakan Güldaş Remco van der Hofstad Frank den Hollander
+	Mixing times of random walks on dynamic configuration models	2016	Luca Avena Hakan Güldaş Remco van der Hofstad Frank den Hollander
+	Speeding up random walk mixing by starting from a uniform vertex	2022	Alberto Espuny Díaz Patrick Morris Guillem Perarnau Oriol Serra

Works That Cite This (4)

Action	Title	Year	Authors
+	Some observations on the smallest adjacency eigenvalue of a graph	2019	Sebastian M. Cioabă Randall J. Elzinga David A. Gregory
+ PDF Chat	Hitting times for second-order random walks	2022	Dario Fasino Arianna Tonetto Francesco Tudisco
+ PDF Chat	Spectra of Random Regular Hypergraphs	2021	Ioana Dumitriu Yizhe Zhu
+	Some observations on the smallest adjacency eigenvalue of a graph	2020	Sebastian M. Cioabă Randall J. Elzinga David A. Gregory

Works Cited by This (5)

Action	Title	Year	Authors
+	Spectra of Hypergraphs and Applications	1996	Keqin Feng Wen-Ching Winnie Li
+ PDF Chat	Poisson approximation for non-backtracking random walks	2009	Noga Alon Eyal Lubetzky
+ PDF Chat	NON-BACKTRACKING RANDOM WALKS MIX FASTER	2007	Noga Alon Itaı Benjamini Eyal Lubetzky Sasha Sodin
+ PDF Chat	Non-backtracking Random Walk	2013	Robert Fitzner Remco van der Hofstad
+	Spectral redemption in clustering sparse networks	2013	Florent Krząkała Cristopher Moore Elchanan Mossel Joe Neeman Allan Sly Lenka Zdeborová Pan Zhang