Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.19951 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915571390480384 |
|---|---|
| author | Kiwi, Marcos Martinez, Carlos Mitsche, Dieter |
| author_facet | Kiwi, Marcos Martinez, Carlos Mitsche, Dieter |
| contents | In this paper we study the mixing time of the simple random walk on the giant component of supercritical $d$-dimensional random geometric graphs generated by the unit intensity Poisson Point Process in a $d$-dimensional cube of volume $n$. With $r_g$ denoting the threshold for having a giant component, we show that for every $ε> 0$ and any $r \ge (1+ε)r_g$, the mixing time of the giant component is with high probability $Θ(n^{2/d}/r^{2})$, thereby closing a gap in the literature. The main tool is an isoperimetric inequality which holds, w.h.p., for any large enough vertex set, a result which we believe is of independent interest. Our analysis also implies that the relaxation time is of the same order. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19951 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Mixing time and isoperimetry in random geometric graphs Kiwi, Marcos Martinez, Carlos Mitsche, Dieter Probability Combinatorics In this paper we study the mixing time of the simple random walk on the giant component of supercritical $d$-dimensional random geometric graphs generated by the unit intensity Poisson Point Process in a $d$-dimensional cube of volume $n$. With $r_g$ denoting the threshold for having a giant component, we show that for every $ε> 0$ and any $r \ge (1+ε)r_g$, the mixing time of the giant component is with high probability $Θ(n^{2/d}/r^{2})$, thereby closing a gap in the literature. The main tool is an isoperimetric inequality which holds, w.h.p., for any large enough vertex set, a result which we believe is of independent interest. Our analysis also implies that the relaxation time is of the same order. |
| title | Mixing time and isoperimetry in random geometric graphs |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2510.19951 |