On the jump of the cover time in random geometric graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912212533116928 |
|---|---|
| author | Martinez, Carlos Mitsche, Dieter |
| author_facet | Martinez, Carlos Mitsche, Dieter |
| contents | In this paper we study the cover time of the simple random walk on the giant component of supercritical $d$-dimensional random geometric graphs on $\mathrm{Poi}(n)$ vertices. We show that the cover time undergoes a jump at the connectivity threshold radius $r_c$: with $r_g$ denoting the threshold for having a giant component, we show that if the radius $r$ satisfies $(1+\varepsilon)r_g \le r \le (1-\varepsilon)r_c$ for $\varepsilon > 0$ arbitrarily small, the cover time of the giant component is asymptotically almost surely $Θ(n \log^2 n$). On the other hand, we show that for $r \ge (1+\varepsilon)r_c$, the cover time of the graph is asymptotically almost surely $Θ(n \log n)$ (which was known for $d=2$ only for a radius larger by a constant factor). Our proofs also shed some light onto the behavior around $r_c$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02433 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the jump of the cover time in random geometric graphs Martinez, Carlos Mitsche, Dieter Probability Combinatorics 05C80, 60D05, 05C81 In this paper we study the cover time of the simple random walk on the giant component of supercritical $d$-dimensional random geometric graphs on $\mathrm{Poi}(n)$ vertices. We show that the cover time undergoes a jump at the connectivity threshold radius $r_c$: with $r_g$ denoting the threshold for having a giant component, we show that if the radius $r$ satisfies $(1+\varepsilon)r_g \le r \le (1-\varepsilon)r_c$ for $\varepsilon > 0$ arbitrarily small, the cover time of the giant component is asymptotically almost surely $Θ(n \log^2 n$). On the other hand, we show that for $r \ge (1+\varepsilon)r_c$, the cover time of the graph is asymptotically almost surely $Θ(n \log n)$ (which was known for $d=2$ only for a radius larger by a constant factor). Our proofs also shed some light onto the behavior around $r_c$. |
| title | On the jump of the cover time in random geometric graphs |
| topic | Probability Combinatorics 05C80, 60D05, 05C81 |
| url | https://arxiv.org/abs/2501.02433 |