Mixing time of the random walk on the giant component of the random geometric graph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911337768026112 |
|---|---|
| author | Haaland, Magnus H. Šarković, Anđela |
| author_facet | Haaland, Magnus H. Šarković, Anđela |
| contents | We consider a random geometric graph obtained by placing a Poisson point process of intensity 1 in the d-dimensional torus of side length n^(1/d) and connecting two points by an edge if their distance is at most r. We consider the case of d>=2 and r in [r_min, r_max], where r_min<r_max are any constants with r_min>r_g and r_g is a constant above which this graph has a giant component with high probability. We show that, with high probability, the mixing time and the relaxation time of the simple random walk on the giant component in this case are both of order n^(2/d) and that therefore there is no cutoff. We also obtain bounds for the isoperimetric profile of subsets of the giant component of at least polylogarithmic size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21322 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Mixing time of the random walk on the giant component of the random geometric graph Haaland, Magnus H. Šarković, Anđela Probability 60D05 (Primary) 05C80, 05C81 (Secondary) We consider a random geometric graph obtained by placing a Poisson point process of intensity 1 in the d-dimensional torus of side length n^(1/d) and connecting two points by an edge if their distance is at most r. We consider the case of d>=2 and r in [r_min, r_max], where r_min<r_max are any constants with r_min>r_g and r_g is a constant above which this graph has a giant component with high probability. We show that, with high probability, the mixing time and the relaxation time of the simple random walk on the giant component in this case are both of order n^(2/d) and that therefore there is no cutoff. We also obtain bounds for the isoperimetric profile of subsets of the giant component of at least polylogarithmic size. |
| title | Mixing time of the random walk on the giant component of the random geometric graph |
| topic | Probability 60D05 (Primary) 05C80, 05C81 (Secondary) |
| url | https://arxiv.org/abs/2512.21322 |