Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees
Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees
复制标题
通过高斯自由场的覆盖时间渐近：有界度图和一般树
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Jian Ding
中科院分区：
文献类型：
--
作者：
Jian Ding
在本文中，我们证明了在有界度图和一般的树，简单随机游动的覆盖时间是渐近等于产品的边的数量和平方的期望上确界的高斯自由域的图，假设最大命中时间是显着小于覆盖时间。以前，这只证明了正规树和2D格。此外，对于一般的树，我们得到指数浓度的覆盖时间，这意味着覆盖时间的标准差是有界的覆盖时间和最大命中时间的几何平均值。
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.