Detection of first homology via random geometric graphs in the thermodynamic regime

Source abstract

Consider a random geometric graph $G_M(n;r)$ on a compact Riemannian manifold $M$, whose vertices are a cloud of $n$ independently sampled points, and whose edges connect vertices at distance $\le r$. We show that, in the thermodynamic (i.e. bounded expected average degree) regime, if $G_M(n;r)$ is supercritical in the sense of continuum percolation, then the first homology group $H_1(M)$ of $M$ can be correctly inferred from $G_M(n;r)$ with high probability as $n \to \infty$. Specifically, one can obtain $H_1(M)$ by taking the cycle space of $G_M(n;r)$ and quotienting out all the cycles of metric diameter $O(r|\log r|)$ (or of graph diameter $O(|\log r|)$). Our method of estimating $H_1(M)$ exploits a coarse-topological fact about supercritical percolation, as opposed to usual methods, which examine the topology of neighborhoods of the point cloud. Whereas previous methods use combinatorial models which require $O(n \log n)$ edges, our method only requires $O(n)$ edges. We also show that, in all phases of the thermodynamic regime, if one instead takes the quotient by cycles of metric diameter $o(r|\log r|)$, with high probability, one will not recover $H_1(M)$. Thus $Θ(r|\log r|)$ is the ``right scale.'' On the way, we show that an arbitrary compact $d$-dimensional Riemannian manifold has a \emph{first homological percolation threshold} in the sense of Bobrowski and Skraba \cite{BS2020} which coincides with the continuum percolation threshold on $\R^d$, a result previously only known for the flat torus. This strongly suggests that our results are optimal, in the sense that $H_1(M)$ cannot be inferred from $G_M(n;r)$ in the subcritical thermodynamic regime. All results hold for homology with arbitrary coefficients.