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.
Benjamini, Gurel-Gurevich and Morris, showed that for bounded degree graphs it is exponentially unlikely to cover the graph in linear time @cite_19 . This is a different type of large deviation result on the cover time from the one that we prove.
@cite_19
2007625773
We show that the probability that a simple random walk covers a finite, bounded degree graph in linear time is exponentially small. We conjecture that the same holds for any simple graph.