Cover times, blanket times, and the Gaussian free field

Yuval Peres előadásának absztraktja

2011. június 7. kedd (!!), 16:15

 
 

The cover time of a finite graph G (the expected time for simple random walk to visit all vertices) has been extensively studied, yet a number of fundamental questions concerning cover times have remained open: Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to a constant factor; Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution of the walk is within a factor of 2, say, of the stationary distribution) and conjectured that the blanket time is always within O(1) of the cover time. The best approximation factor found earlier for both these problems was (log log n)^2 for n-vertex graphs, due to Kahn, Kim, Lovász, and Vu (2000). We show that the cover time of G, normalized by the number of edges, is equivalent (up to a universal constant) to the square of the expected maximum of the Gaussian free field on G. We use this connection  and Talagrand's majorizing measure theory to deduce positive answers to the questions of Aldous-Fill and Winkler-Zuckerman. No prior knowledge of Talagrand's theory or of cover times will be assumed.

Joint work with Jian Ding and James Lee.


 
Balázs Márton, 2011.05.26