Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees

ABSTRACT: 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 supremum of the Gaussian free field on the graph, assuming that the maximal hitting time is significantly smaller than the cover time. 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. In the talk, I will try to explain the main steps for the proof of bounded-degree graphs, including an application of sprinkling method, a detection argument for Gaussian free field, as well as a reconstruction of the embedded walk from local times which uses a connection with enumeration of Eulerian circuits.


BIO: 
Jian Ding recently finished his PhD in the Statistics Department at UC Berkeley. He was a frequent visitor to MSR, as his advisor was Yuval Peres.
Currently, Jian has a visiting postdoctoral appointment at the CS Dept in UW. He will be a Szego Assistant Professor at Stanford starting this fall.