Id: arxiv/2603.24545 Url: https://arxiv.org/abs/2603.24545 Tags: math.ST, cs.CC, cs.DS, math.PR, stat.ML Score: 0 Title: Detection of local geometry in random graphs: information-theoretic and computational limits Domain: math.ST Source: arxiv Authors: Jinho Bok, Shuangping Li, Sophie H. Yu Reviews: 0 Subject: math.ST Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-25 Page: https://delphi.science/r/arxiv/2603.24545 We study the problem of detecting local geometry in random graphs. We introduce a model $\mathcal{G}(n, p, d, k)$, where a hidden community of average size $k$ has edges drawn as a random geometric graph on $\mathbb{S}^{d-1}$, while all remaining edges follow the Erdős--Rényi model $\mathcal{G}(n, p)$. The random geometric graph is generated by thresholding inner products of latent vectors on $\mathbb{S}^{d-1}$, with each edge having marginal probability equal to $p$. This implies that $\mathcal{G}(n, p, d, k)$ and $\mathcal{G}(n, p)$ are indistinguishable at the level of the marginals, and…