Key points are not available for this paper at this time.
For two correlated graphs which are independently sub-sampled from a common Erdős-Rényi graph G (n, p), we wish to recover their latent vertex matching from the observation of these two graphs without labels. When p = n^-α+o (1) for α (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.
Ding et al. (Sun,) studied this question.