Matching recovery threshold for correlated random graphs

Jian Ding, Hang Du

For two correlated graphs which are independently sub-sampled from a common Erdős-Rényi graph $\mathbf{G}(n,p)$, we wish to recover their \emph{latent} vertex matching from the ob…