# The Planted Matching Problem: Phase Transitions and Exact Results

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2019.

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

- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [The planted matching problem: Sharp threshold and infinite-order phase transition](https://mlsanity.com/paper/2103.09383/) (2021)
- [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)
- [Detection of Correlated Random Vectors](https://mlsanity.com/paper/2401.13429/) (2024)
- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)
- [Recovery thresholds for hidden weighted sparse graphs](https://mlsanity.com/paper/2606.14335/) (2026)

## Abstract (arXiv)

We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs Kn,n. For some unknown perfect matching M^*, the weight of an edge is drawn from one distribution P if e ∈ M^* and another distribution Q if e notin M^*. Our goal is to infer M^*, exactly or approximately, from the edge weights. In this paper we take P=exp(λ) and Q=exp(1/n), in which case the maximum-likelihood estimator of M^* is the minimum-weight matching Mmin. We obtain precise results on the overlap between M^* and Mmin, i.e., the fraction of edges they have in common. For λ ≥ 4 we have almost perfect recovery, with overlap 1-o(1) with high probability. For λ < 4 the expected overlap is an explicit function α(λ) < 1: we compute it by generalizing Aldous' celebrated proof of the zeta(2) conjecture for the un-planted model, using local weak convergence to relate Kn,n to a type of weighted infinite tree, and then deriving a system of differential equations from a message-passing algorithm on this tree.