The geometry of the giant component of random geometric graphs
Karoline Dubin, Christian Gorski, Marcus Michelen · 2026
Read The geometry of the giant component of random geometric graphs by Karoline Dubin, Christian Gorski, Marcus Michelen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01627.txt.
Introduction
Dubin, Gorski, and Michelen study the shape of the giant component in random geometric graphs. Points are scattered uniformly on a Riemannian manifold. Edges join pairs whose distance stays below a radius r. Past a critical mean degree, a giant component forms in the graph. That threshold depends only on the manifold's dimension. The team ask what the giant component looks like at large scale. Equipped with graph distance, it converges to the manifold itself.
Convergence is in Gromov-Hausdorff distance, after a deterministic rescaling. The result holds even when mean degree grows slowly with n. A payoff follows for telling manifolds apart from samples. A polynomial-time algorithm distinguishes graphs on two non-isometric manifolds. First-passage percolation tools drive the proof.
Catalog record
| CREATOR | Karoline Dubin, Christian Gorski, Marcus Michelen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.01627
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The geometry of the giant component of random geometric graphs Karoline Dubin, Christian Gorski, Marcus Michelen Abstract . Consider a random geometric graph G M ( n , r ) G_{M}(n;r) whose vertex set consists of n n points chosen independently and uniformly from a Riemannian manifold M M , with edges joining pairs of vertices whose distance in the metric d M d_{M} is at most r r . Let Δ \Delta denote the expected average degree of the graph. As is the case for Erdős-Rényi graphs, there is a critical value Δ c \Delta_{c} , depending only on the dimension of M M , such that if Δ > Δ c \Delta>\Delta_{c} then G M ( n , r ) G_{M}(n;r) has a giant component. We show that whenever Δ > Δ c \Delta>\Delta_{c} , the giant component of G M ( n , r ) G_{M}(n;r) , equipped with the graph distance, converges to the underlying manifold M M in the Gromov-Hausdorff distance after rescaling by an appropriate deterministic factor. Our result holds for Δ \Delta depending on n n as well, provided Δ = o ( n ) \Delta=o(n) and Δ ≥ Δ c + ε \Delta\geq\Delta_{c}+\varepsilon for any fixed ε > 0 \varepsilon>0 . As a consequence, we show that for any pair of non-isometric compact Riemannian manifolds M 1 M_{1} and M 2 M_{2} , there is a polynomial-time algorithm that distinguishes random geometric graphs on M 1 M_{1} and M 2 M_{2} throughout this regime of Δ . \Delta. In the thermodynamic regime—i.e. when Δ \Delta is constant—our results appear to be new even in the classical cases where M M is a sphere or a torus. Our proof makes use of techniques from first-passage percolation which allow us to understand the long-range behavior of the graph distance on small, approximately Euclidean patches of M M , together with global arguments that glue these local estimates into a global description. 1. Introduction Let M be a compact d -dimensional Riemannian manifold. For parameters n and r>0 , define the random geometric graph G_{M}(n;r) to be the random graph whose vertex set consists of n points v_{1},\ldots,v_{n} placed on M uniformly at random and whose edge set consists of pairs \{v_{i},v_{j}\} with d_{M}(v_{i},v_{j})\leq r . We are interested in the following general question: how can we understand the geometry of M based on the graph G_{M}(n;r) ? It is useful to parameterize r in terms of the average degree. With this in mind, let \Delta be the expected average degree of G_{M}(n;r) . Classical results on random geometric graphs tell us that when M is a box in \mathbb{R}^{d} and d\geq 2 , there is some constant \Delta_{c}=\Delta_{c}(d)\in(1,\infty) depending only on d so that if \Delta>\Delta_{c} , there is a unique giant component, meaning that there is only one component of the graph with \Omega(n) many vertices [ 20 , Chapter 11] . In stark contrast to this, when \Delta<\Delta_{c} , all components are only polylogarithmic in size with high probability. This same phase transition occurs when M is a connected and compact Riemannian manifold of underlying dimension d\geq 2 , which leads to a fundamental question: in the case of \Delta>\Delta_{c} , what can we deduce about the underlying manifold M from the graph G_{M}(n;r) ? Our main result shows that when M is any compact d -dimensional Riemannian manifold, the random metric space given by the graph distance on the giant component of G_{M}(n;r) is approximately isometric to the underlying metric space (M,d_{M}) . To state this result, we will ultimately use the framework of the Gromov-Hausdorff distance, and so we let d_{\mathrm{GH}} be the Gromov-Hausdorff distance. The amount we will need to rescale by will depend on both the connection radius r and a (continuous, deterministic, non-increasing) function \overline{\mu}:(\Delta_{c},\infty)\to(1,\infty) depending on the dimension; we will see this function is closely related to the time constant of a (continuum) first-passage percolation model. We are ready to state our main theorem: Theorem 1 . Let M be a connected compact d -dimensional Riemannian manifold with d\geq 2 and let \Delta_{c}=\Delta_{c}(d) be the critical average degree for having a giant component. For each fixed \Delta_{0}>\Delta_{c} and \varepsilon>0 , there exists \alpha=\alpha(M,\Delta_{0},\varepsilon)>0 , c=c(M,\Delta_{0},\varepsilon)>0 and n_{0}=n_{0}(M,\Delta_{0},\varepsilon) so that the following holds. Let G=G_{M}(n;r) be the random geometric graph on M with expected average degree \Delta\in[\Delta_{0},\alpha n]. Let \mathring{G}_{M}(n;r) be the component of G with largest diameter and d_{G} be the graph metric on G . Then \mathbb{P}\left(d_{{\mathrm{GH}}}\left(\left(\mathring{G}_{M}(n;r),\frac{r}{\overline{\mu}(\Delta)}d_{G}\right),(M,d_{M})\right)>\varepsilon\right)\leq\exp(-c\log^{2}n) for all n\geq n_{0} . The most well-studied examples of random geometric graphs are taken with M either equal to a sphere or a (flat) torus; 1 is new even in these cases in the “thermodynamic regime” when \Delta_{c}<\Delta=O(1) . We will prove 1 in two cases depending on the degree. The more challenging case will be \Delta\in[\Delta_{0},n^{1-\beta}] for some \beta>0 , while the case of \Delta>n^{1-\beta} will be more straightforward. The critical values \Delta_{c} will appear due to a connection with continuum percolation: if one places a Poisson process of intensity \lambda>0 on \mathbb{R}^{d} and connects points that are within distance 1 of each other, then for d\geq 2 there will be some \lambda_{c}(d) so that for \lambda>\lambda_{c}(d) there is an infinite connected component almost-surely, while for \lambda<\lambda_{c}(d) there almost-surely will not be. If one lets \Delta be the average degree of a vertex in this setting, one obtains a critical average degree \Delta_{c} from this process, which coincides with our \Delta_{c} in 1 . While the critical values \Delta_{c} are not known precisely in any dimension—except the trivial case of \Delta_{c}=+\infty for d=1 ---extensive simulations in the physics literature provide estimates; we include predictions 1 1 1 The critical parameter they present \eta_{c} is related to our \Delta_{c} via \Delta_{c}=2^{d}\eta_{c} . from Torquato and Jiao [ 22 ] , where we round to three decimal places: d predicted \Delta_{c} 2 4.512 3 2.735 4 2.086 5 1.742 6 1.497 7 1.345 8 1.255 9 1.205 10 1.165 11 1.133 Table 1. Predicted critical average degree \Delta_{c} for continuum percolation in \mathbb{R}^{d} . While \Delta_{c}(d) appears to be decreasing in d , it seems that this is not rigorously known. However, a theorem of Penrose [ 21 ] shows that \lim_{d\to\infty}\Delta_{c}(d)=1 . With this in mind, 1 shows that in sufficiently high dimensions, one only needs the average degree to be slightly above 1 in order to infer the underlying geometry of the manifold. In both regimes of \Delta<n^{1-\beta} and \Delta>n^{1-\beta} , we will make use of the Poissonized version of the random geometric graph and it will be simple to deduce 1 from its Poissonized versions. We will let G_{M}^{n}(r) be the random graph on M whose vertex set \{v_{j}\} is the set of points of a Poisson process of intensity n and whose edges consist of pairs \{v_{i},v_{j}\} with d_{M}(v_{i},v_{j})\leq r . We now state the more challenging part, where \Delta is allowed to be arbitrarily close to the critical average degree \Delta_{c} . Theorem 2 . Let M be a connected compact d -dimensional Riemannian manifold with d\geq 2 and let \Delta_{c}=\Delta_{c}(d) be the critical average degree for having a