The Planted Matching Problem: Phase Transitions and Exact Results

Abstract

We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs $K_{n,n}$. For some unknown perfect matching $M^{\ast }$, the weight of an edge is drawn from one distribution $P$ if $e\in M^{\ast }$ and another distribution $Q$ if $e\notin M^{\ast }$. Our goal is to infer $M^{\ast }$, exactly or approximately, from the edge weights. In this paper we take $P=\exp (\lambda )$ and $Q=\exp (1/n)$, in which case the maximum-likelihood estimator of $M^{\ast }$ is the minimum-weight matching $M_{\text{min}}$. We obtain precise results on the overlap between $M^{\ast }$ and $M_{\text{min}}$, i.e., the fraction of edges they have in common. For $\lambda \ge 4$ we have almost perfect recovery, with overlap $1-o(1)$ with high probability. For $\lambda <4$ the expected overlap is an explicit function $\alpha (\lambda )<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 $K_{n,n}$ to a type of weighted infinite tree, and then deriving a system of differential equations from a message-passing algorithm on this tree.