Detection of first homology via random geometric graphs in the thermodynamic regime
Abstract
Consider a random geometric graph GM(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 ≤ r. We show that, in the thermodynamic (i.e. bounded expected average degree) regime, if GM(n;r) is supercritical in the sense of continuum percolation, then the first homology group H1(M) of M can be correctly inferred from GM(n;r) with high probability as n → ∞. Specifically, one can obtain H1(M) by taking the cycle space of GM(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 H1(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 H1(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 Rd, a result previously only known for the flat torus. This strongly suggests that our results are optimal, in the sense that H1(M) cannot be inferred from GM(n;r) in the subcritical thermodynamic regime. All results hold for homology with arbitrary coefficients.
Related
- Sharp detection thresholds for random geometric graphs with polynomial average degrees
- Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs
- Planarity and number of crossings in general models of random geometric graphs
- Maximum degree for random geometric graphs in the connectivity regime and beyond
- High powers of grids in random geometric graphs and thresholds for wide spanning structures
BibTeX
@misc{gorski2026detection,
title = {{Detection of first homology via random geometric graphs in the thermodynamic regime}},
author = {Christian Gorski},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.25065},
eprint = {2608.25065},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.25065},
}
RIS
TY - UNPB
TI - Detection of first homology via random geometric graphs in the thermodynamic regime
AU - Christian Gorski
PY - 2026
DA - 2026/08/25
PB - arXiv
DO - 10.48550/arxiv.2608.25065
UR - https://arxiv.org/abs/2608.25065
AB - 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 ≤ 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 → ∞. 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.
ER -