Cover times, blanket times, and majorizing measures

2012/04/09 by Jian Ding, James C. Lee, Yuval Peres · 1 citation
Mathematics · #Markov Chains and Monte Carlo Methods #Graph theory and applications #Limits and Structures in Graph Theory #Gaussian free field #Mathematics #Cover (algebra) #Combinatorics #Blanket #Gaussian #Graph #Connection (principal bundle) #Time complexity #Discrete mathematics #Geometry #Physics

paper · pdf · doi:10.4007/annals.2012.175.3.8

openalex publication_date 2012/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph G is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on G, scaled by the number of edges in G.

Citations

• Deterministic approximation for the cover time of trees
• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• A tight upper bound on the cover time for random walks on graphs

Cited by

• New Bounds for Edge-Cover by Random Walk
• Gaussian free field [wikipedia]