Strong Detection Threshold for Correlated Erdős-Rényi Graphs with Constant Average Degree

Abstract

Consider a pair of correlated Erdős-Rényi graphs $\mathcal{G}(n,\frac{\lambda }{n};s)$ that are subsampled from a common parent Erdős-Rényi graph with average degree $\lambda$ and subsampling probability $s$. We establish a sharp information-theoretic threshold for the detection problem between this model and two independent Erdős-Rényi graphs $\mathcal{G}(n,\frac{\lambda }{n})$, showing that strong detection is information-theoretically possible if and only if $s>\min \{\frac{1}{\sqrt{\lambda }},\sqrt{\alpha }\}$ where $\alpha \approx 0.338$ is the Otter's constant. Our result resolves a constant gap between arXiv:2203.14573 and arXiv:2008.10097.

14 pages