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.
Previous to our work, the only non-trivial examples for which has been verified are regular trees and the 2D torus. For regular trees, the asymptotics of cover times was shown in @cite_27 , while the supremum of the Gaussian free field was known as a folklore and a precise estimate up to an additive constant can be deduced by adapting Bramson's methods on the maximal displacement of branching Brownian motion @cite_31 . Indeed, an analogue of Bramson's result for a wide range of branching random walks was proved by Addario-Berry and Reed @cite_25 . For the 2D lattice, the asymptotics of the supremum of the Gaussian free field was determined in @cite_14 , and the asymptotics of cover times was established in @cite_16 . We emphasize that in both cases, the asymptotics of cover times was very tricky, despite the fact that the supremum of the GFFs had been established.
@cite_14 @cite_27 @cite_31 @cite_16 @cite_25
1979312416 2964051416 2760496220 2906272554
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. We consider the maximum of the discrete two-dimensional Gaussian free field (GFF) in a box and prove that its maximum, centered at its mean, is tight, settling a longstanding conjecture. The proof combines a recent observation by Bolthausen, Deuschel, and Zeitouni with elements from Bramson's results on branching Brownian motion and comparison theorems for Gaussian fields. An essential part of the argument is the precise evaluation, up to an error of order 1, of the expected value of the maximum of the GFF in a box. Related Gaussian fields, such as the GFF on a two-dimensional torus, are also discussed. © 2011 Wiley Periodicals, Inc. 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]. We consider a continuous time random walk on the rooted binary tree of depth @math with all transition rates equal to one and study its cover time, namely the time until all vertices of the tree have been visited. We prove that, normalized by @math and then centered by @math , the cover time admits a weak limit as the depth of the tree tends to infinity. The limiting distribution is identified as that of a Gumbel random variable with rate one, shifted randomly by the logarithm of the sum of the limits of the derivative martingales associated with two negatively correlated discrete Gaussian free fields on the infinite version of the tree. The existence of the limit and its overall form were conjectured in the literature. Our approach is quite different from those taken in earlier works on this subject and relies in great part on a comparison with the extremal landscape of the discrete Gaussian free field on the tree.