Cover times, blanket times, and majorizing measures

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

Yuval Peres, Jian Ding, James R. Lee

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability approximations via the Poisson clumping heuristic
• 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
• Gaussian Hilbert Spaces
• 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
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Majorizing measures: The generic chaining
• 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
• 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
• Multiple cover time
• A Technique for Lower Bounding the Cover Time

Cited In (52)

• Statistical physics and random surfaces. Abstracts from the workshop held May 12--17, 2024
• Linear cover time is exponentially unlikely
• Thick points of random walk and the Gaussian free field
• On the Cover Time of the Emerging Giant
• Covering a compact space by fixed-radius or growing random balls
• Extrema of the Two-Dimensional Discrete Gaussian Free Field
• 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
• Convergence of blanket times for sequences of random walks on critical random graphs
• Cover Times and Generic Chaining
• 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
• 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
• Dynkin isomorphism theorems revisited
• Cover times for sequences of reversible Markov chains on random graphs
• New Bounds for Edge-Cover by Random Walk
• Geometric structures of late points of a two-dimensional simple random walk
• Bounds on the cover time
• Cover and hitting times of hyperbolic random graphs
• Multiple random walks on graphs: mixing few to cover many
• On the Cover Time of Dense Graphs
• A spectral characterization for concentration of the cover time
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• 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
• 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
• 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
• A Ray-Knight theorem for \(\nabla \phi\) interface models and scaling limits
• Extremes of local times for simple random walks on symmetric trees
• Isomorphism Theorems: Markov Processes, Gaussian Processes and Beyond
• Tightness for the cover time of the two dimensional sphere

Recommendations

• Cover times, blanket times, and majorizing measures 👍 👎
• Bounds on the cover time 👍 👎
• A spectral characterization for concentration of the cover time 👍 👎
• Deterministic approximation of the cover time 👍 👎
• Cover Times and Generic Chaining 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)