Mixing time and isoperimetry in random geometric graphs

Abstract

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 $\hat{I}\mu >0$ and any $r\ge (1+\hat{I}\mu )r_g$, the mixing time of the giant component is with high probability $\hat{I}˜(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.

comments are welcome