  We study the problem of recovering a planted matching in randomly weighted
complete bipartite graphs $K_{n,n}$. For some unknown perfect matching $M^*$,
the weight of an edge is drawn from one distribution $P$ if $e \in 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(\lambda)$ and $Q=\exp(1/n)$, in which case the maximum-likelihood
estimator of $M^*$ is the minimum-weight matching $M_{\text{min}}$. We obtain
precise results on the overlap between $M^*$ 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.

Data Structures and Algorithms;Statistical Mechanics;Combinatorics