Linear cover time is exponentially unlikely

Quentin Dubroff, Jeff Kahn

Type: Preprint

Publication Date: 2021-09-02

Citations: 0

Locations

The Annals of Probability - View
arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Linear cover time is exponentially unlikely	2021	Quentin Dubroff Jeff Kahn
+	Linear Cover Time is Exponentially Unlikely	2010	Itaı Benjamini Ori Gurel-Gurevich Ben Morris
+ PDF Chat	Linear cover time is exponentially unlikely	2011	Itaı Benjamini Ori Gurel-Gurevich Ben Morris
+	Linear cover time for trees is exponentially unlikely.	2012	Amir Yehudayoff
+	On Necessary Conditions of Linear Cover Time Random Walks	2008	Yoshiaki Nonaka Ono Hirotaka Kunihiko Sadakane Yamashita Masafumi
+ PDF Chat	Linear Probing and Graphs	1998	Donald E. Knuth
+	Pairwise Independent Random Walks Can Be Slightly Unbounded.	2018	Shyam Narayanan
+	Linear colouring of binomial random graphs	2024	Austin Eide Paweł Prałat
+ PDF Chat	Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process	2021	Patrick Bennett Ryan Cushman Andrzej Dudek
+	The linear arboricity of $10$-regular graphs	1986	Filip Guldan
+	Upper bound for linear arboricity	1991	Paul C. Kainen
+ PDF Chat	Optimal Hamilton covers and linear arboricity for random graphs	2025	Nemanja Draganić Stefan Glock David Munhá Correia Benny Sudakov
+ PDF Chat	Counting Small Induced Subgraphs: Hardness via Fourier Analysis	2025	Radu Curticapean Daniel Neuen
+ PDF Chat	The Cover Time of Deterministic Random Walks	2010	Tobias Friedrich Thomas Sauerwald
+	Cycles Embedded in Linear Time	2019	Brandon lerma
+	Counting independent sets in graphs with bounded bipartite pathwidth	2018	Martin J.S. Dyer Catherine Greenhill Haiko Müller
+	Linear Random Walks	2016	Yves Benoist Jean-François Quint
+	Supporting the Collatz Conjecture Through a Simple Probabilistic Heuristic	2024	Shreyansh Jaiswal
+	Induced subgraph density. V. All paths approach Erdos-Hajnal	2023	Tung Nguyen Alex Scott Paul Seymour
+	Light spanners and sparse pseudo-random graphs	2003	Papa A. Sissokho Michelangelo Grigni Vojtěch Rödl

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (9)

Action	Title	Year	Authors
+	Random Walks on Graphs: A Survey	2001	László Lovász
+ PDF Chat	Linear cover time is exponentially unlikely	2011	Itaı Benjamini Ori Gurel-Gurevich Ben Morris
+	Asymptotically Good List-Colorings	1996	Jeff Kahn
+	Lower bounds for covering times for reversible Markov chains and random walks on graphs	1989	David Aldous
+	A Chernoff Bound for Random Walks on Expander Graphs	1998	David Gillman
+	Linear cover time for trees is exponentially unlikely.	2012	Amir Yehudayoff
+	Exponential concentration of cover times	2018	Alex Zhai
+	Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees	2014	Jian Ding
+ PDF Chat	Cover times, blanket times, and majorizing measures	2012	Jian Ding James C. Lee Yuval Peres