Cover times, blanket times, and majorizing measures

DOI10.4007/ANNALS.2012.175.3.8zbMATH Open1250.05098arXiv1004.4371OpenAlexW2019415463MaRDI QIDQ431644FDOQ431644

Authors: Jian Ding, James R. Lee, Yuval Peres 

Publication date: 29 June 2012

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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$. This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an O(1) factor for any graph, answering a question of Aldous and Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph, the blanket and cover times are within an O(1) factor. The best previous approximation factor for both these problems was $O((loglogn{)}^2)$ for $n$-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).

Full work available at URL: https://arxiv.org/abs/1004.4371

Recommendations

• Cover times, blanket times, and majorizing measures
• Bounds on the cover time
• Cover times and generic chaining
• scientific article; zbMATH DE number 3889840
• A spectral characterization for concentration of the cover time
• scientific article; zbMATH DE number 878356
• Publication:4945268
• Deterministic approximation of the cover time
• Publication:4735857

zbMATH Keywords

random walksGaussian free fieldeffective resistancemajorizing measurescover timescommute timesDynkin isomorphism

Mathematics Subject Classification ID

Gaussian processes (60G15) Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81) Local time and additive functionals (60J55)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Probability approximations via the Poisson clumping heuristic
• Title not available (Why is that?)
• Random walks, capacity and percolation on trees
• The concentration of measure phenomenon
• The Generic Chaining
• Probability on trees and networks
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• Title not available (Why is that?)
• Gaussian Hilbert Spaces
• Title not available (Why is that?)
• Matrix multiplication via arithmetic progressions
• Cover times for Brownian motion and random walks in two dimensions
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Chernoff's theorem in the branching random walk
• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• Markov Processes, Gaussian Processes, and Local Times
• Title not available (Why is that?)
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Majorizing measures: The generic chaining
• Title not available (Why is that?)
• Regularity of Gaussian processes
• Random walks and the effective resistance of networks
• Random walk covering of some special trees
• Threshold limits for cover times
• Majorizing measures without measures
• Gaussian and non-Gaussian random fields associated with Markov processes
• Régularité de processus gaussiens
• The evolution of the cover time
• Covering problems for Markov chains
• Title not available (Why is that?)
• Markov chains with almost exponential hitting times
• The electrical resistance of a graph captures its commute and cover times
• The cover time of the giant component of a random graph
• Sojourn times of diffusion processes
• Random Walks and A Sojourn Density Process of Brownian Motion
• A Ray-Knight theorem for symmetric Markov processes.
• Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes
• On the cover time of planar graphs
• Bounds on the cover time
• On the cover time of random walks on graphs
• Title not available (Why is that?)
• Algorithms, graph theory, and linear equations in Laplacian matrices
• Multiple cover time
• Title not available (Why is that?)
• A Technique for Lower Bounding the Cover Time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (55)

• Dynkin isomorphism theorems revisited
• Cover and hitting times of hyperbolic random graphs
• Statistical physics and random surfaces. Abstracts from the workshop held May 12--17, 2024
• A Ray-Knight theorem for \(\nabla \phi\) interface models and scaling limits
• Linear cover time is exponentially unlikely
• On the cover time of dense graphs
• The evolution of the cover time
• Thick points of random walk and the Gaussian free field
• Covering a compact space by fixed-radius or growing random balls
• Brownian motion on graph-like spaces
• Out-of-equilibrium random walks
• Avoided points of two-dimensional random walks
• A polynomial time approximation scheme for computing the supremum of Gaussian processes
• A scaling limit for the cover time of the binary tree
• Maxima of branching random walks with piecewise constant variance
• Cover times, blanket times, and majorizing measures
• Convergence of blanket times for sequences of random walks on critical random graphs
• On the cover time of \(\lambda\)-biased walk on supercritical Galton-Watson trees
• Modulus metrics on networks
• Title not available (Why is that?)
• Exponential concentration of cover times
• Mixing time bounds via bottleneck sequences
• Geometry of the Gibbs measure for the discrete 2D Gaussian free field with scale-dependent variance
• Exceptional points of two-dimensional random walks at multiples of the cover time
• Inverting Ray-Knight identity
• Divide and color representations for threshold Gaussian and stable vectors
• On the cover time of the emerging giant
• Extreme values for two-dimensional discrete Gaussian free field
• Properties of the gradient squared of the discrete Gaussian free field
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Limit law for the cover time of a random walk on a binary tree
• Second-order term of cover time for planar simple random walk
• Cover times for sequences of reversible Markov chains on random graphs
• Geometric structures of late points of a two-dimensional simple random walk
• Bounds on the cover time
• Cover times and generic chaining
• Multiple random walks on graphs: mixing few to cover many
• A spectral characterization for concentration of the cover time
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• Isomorphism theorems: Markov processes, Gaussian processes and beyond
• The Cover Time of Cartesian Product Graphs
• Exponents for the number of pairs of \(\alpha \)-favorite points of a simple random walk in \(\mathbb{Z}^2\)
• Sandwich theorem of cover times
• Extrema of the two-dimensional discrete Gaussian free field
• Effective resistances for supercritical percolation clusters in boxes
• The geometry of random walk isomorphism theorems
• Extreme local extrema of two-dimensional discrete Gaussian free field
• On uniform closeness of local times of Markov chains and i.i.d. sequences
• New bounds for edge-cover by random walk
• The power of two choices for random walks
• A comparison principle for random walk on dynamical percolation
• The free uniform spanning forest is disconnected in some virtually free groups, depending on the generator set
• Extremes of local times for simple random walks on symmetric trees
• Improved approximation of the minimum cover time
• Tightness for the cover time of the two dimensional sphere

This page was built for publication: Cover times, blanket times, and majorizing measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q431644)