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

arXiv: https://arxiv.org/abs/2103.09383 · HTML: https://mlsanity.com/paper/2103.09383/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 32 references that are in the map.
- First posted on arXiv 17 Mar 2021.

## Builds on (most cited first, 6 of 6)

- [MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel](https://mlsanity.com/paper/1507.03857/) (2015)
- [The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness](https://mlsanity.com/paper/1702.00467/) (2017)
- [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015)
- [The Planted Matching Problem: Phase Transitions and Exact Results](https://mlsanity.com/paper/1912.08880/) (2019)
- [Hidden Hamiltonian Cycle Recovery via Linear Programming](https://mlsanity.com/paper/1804.05436/) (2018)
- [Consistent recovery threshold of hidden nearest neighbor graphs](https://mlsanity.com/paper/1911.08004/) (2019)

## Built on by (most cited first, 9 of 9)

- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [Phase Transitions in the Detection of Correlated Databases](https://mlsanity.com/paper/2302.03380/) (2023)
- [Gaussian Database Alignment and Gaussian Planted Matching](https://mlsanity.com/paper/2307.02459/) (2023)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Testing Dependency of Unlabeled Databases](https://mlsanity.com/paper/2311.05874/) (2023)
- [Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein](https://mlsanity.com/paper/2311.13595/) (2023)
- [Detection of Correlated Random Vectors](https://mlsanity.com/paper/2401.13429/) (2024)
- [Recovery thresholds for hidden weighted sparse graphs](https://mlsanity.com/paper/2606.14335/) (2026)

## Abstract (arXiv)

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].