Matching recovery threshold for correlated random graphs

Abstract

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 observation of these two graphs \emph{without labels}. When $p=n^{-\alpha +o(1)}$ for $\alpha \in (0,1]$, we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.

32 pages