AI summaryⓘ
The authors study a type of random graph made by placing points on a high-dimensional sphere and connecting nearby points, called the spherical random geometric graph. They investigate when this graph looks different from a simpler random graph where edges are just randomly included with some fixed probability. They confirm a previous prediction about the conditions on dimension and edge probability under which the two graphs become indistinguishable. Their proof covers a wider range of edge probabilities and provides precise estimates of the chance that the spherical model forms any given graph, highlighting a specific statistic called the signed triangle count. This advances understanding of when geometry genuinely influences random graph structure.
spherical random geometric graphErdős–Rényi random graphtotal variation distancehigh-dimensional geometrysigned triangle countrandom graphsgraph distinguishabilityasymptotic probabilityedge probability
Abstract
The spherical random geometric graph $G(n,d,p)$ is obtained by sampling $n$ independent points uniformly on the unit sphere $\mathbb{S}^{d-1}\subseteq\mathbb{R}^d$ and joining pairs of points which are sufficiently close, where the threshold is chosen so that the edge probability is $p$. The central question related to this model, and to a broad class of other models, is the following: when does the underlying geometry affect the resulting graph in a way which makes it distinguishable from the Erdős--Rényi random graph $G(n,p)$, as measured in total variation distance? The precise answer to this question was conjectured by Bubeck, Ding, Eldan, and Rácz, who predicted that $G(n,d,p)$ and $G(n,p)$ are indistinguishable precisely when $d \gg n^3p^3(\log p^{-1})^3$, and provided a test for distinguishing these models in the low-dimensional regime. Although this conjecture attracted considerable attention from researchers in probability, theoretical computer science, and high-dimensional statistics, it was previously fully proved only in the constant-density case. In this paper, we resolve the distinguishability conjecture in the broad range $1/3 \geq p \geq n^{-1/5} \text{polylog}(n)$. The key ingredient of our proof is a stronger statement which gives a precise asymptotic formula for the probability that $G(n,d,p)$ realizes a prescribed graph $H$: above the conjectured threshold, this probability is at most $(1+o(1))$ times the corresponding probability for $G(n,p)$, with the signed triangle count of $H$ appearing as the leading correction term.