Cover times of graphs, majorizing measures, and the Gaussian free field
Seminar Room 1, Newton Institute
The cover time of a finite graph (the expected time for the simple random walk to visit all the vertices) has been extensively studied, yet a number of fundamental questions have remained open. We present a connection between the cover time, the discrete Gaussian free field on the underlying graph, and the Fernique-Talagrand theory of majorizing measures. At its most basic level, this involves embedding the graph into Euclidean space via the effective resistance, and then studying the associated Gaussian process (the image points under random projection) using the geometry of the resistance metric, in combination with Talagrand's ultrametric interpretation of majorizing measures.
This allows us resolve a number of open questions. Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution if 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. Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to an O(1) factor. The best approximation factor found so far for both these problems was (log log n)^2 for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000). We use the aforementioned connection to deduce a positive answer to the question of Aldous and Fill and to establish the conjecture of Winkler and Zuckerman. These results extend to arbitrary reversible finite Markov chains
This is joint work with Jian Ding (U. C. Berkeley) and Yuval Peres (Microsoft Research).