text: 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 @math is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on @math , scaled by the number of edges in @math . 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 @math for @math -vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).
  @cite_37: 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.
  @cite_45: We study the cover time of a random walk on the largest component of the random graph Gn,p. We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(lnn). In particular, we show that the cover time is not monotone for c = Θ(lnn). We also determine the cover time of the k-cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008
  @cite_22: LetT (x;") denote the rst hitting time of the disc of radius " centered at x for Brownian motion on the two dimensional torus T 2 . We prove that sup x2T2T (x;")=j log"j 2 ! 2= as " ! 0. The same applies to Brownian motion on any smooth, compact connected, two- dimensional, Riemannian manifold with unit area and no boundary. As a consequence, we prove a conjecture, due to Aldous (1989), that the number of steps it takes a simple random walk to cover all points of the lattice torus Z 2 is asymptotic to 4n 2 (logn) 2 = . Determining these asymptotics is an essential step toward analyzing the fractal structure of the set of uncovered sites before coverage is complete; so far, this structure was only studied non-rigorously in the physics literature. We also establish a conjecture, due to Kesten and R ev esz, that describes the asymptotics for the number of steps needed by simple random walk in Z 2 to cover the disc of radius n.
summary: Furthermore, for a few families of specific examples, the asymptotics of the cover time have been calculated more precisely. These include the work of Aldous @cite_37 for regular trees, Dembo, Peres, Rosen, and Zeitouni @cite_22 for the 2-dimensional discrete torus, and Cooper and Frieze @cite_45 for the giant component of various random graphs.