Sharp detection thresholds for random geometric graphs with polynomial average degrees
Abstract
We study the random geometric graph formed by connecting n independent uniform points on 𝕊d−1 whenever their inner product exceeds a threshold chosen to give edge density p. We establish the conjectured dimensionality threshold for indistinguishability from the Erdös-Rényi graph G(n,p) throughout the sparse regime with polynomially growing average degree. Specifically, for every fixed δ>0, if p→0, p≥ n−1+δ, and d≫ (nplog(1/p))3, then the Kullback-Leibler (KL) divergence between the two distributions vanishes. Our proof builds on the posterior analysis framework introduced in previous work of the authors, combining a truncated second moment analysis with Fourier and spherical harmonic expansions. As in prior works, we reduce the KL bound to controlling a truncated χ2-divergence Δ for the neighborhood of the last vertex conditional on the graph induced by the preceding vertices. We then bound Δ using a Fourier expansion of the conditional likelihood ratio for this neighborhood, where the high-frequency contribution is made negligible by truncation to a typical-degree event, while a spherical harmonic expansion approximates the low-frequency contribution in terms of posterior moments of bounded-degree harmonic polynomials. The key observation is that these moments and Δ satisfy a coupled system of cavity recurrences, yielding a self-bounding inequality that implies the desired KL bound.
Related
- Seed thresholds and degree variance in heterogeneous bootstrap percolation with growing degrees
- Tempered Langevin diffusions with polynomial-tailed targets: explosions, moment thresholds and ergodicity
- Estimating the average treatment effect under limited overlap via Polynomial Approximation and Extrapolation
- High powers of grids in random geometric graphs and thresholds for wide spanning structures
- The stability landscape in wave-packet scattering: geometric rigidity and sharp Sobolev thresholds
BibTeX
@misc{du2026sharp,
title = {{Sharp detection thresholds for random geometric graphs with polynomial average degrees}},
author = {Hang Du and Cheng Mao and Nike Sun and Yihong Wu and Jiaming Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08517},
eprint = {2610.08517},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08517},
}
RIS
TY - UNPB
TI - Sharp detection thresholds for random geometric graphs with polynomial average degrees
AU - Hang Du
AU - Cheng Mao
AU - Nike Sun
AU - Yihong Wu
AU - Jiaming Xu
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08517
UR - https://arxiv.org/abs/2610.08517
AB - We study the random geometric graph formed by connecting n independent uniform points on 𝕊^d−1 whenever their inner product exceeds a threshold chosen to give edge density p. We establish the conjectured dimensionality threshold for indistinguishability from the Erdös-Rényi graph G(n,p) throughout the sparse regime with polynomially growing average degree. Specifically, for every fixed δ>0, if p→0, p≥ n^−1+δ, and d≫ (nplog(1/p))^3, then the Kullback-Leibler (KL) divergence between the two distributions vanishes. Our proof builds on the posterior analysis framework introduced in previous work of the authors, combining a truncated second moment analysis with Fourier and spherical harmonic expansions. As in prior works, we reduce the KL bound to controlling a truncated χ^2-divergence Δ for the neighborhood of the last vertex conditional on the graph induced by the preceding vertices. We then bound Δ using a Fourier expansion of the conditional likelihood ratio for this neighborhood, where the high-frequency contribution is made negligible by truncation to a typical-degree event, while a spherical harmonic expansion approximates the low-frequency contribution in terms of posterior moments of bounded-degree harmonic polynomials. The key observation is that these moments and Δ satisfy a coupled system of cavity recurrences, yielding a self-bounding inequality that implies the desired KL bound.
ER -