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 G(n,λn;s) that are subsampled from a common parent Erdős-Rényi graph with average degree λ 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 G(n,λsn), showing that strong detection is information-theoretically possible if and only if s>min{1 λ,α} where α≈0.338 is the Otter’s constant. Our result resolves a constant gap between [3] and [21].
Fields of Study & Subjects
Cooperative Communication and Network Coding
Wireless Communication Security Techniques
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Electronic Communications in Probability
- Volume
- 31
- Issue
- none
- Pages
- 1–9
- Publication date
- 1 January 2026
- Language
- EN