The partial reconstruction threshold conjecture for sparse graph alignment

Let $\mathcal{G}$ and $\mathcal{H}$ be the correlated sparse random graphs in the model under consideration, with sparsity parameter $\lambda$ and edge correlation parameter $s$. Let $\pi^*$ be the latent vertex-matching permutation, and let $\hat{\pi}$ be an estimator of $\pi^*$. Define the overlap by

$$\operatorname{ov}(\hat{\pi}(\mathcal{G},\mathcal{H}),\pi^*):= \frac{1}{n!} \sum_{\sigma \in \mathcal{S}_n} \sum_{i=1}^{n} \mathbf{1}_{\hat{\pi}(\mathcal{G}^{\sigma},\mathcal{H})(i)= \pi^* \circ \sigma^{-1} (i)}.$$

Partial reconstruction threshold conjecture. If $\lambda s \leq 1$, then partial reconstruction is impossible: for every $\alpha>0$ and every estimator $\hat{\pi}$,

$$\mathbb{P}\left(\operatorname{ov}(\hat{\pi},\pi^*) > \alpha n \right) \underset{n \to \infty}{\longrightarrow} 0.$$

If $\lambda s>1$, then partial reconstruction is possible: there exist $\alpha>0$ and an estimator $\hat{\pi}$ such that

$$\mathbb{P}\left(\operatorname{ov}(\hat{\pi},\pi^*) > \alpha n \right) \underset{n \to \infty}{\longrightarrow} 1.$$

The conjecture identifies $\lambda s=1$ as the sharp threshold for recovering a positive fraction of the vertices in the sparse graph alignment problem. The statement concerns partial rather than exact alignment because the sparse graphs contain linearly many isolated vertices, which cannot be matched better than chance even without observation noise. The parser provides no evidence that either direction has been resolved.