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 lattice version of the free eld in two dimensions (also called harmonic crystal). The main aim of the paper is to discuss quantitatively the entropic repulsion of the random surface in the presence of a hard wall. The basic ingredient of the proof is the analysis of the maximum of the eld which requires a multiscale analysis reducing the problem essentially to a problem on a eld with a tree structure. 2000 MSC: 60K35, 60G15, 82B41 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. It is shown that the position of any fixed percentile of the maximal displacement of standard branching Brownian motion in one dimension is 21 2t–3 · 2−3 2 log t + O(1) at time t, the second-order term having been previously unknown. This determines (to within O(1)) the position of the travelling wave of the semilinear heat equation, ut =1 2uxx +f(u), in the classic paper by Kolmogorov-Petrovsky-Piscounov, “Etude de l'equations de la diffusion avec croissance de la quantite de la matiere et son application a un probleme biologique”, 1937. 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. Given a branching random walk, let @math be the minimum position of any member of the @math th generation. We calculate @math to within O(1) and prove exponential tail bounds for @math , under quite general conditions on the branching random walk. In particular, together with work by Bramson [Z. Wahrsch. Verw. Gebiete 45 (1978) 89―108], our results fully characterize the possible behavior of @math when the branching random walk has bounded branching and step size.