Strong detection threshold for correlated Erdős-Rényi graphs with constant average degree

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].