We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range $(2,3)$. In particular, we focus on the expected times for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that up to multiplicative constants: the cover time is $n(\log n)^2$, the maximum hitting time is $n\log n$, and the average hitting time is $n$. The first two results hold in expectation and a.a.s. and the last in expectation (with respect to the HRG). We prove these results by determining the effective resistance either between an average vertex and the well-connected "center" of HRGs or between an appropriately chosen collection of extremal vertices. We bound the effective resistance by the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane on which we overlay a forest-like structure.
翻译:我们研究的是超曲随机图(HRGs)巨型成份的随机行走。 当度分布符合权力法, 且在范围为$(2,3美元) 时, 我们研究的是超曲随机图(HRGs) 巨型成份的随机行走。 特别是, 我们关注随机行走击中给定的脊椎或访问( 覆盖) 的预期时间, 即所有脊椎。 我们显示, 最多可以乘以倍增常数: 覆盖时间是 $n( log n) $2, 最高击球时间是 $n\ log n, 平均击球时间是 $n. 。 头两个结果维持在期待和 a.a. 中, 以及最后的结果( HRG) 。 我们通过确定平均的脊椎和连接良好的“ 中心” 之间, 或者在适当选择的 边脊椎收集之间的有效抵抗力。 我们把能量消散的有效抵抗力通过精心设计的网络流来控制, 与我们覆盖类似森林结构的双向上的超叶平面的平面结构相关联 。