Consider a pair of correlated Erd\H{ o}s-R\'enyi graphs $\mathcal G(n,\tfrac{ \lambda}{ n};s)$ that are subsampled from a common parent Erd\H{ o}s-R\'enyi 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\H{ o}s-R\'enyi graphs $\mathcal G(n,\tfrac{ \lambda}{ n})$, showing that strong detection is information-theoretically possible if and only if $s>\min\{ \tfrac{ 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.
Categories: math.PR