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 xn 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 distributionPif e. M * and fromQif e /. M *. We show that if v dB(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 * v converges to 0 as n. 8. Conversely, if dB(P, Q) = 1 + for an arbitrarily small constant > 0, the reconstruction error for any estimator is shown to be bounded away from 0 for both the sparse (fixed d) and dense (growing d) regimes, resolving the conjecture in Moharrami et al. (Ann Appl Probab 31(6):2663-2720, 2021. https://doi.org/10.1214/20- AAP1660) and Semerjian et al. (Phys Rev E 102:022304, 2020. https://doi.org/ 10.1103/PhysRevE.102.022304). 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,