The planted matching problem: Sharp threshold and infinite-order phase transition

We study the problem of reconstructing a perfect matching M^* hidden in a randomly weighted n× n bipartite graph. The edge set includes every node pair in M^* and each of the n(n-1) node pairs not in M^* independently with probability d/n. The weight of each edge e is independently drawn from the distribution P if e ∈ M^* and from Q if e notin M^*. We show that if √d B(P,Q) ≤ 1, where B(P,Q) stands for the Bhattacharyya coefficient, the reconstruction error (average fraction of misclassified edges) of the maximum likelihood estimator of M^* converges to 0 as n→ ∞. Conversely, if √d B(P,Q) ≥ 1+ε for an arbitrarily small constant ε>0, the reconstruction error for any estimator is shown to be bounded away from 0 under both the sparse and dense model, resolving the conjecture in [Moharrami et al. 2019, Semerjian et al. 2020]. Furthermore, in the special case of complete exponentially weighted graph with d=n, P=exp(λ), and Q=exp(1/n), for which the sharp threshold simplifies to λ=4, we prove that when λ ≤ 4-ε, the optimal reconstruction error is expleft( - Theta(1/√ε) right), confirming the conjectured infinite-order phase transition in [Semerjian et al. 2020].