Detection Threshold for Correlated Erdos-Renyi Graphs via Densest Subgraph

The problem of detecting edge correlation between two Erdos-Renyi random graphs on n unlabeled nodes can be formulated as a hypothesis testing problem: under the null hypothesis, the two graphs are sampled independently; under the alternative, the two graphs are independently sub-sampled from a parent graph which is Erdos-Renyi Gpn, pq (so that their marginal distributions are the same as the null). We establish a sharp information-theoretic threshold when p = n(-a+o(1)) for alpha is an element of(0, 1] which sharpens a constant factor in a recent work by Wu, Xu and Yu. A key novelty in our work is an interesting connection between the detection problem and the densest subgraph of an Erd.os-Renyi graph.