Cover Time of Random Walk on General Graphs
Posed by Peter Winkler, David Zuckerman (1996)
§ Problem Statement
§ Discussion
§ Significance & Implications
§ Known Partial Results
§ References
Cover times, blanket times, and majorizing measures
Jian Ding, James R. Lee, Yuval Peres (2012)
Annals of Mathematics
📍 Section 1 (Introduction), Conjecture 1.1 (“The blanket time,” attributed to Winkler–Zuckerman 1996), p. 1411 (related open algorithmic question: Question 1.2, p. 1411).
Multiple cover time
Peter Winkler, David Zuckerman (1996)
Random Structures & Algorithms
📍 Section 4 (Blanket time), Conjecture 4.1 (blanket time is Θ(cover time) for all finite connected graphs), p. 409.
Cover times for Brownian motion and random walks in two dimensions
Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni (2004)
Annals of Mathematics
📍 Section 1 (Introduction), Theorem 1.1 (precise asymptotics for planar cover time), p. 434.