We prove that for a sequence of finite vertex-transitive graphs of increasing sizes, the cover times are asymptotically concentrated iff the product of the spectral-gap and the expected cover time diverges. In fact, we prove this for general reversible Markov chains under the much weaker assumptions (than transitivity) that the maximal hitting time of a state is comparable to the average hitting time of a state and that the maximal stationary probability of a state vanishes.
Cover times have been studied extensively for over 35 years. This is a topic with rich ties to other objects such as the Gaussian free field @cite_22 . There has been many works providing general bounds on the cover time, studying its evolution and its fluctuations in general @cite_3 @cite_26 @cite_7 @cite_10 @cite_5 , and in particular for the giant component of various random graphs @cite_16 , for trees @cite_20 @cite_1 , for the two dimensional torus @cite_24 @cite_23 @cite_8 @cite_13 and for higher dimensional tori @cite_0 . Feige @cite_18 @cite_12 proved tight extremal upper and lower bounds on cover times of graphs (by SRW). For a more comprehensive review of the literature see the related work section in @cite_22 and the references therein. For background on mixing, hitting times and cover times see @cite_21 @cite_19 .
@cite_13 @cite_18 @cite_26 @cite_22 @cite_7 @cite_8 @cite_21 @cite_1 @cite_3 @cite_24 @cite_0 @cite_19 @cite_23 @cite_5 @cite_16 @cite_10 @cite_12 @cite_20
2057596055 2760496220 1979312416 1971599265
The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovasz and Vu [25] yielded a (log logn)2 polynomial time approximation. We refine the upper bound of [25], and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdős–Renyi random graph G(n, c n) in the supercritical regime with c > 1 fixed, is asymptotic to ϕ(c)nlog2n, where ϕ(c) → 1 as c ↓ 1. However, our new bound implies that the cover time for the critical Erdős–Renyi random graph G(n, 1 n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube 0, 1 n, on high-girth expanders, and on tori ℤdn for fixed large d. This approach also gives a simpler proof of a result of Aldous [2] that the cover time of a uniform labelled tree on k vertices is of order k3 2. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman [45], is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4. We consider the cover time for a simple random walk on the two-dimensional discrete torus of side length @math . Dembo, Peres, Rosen, and Zeitouni [Ann. Math. 160:433-464, 2004] identified the leading term in the asymptotics for the cover time as @math goes to infinity. In this paper, we study the exact second order term. This is a discrete analogue of the work on the cover time for planar Brownian motion by Belius and Kistler [Probab. Theory Relat Fields. 167:461-552, 2017]. In this paper we show that on bounded degree graphs and general trees, the cover time of the simple random walk is asymptotically equal to the product of the number of edges and the square of the expected supremum of the Gaussian free field on the graph, assuming that the maximal hitting time is significantly smaller than the cover time. Previously, this was only proved for regular trees and the 2D lattice. Furthermore, for general trees, we derive exponential concentration for the cover time, which implies that the standard deviation of the cover time is bounded by the geometric mean of the cover time and the maximal hitting time. Abstract For simple random walk on a finite tree, the cover time is the time taken to visit every vertex. For the balanced b-ary tree of height m, the cover time is shown to be asymptotic to 2m 2 b m + 1 ( log b) (b − 1) as m → ∞ . On the uniform random labeled tree on n vertices, we give a convincing heuristic argument that the mean time to cover and return to the root is asymptotic to 6(2π) 1 2 n 3 2 , and prove a weak O(n 3 2 ) upper bound. The argument rests upon a recursive formula for cover time of trees generated by a simple branching process.