Report
Cover and Hitting Times of Hyperbolic Random Graphs
| العنوان: | Cover and Hitting Times of Hyperbolic Random Graphs |
|---|---|
| المؤلفون: | Kiwi, Marcos, Schepers, Markus, Sylvester, John |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Probability, Computer Science - Discrete Mathematics, Mathematics - Combinatorics, 05C80, 60J10, 60G40 |
| الوصف: | 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 first focus on the expected time for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that, a.a.s. (with respect to the HRG), and 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$. We then determine the expected time to commute between two given vertices a.a.s., up to a small factor polylogarithmic in $n$, and under some mild hypothesis on the pair of vertices involved. Our results are proved by controlling effective resistances using the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane, on which we overlay a forest-like structure. Comment: 55 pages, 4 figures. Appeared in Proceedings of RANDOM 2022 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2207.06956 |
| رقم الانضمام: | edsarx.2207.06956 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |