The geometry of the giant component of random geometric graphs

Christian Gorski; Karoline Dubin; Marcus Michelen

arxiv: 2606.01627 · v1 · pith:N5XXTQNTnew · submitted 2026-06-01 · 🧮 math.PR · math.CO

The geometry of the giant component of random geometric graphs

Karoline Dubin , Christian Gorski , Marcus Michelen This is my paper

Pith reviewed 2026-06-28 13:19 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords random geometric graphsgiant componentGromov-Hausdorff convergenceRiemannian manifoldfirst-passage percolationgraph distancerandom graphs on manifolds

0 comments

The pith

The giant component of a random geometric graph on a manifold converges in rescaled graph distance to the manifold in the Gromov-Hausdorff metric.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that above a critical expected average degree depending only on dimension, the giant component of a random geometric graph on any compact Riemannian manifold M, when given the graph distance and rescaled by a deterministic factor, converges to M itself in the Gromov-Hausdorff distance. The result continues to hold when this degree grows with the number of vertices n but remains o(n) and stays a fixed amount above criticality. A reader would care because the discrete connectivity structure then recovers the continuous geometry of the underlying space, even in the constant-degree regime for familiar cases such as spheres and tori. As a direct consequence the paper obtains a polynomial-time algorithm that distinguishes random geometric graphs drawn on non-isometric manifolds.

Core claim

Whenever Δ exceeds the critical value Δ_c that depends only on dimension, the giant component of G_M(n;r), equipped with graph distance, converges to the manifold M in the Gromov-Hausdorff distance after deterministic rescaling. The statement holds for Δ = o(n) and Δ ≥ Δ_c + ε. The argument proceeds by applying first-passage percolation estimates to control graph distances on small approximately Euclidean patches of M and then gluing the local controls into a global limit.

What carries the argument

First-passage percolation estimates on approximately Euclidean patches of M that control long-range graph distances and are glued into a global Gromov-Hausdorff limit.

If this is right

Non-isometric compact Riemannian manifolds can be distinguished by a polynomial-time algorithm that inspects samples of their random geometric graphs throughout the stated regime of Δ.
The geometric recovery holds in the constant-degree thermodynamic regime, including the classical cases of the sphere and the torus.
The same convergence applies when the expected degree grows slowly with n but remains bounded away from both criticality and linear growth.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Graph distances extracted from the giant component may permit numerical reconstruction of manifold geometry from finite point samples.
The local-to-global gluing strategy could extend to other random-graph models whose edges are determined by a manifold metric.
Direct simulation on the circle or sphere would provide a concrete numerical check of the predicted convergence rate.

Load-bearing premise

The manifold is locally close enough to Euclidean on the scale of the connection radius that first-passage percolation estimates on small patches can be glued into a global limit.

What would settle it

An explicit manifold M and sequence of parameters with Δ > Δ_c for which the rescaled graph metric on the giant component fails to converge to the manifold metric in the Gromov-Hausdorff distance.

read the original abstract

Consider a random geometric graph $G_M(n;r)$ whose vertex set consists of $n$ points chosen independently and uniformly from a Riemannian manifold $M$, with edges joining pairs of vertices whose distance in the metric $d_M$ is at most $r$. Let $\Delta$ denote the expected average degree of the graph. As is the case for Erd\H{o}s-R\'enyi graphs, there is a critical value $\Delta_c$, depending only on the dimension of $M$, such that if $\Delta > \Delta_c$ then $G_M(n;r)$ has a giant component. We show that whenever $\Delta > \Delta_c$, the giant component of $G_M(n;r)$, equipped with the graph distance, converges to the underlying manifold $M$ in the Gromov-Hausdorff distance after rescaling by an appropriate deterministic factor. Our result holds for $\Delta$ depending on $n$ as well, provided $\Delta = o(n)$ and $\Delta \geq \Delta_c + \varepsilon$ for any fixed $\varepsilon > 0$. As a consequence, we show that for any pair of non-isometric compact Riemannian manifolds $M_1$ and $M_2$, there is a polynomial-time algorithm that distinguishes random geometric graphs on $M_1$ and $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$ 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$, together with global arguments that glue these local estimates into a global description.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The giant component converges in Gromov-Hausdorff distance to the manifold after rescaling, with a polynomial-time distinction algorithm as a consequence.

read the letter

The core result is that for random geometric graphs on a compact Riemannian manifold, once the average degree exceeds the percolation threshold by a fixed amount, the giant component with graph distance converges in Gromov-Hausdorff sense to the manifold itself after deterministic rescaling. The claim covers both constant degree and slowly growing degree up to o(n), and it yields a poly-time algorithm that distinguishes samples from non-isometric manifolds.

The work does two things cleanly. It moves the giant-component geometry from flat or toroidal settings to general compact manifolds by treating small patches as approximately Euclidean and controlling graph distances there via first-passage percolation, then gluing the local limits. The abstract notes that even the sphere and torus cases in the thermodynamic regime appear new, which is the clearest advance. The algorithmic corollary follows directly once the convergence is in hand.

The main soft spot is the lack of explicit scaling factor or rate in the abstract; without the full derivation it is hard to judge how the constants depend on curvature or injectivity radius and whether the gluing step accumulates error that grows with the number of patches. The regime Δ = o(n) is plausible because local Euclidean approximation improves as r shrinks, but any quantitative version would need uniform control over the manifold. No internal contradiction shows up in the stated argument structure.

The paper is aimed at people working in geometric probability and percolation on manifolds. A reader who already knows continuum percolation and FPP shape theorems will see the value in the extension and the distinction algorithm. It deserves a serious referee because the claim is substantial and the method is standard enough to be checkable.

Referee Report

0 major / 2 minor

Summary. The paper proves that in the random geometric graph G_M(n;r) on a compact Riemannian manifold M, when the expected average degree Δ exceeds the critical threshold Δ_c (depending only on dim(M)) by a fixed ε>0 and Δ=o(n), the giant component equipped with graph distance converges in the Gromov-Hausdorff metric to M after rescaling by a deterministic factor. The argument combines local first-passage percolation estimates on approximately Euclidean patches of M with global gluing; the result is new even for spheres and tori in the constant-Δ regime and yields a polynomial-time algorithm distinguishing non-isometric manifolds from samples of their RGGs.

Significance. If the central convergence holds, the work supplies a geometric limit theorem for supercritical giant components of RGGs on general manifolds, extending Euclidean results and furnishing a concrete algorithmic consequence. The FPP-based control of long-range distances on local patches is a natural and appropriate technique, and the uniformity over compact M (via bounded curvature and injectivity radius) is a clear strength. The result being novel in the thermodynamic regime on standard manifolds adds to its value.

minor comments (2)

Abstract: the deterministic scaling factor is referred to only as 'appropriate'; the main text should state its explicit construction from the FPP shape theorem on tangent spaces and confirm it is independent of n and r in the stated regime.
The gluing argument is described at a high level; a brief outline of the error terms that vanish uniformly as r→0 would improve readability without altering the proof structure.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, the recognition of its novelty even in the constant-degree regime on standard manifolds, and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation invokes external first-passage percolation estimates on approximately Euclidean patches of the compact manifold M, then glues them globally; these techniques are drawn from the established FPP literature and are not reduced to quantities defined inside the paper. No self-definitional relations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the stated argument. The compactness of M and the regime Δ = o(n) with Δ ≥ Δ_c + ε supply the necessary uniform bounds without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, ad-hoc axioms, or invented entities are named. The result is a convergence theorem whose technical assumptions (Riemannian structure, first-passage percolation applicability on patches) are standard in the cited literature.

pith-pipeline@v0.9.1-grok · 5860 in / 1297 out tokens · 19419 ms · 2026-06-28T13:19:49.963234+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 1 linked inside Pith

[1]

Antal and A

P. Antal and A. Pisztora. On the chemical distance for supercritical Bernoulli percolation.Ann. Probab., 24(2):1036–1048,
[2]

Auffinger, M

A. Auffinger, M. Damron, and J. Hanson.50 years of first-passage percolation, volume 68. American Mathematical Soc.,
[3]

Bernstein, V

M. Bernstein, V. De Silva, J. C. Langford, and J. B. Tenenbaum. Graph approximations to geodesics on embedded manifolds. Technical report, Technical report, Department of Psychology, Stanford University, 2000. 4

2000
[4]

Bollob´ as

B. Bollob´ as. Random graphs. InModern graph theory, pages 215–252. Springer, 2011. 5

2011
[5]

Bonnet and A

G. Bonnet and A. Gusakova. Concentration inequalities for PoissonU-statistics.arXiv preprint arXiv:2404.16756, 2024. 24

arXiv 2024
[6]

Bubeck, J

S. Bubeck, J. Ding, R. Eldan, and M. Z. R´ acz. Testing for high-dimensional geometry in random graphs.Random Structures & Algorithms, 49(3):503–532, 2016. 3

2016
[7]

Burago, Y

D. Burago, Y. Burago, and S. Ivanov.A course in metric geometry, volume 33 ofGraduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001. 23

2001
[8]

J. T. Cox and R. Durrett. Some limit theorems for percolation processes with necessary and sufficient conditions.The Annals of Probability, pages 583–603, 1981. 6

1981
[9]

Dubin and C

K. Dubin and C. Gorski. Lipschitz continuity of the time constant for continuum percolation.arXiv preprint arXiv:2605.31568, 2026. 9

Pith/arXiv arXiv 2026
[10]

E. N. Gilbert. Random plane networks.Journal of the society for industrial and applied mathematics, 9(4):533–543, 1961. 6

1961
[11]

Gromov.Metric structures for Riemannian and non-Riemannian spaces

M. Gromov.Metric structures for Riemannian and non-Riemannian spaces. Springer, 2007. 20

2007
[12]

Huang, P

H. Huang, P. Jiradilok, and E. Mossel. Reconstructing the geometry of random geometric graphs. InThe Thirty Seventh Annual Conference on Learning Theory, pages 2519–2521. PMLR, 2024. 4

2024
[13]

Huang, P

H. Huang, P. Jiradilok, and E. Mossel. Reconstructing Riemannian metrics from random geometric graphs.arXiv preprint arXiv:2511.05434, 2025. 4

arXiv 2025
[14]

Huang, P

H. Huang, P. Jiradilok, and E. Mossel. Denoising distances beyond the volumetric barrier.arXiv preprint arXiv:2604.00432,

arXiv
[15]

J. F. Kingman. The ergodic theory of subadditive stochastic processes.Journal of the Royal Statistical Society: Series B (Methodological), 30(3):499–510, 1968. 6

1968
[16]

Last and M

G. Last and M. Penrose.Lectures on the Poisson process, volume 7. Cambridge University Press, 2018. 8

2018
[17]

J. M. Lee.Introduction to Riemannian manifolds, volume 2. Springer, 2018. 7

2018
[18]

S. Liu, S. Mohanty, T. Schramm, and E. Yang. Testing thresholds for high-dimensional sparse random geometric graphs. Association for Computing Machinery, page 672–677, 2022. 4

2022
[19]

Meester and R

R. Meester and R. Roy.Continuum percolation, volume 119 ofCambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1996. 3, 6

1996
[20]

Penrose.Random geometric graphs, volume 5 ofOxford Studies in Probability

M. Penrose.Random geometric graphs, volume 5 ofOxford Studies in Probability. Oxford University Press, Oxford, 2003. 1, 3, 8, 9, 26, 27

2003
[21]

M. D. Penrose. Continuum percolation and euclidean minimal spanning trees in high dimensions.The Annals of Applied Probability, 6(2):528–544, 1996. 2

1996
[22]

Torquato and Y

S. Torquato and Y. Jiao. Effect of dimensionality on the continuum percolation of overlapping hyperspheres and hypercubes. ii. simulation results and analyses.The Journal of chemical physics, 137(7), 2012. 2

2012
[23]

A. A. Tuzhilin. Lectures on Hausdorff and Gromov-Hausdorff distance geometry.arXiv preprint arXiv:2012.00756, 2020. 20

arXiv 2012
[24]

crossing events

C.-L. Yao, G. Chen, and T.-D. Guo. Large deviations for the graph distance in supercritical continuum percolation.J. Appl. Probab., 48(1):154–172, 2011. 3, 6, 8, 9, 13, 14, 15, 27, 28 AppendixA.Some results for geometric random graphs onR d with distorted metric and intensity measure Proof of Theorem 13.We will adapt the proof of its homogeneous analogue,...

2011

[1] [1]

Antal and A

P. Antal and A. Pisztora. On the chemical distance for supercritical Bernoulli percolation.Ann. Probab., 24(2):1036–1048,

[2] [2]

Auffinger, M

A. Auffinger, M. Damron, and J. Hanson.50 years of first-passage percolation, volume 68. American Mathematical Soc.,

[3] [3]

Bernstein, V

M. Bernstein, V. De Silva, J. C. Langford, and J. B. Tenenbaum. Graph approximations to geodesics on embedded manifolds. Technical report, Technical report, Department of Psychology, Stanford University, 2000. 4

2000

[4] [4]

Bollob´ as

B. Bollob´ as. Random graphs. InModern graph theory, pages 215–252. Springer, 2011. 5

2011

[5] [5]

Bonnet and A

G. Bonnet and A. Gusakova. Concentration inequalities for PoissonU-statistics.arXiv preprint arXiv:2404.16756, 2024. 24

arXiv 2024

[6] [6]

Bubeck, J

S. Bubeck, J. Ding, R. Eldan, and M. Z. R´ acz. Testing for high-dimensional geometry in random graphs.Random Structures & Algorithms, 49(3):503–532, 2016. 3

2016

[7] [7]

Burago, Y

D. Burago, Y. Burago, and S. Ivanov.A course in metric geometry, volume 33 ofGraduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001. 23

2001

[8] [8]

J. T. Cox and R. Durrett. Some limit theorems for percolation processes with necessary and sufficient conditions.The Annals of Probability, pages 583–603, 1981. 6

1981

[9] [9]

Dubin and C

K. Dubin and C. Gorski. Lipschitz continuity of the time constant for continuum percolation.arXiv preprint arXiv:2605.31568, 2026. 9

Pith/arXiv arXiv 2026

[10] [10]

E. N. Gilbert. Random plane networks.Journal of the society for industrial and applied mathematics, 9(4):533–543, 1961. 6

1961

[11] [11]

Gromov.Metric structures for Riemannian and non-Riemannian spaces

M. Gromov.Metric structures for Riemannian and non-Riemannian spaces. Springer, 2007. 20

2007

[12] [12]

Huang, P

H. Huang, P. Jiradilok, and E. Mossel. Reconstructing the geometry of random geometric graphs. InThe Thirty Seventh Annual Conference on Learning Theory, pages 2519–2521. PMLR, 2024. 4

2024

[13] [13]

Huang, P

H. Huang, P. Jiradilok, and E. Mossel. Reconstructing Riemannian metrics from random geometric graphs.arXiv preprint arXiv:2511.05434, 2025. 4

arXiv 2025

[14] [14]

Huang, P

H. Huang, P. Jiradilok, and E. Mossel. Denoising distances beyond the volumetric barrier.arXiv preprint arXiv:2604.00432,

arXiv

[15] [15]

J. F. Kingman. The ergodic theory of subadditive stochastic processes.Journal of the Royal Statistical Society: Series B (Methodological), 30(3):499–510, 1968. 6

1968

[16] [16]

Last and M

G. Last and M. Penrose.Lectures on the Poisson process, volume 7. Cambridge University Press, 2018. 8

2018

[17] [17]

J. M. Lee.Introduction to Riemannian manifolds, volume 2. Springer, 2018. 7

2018

[18] [18]

S. Liu, S. Mohanty, T. Schramm, and E. Yang. Testing thresholds for high-dimensional sparse random geometric graphs. Association for Computing Machinery, page 672–677, 2022. 4

2022

[19] [19]

Meester and R

R. Meester and R. Roy.Continuum percolation, volume 119 ofCambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1996. 3, 6

1996

[20] [20]

Penrose.Random geometric graphs, volume 5 ofOxford Studies in Probability

M. Penrose.Random geometric graphs, volume 5 ofOxford Studies in Probability. Oxford University Press, Oxford, 2003. 1, 3, 8, 9, 26, 27

2003

[21] [21]

M. D. Penrose. Continuum percolation and euclidean minimal spanning trees in high dimensions.The Annals of Applied Probability, 6(2):528–544, 1996. 2

1996

[22] [22]

Torquato and Y

S. Torquato and Y. Jiao. Effect of dimensionality on the continuum percolation of overlapping hyperspheres and hypercubes. ii. simulation results and analyses.The Journal of chemical physics, 137(7), 2012. 2

2012

[23] [23]

A. A. Tuzhilin. Lectures on Hausdorff and Gromov-Hausdorff distance geometry.arXiv preprint arXiv:2012.00756, 2020. 20

arXiv 2012

[24] [24]

crossing events

C.-L. Yao, G. Chen, and T.-D. Guo. Large deviations for the graph distance in supercritical continuum percolation.J. Appl. Probab., 48(1):154–172, 2011. 3, 6, 8, 9, 13, 14, 15, 27, 28 AppendixA.Some results for geometric random graphs onR d with distorted metric and intensity measure Proof of Theorem 13.We will adapt the proof of its homogeneous analogue,...

2011