Metraipolis › archive › dc_f1187f636fe9

Sharp detection thresholds for random geometric graphs with polynomial average degrees — arXiv:2610.08517

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.08517
License (as archived)
CC0-1.0
Archived
2026-10-07T11:50:22.703Z
SHA-256 of the archived text
f2ca89c504438154c39049bf7b815e3a12d364a763b0babd9845855742d9e506
Stable URL of this page
https://metraipolis.com/documento/dc_f1187f636fe9

How to cite

Sharp detection thresholds for random geometric graphs with polynomial average degrees — arXiv:2610.08517 — arXiv (en), https://arxiv.org/abs/2610.08517 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f1187f636fe9 (Metraipolis archive dc_f1187f636fe9, sha256 f2ca89c504438154c39049bf7b815e3a12d364a763b0babd9845855742d9e506)
BibTeX
@misc{dcf1187f636fe9,
  title = {Sharp detection thresholds for random geometric graphs with polynomial average degrees — arXiv:2610.08517},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.08517},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f1187f636fe9; sha256 f2ca89c504438154c39049bf7b815e3a12d364a763b0babd9845855742d9e506},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.08517. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the random geometric graph formed by connecting $n$ independent uniform points on $\mathbb S^{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 $\delta>0$, if $p\to0$, $p\ge n^{-1+\delta}$, and $d\gg (np\log(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 $\chi^2$-divergence $\Delta$ for the neighborhood of the last vertex conditional on the graph induced by the preceding vertices. We then bound $\Delta$ 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 $\Delta$ satisfy a coupled system of cavity recurrences, yielding a self-bounding inequality that implies the desired KL bound.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.ST, nuovi lavori del giorno).
Categorie arXiv: Probability (math.PR) ; Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2610.08517 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:21:24.636Z dalla pagina https://arxiv.org/list/math.ST/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).