Return to Colloquia & Seminar listing
Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
Probability| Speaker: | Jian Ding, UC Berkeley |
| Location: | 3106 MSB |
| Start time: | Tue, Apr 26 2011, 2:10PM |
I will quickly review the joint work with Lee and Peres (2010), which shows that the cover time for any graph is equivalent up to a universal constant, to the product of the number of edges and the square of the supremum of the Gaussian free field on that graph. I will then report a recent progress on the asymptotics of cover times: 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. 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.
Note the unusual day, time and place