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

By Jian Ding. 2011

50 citations recorded by the source corpus.

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.

Subfields: Condensed Matter Physics, Mathematical Physics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/0556283d8b2aa92d59c769b8100b08c007e63ed2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

1. David Belius
2. N. Kistler
3. Zhan Shi
4. L. Arguin

In Mathematical Physics

1. David Belius
2. N. Kistler
3. L. Arguin
4. Joseph Najnudel
5. Zhan Shi

In Molecular Biology

1. David Belius
2. N. Kistler

Citations in the corpus

• Extreme values for two-dimensional discrete Gaussian free field (2012, unknown): “03 46 v3 [ m at h. PR ] 7 A pr”
• The subleading order of two dimensional cover times (2014, methodology): “For this we will need the following computation of the conditional distribution of T̃ t l (which can be seen as a special case of the results of Section 4 [13]).”