OpenAlex ·
Sharp detection thresholds for random geometric graphs with polynomial average degrees
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.08517
- Original
- Read it at the publisher
- Topics
Abstract
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 $δ>0$, if $p\to0$, $p\ge n^{-1+δ}$, 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 $χ^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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Statistical Mechanics
Overcoming the limitations of body-ordered potentials for atomistic machine learning
Social Physics: A manifesto
Energy-barrier characterization of secured basins in coupled oscillators with inertia
Studying oscillation death in two-dimensional cylinder-airfoil interactions with synchronization-theoretic autoencoder
Mutual Linearity of Complexes in Chemical Reaction Networks
Get the few papers worth your time in Statistical Mechanics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.