Linear cover time is exponentially unlikely

Itaı Benjamini, Ori Gurel-Gurevich, Ben Morris

Type: Article

Publication Date: 2011-12-05

Citations: 5

DOI: https://doi.org/10.1007/s00440-011-0403-2

View Publication

Download PDF

Locations

Probability Theory and Related Fields - View - PDF

Similar Works

Action	Title	Year	Authors
+	Linear Cover Time is Exponentially Unlikely	2010	Itaı Benjamini Ori Gurel-Gurevich Ben Morris
+	Linear cover time is exponentially unlikely	2021	Quentin Dubroff Jeff Kahn
+	Linear cover time is exponentially unlikely	2021	Quentin Dubroff Jeff Kahn
+	Linear cover time for trees is exponentially unlikely.	2012	Amir Yehudayoff
+	How to Design a Linear Cover Time Random Walk on a Finite Graph	2009	Yoshiaki Nonaka Hirotaka Ono Kunihiko Sadakane Masafumi Yamashita
+	Cover times of random walks on finite graphs	2010	拓也大輪
+	Pairwise Independent Random Walks Can Be Slightly Unbounded.	2018	Shyam Narayanan
+	On the probability that a random subgraph contains a circuit	2015	Peter Nelson
+	On the probability that a random subgraph contains a circuit	2015	Peter Nelson
+ PDF Chat	On the Probability that a Random Subgraph Contains a Circuit	2016	Peter Nelson
+	How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)	2008	Chen Avin Michal Koucký Zvi Lotker
+ PDF Chat	On the cover time of random walks on graphs	1989	Jeff D. Kahn Nathan Linial Noam Nisan Michael Saks
+	Linear Random Walks	2016	Yves Benoist Jean-François Quint
+	Random graphs	2010	Béla Bollobás
+	Random walks on regular trees can not be slowed down	2023	Omer Angel Jacob Richey Yinon Spinka Amir Yehudayoff
+	Simple random walks	2022	Lydia Novozhilova Robert Dolan
+	Simple random walks	1995	Henry C. Tuckwell
+	Simple random walks	1988	Henry C. Tuckwell
+	Simple random walks	2017
+ PDF Chat	Linear Probing and Graphs	1998	Donald E. Knuth

Works That Cite This (4)

Action	Title	Year	Authors
+ PDF Chat	Greedy Random Walk	2013	Tal Orenshtein Igor Shinkar
+	Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees	2014	Jian Ding
+ PDF Chat	On large deviations for the cover time of two-dimensional torus	2013	Francis Comets Christophe Gallesco Serguei Popov Marina Vachkovskaia
+	Linear cover time is exponentially unlikely	2021	Quentin Dubroff Jeff Kahn

Works Cited by This (4)

Action	Title	Year	Authors
+	Reversible Markov Chains and Random Walks on Graphs	2014	David Aldous James Allen Fill
+	A random graph	1981	Sheldon M. Ross
+	Threshold limits for cover times	1991	David Aldous
+	A Technique for Lower Bounding the Cover Time	1992	David Zuckerman