Cover and Hitting Times of Hyperbolic Random Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915781732728832 |
|---|---|
| author | Kiwi, Marcos Schepers, Markus Sylvester, John |
| author_facet | Kiwi, Marcos Schepers, Markus Sylvester, John |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_06956 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Cover and Hitting Times of Hyperbolic Random Graphs Kiwi, Marcos Schepers, Markus Sylvester, John Probability Discrete 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. |
| title | Cover and Hitting Times of Hyperbolic Random Graphs |
| topic | Probability Discrete Mathematics Combinatorics 05C80, 60J10, 60G40 |
| url | https://arxiv.org/abs/2207.06956 |