The planted matching problem: Phase transitions and exact results

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 ∈/ 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, that is, 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 ζ(2) conjecture for the unplanted 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.

Duke Scholars

Author Jiaming Xu Fuqua School of Business