Logo image
Back
The planted matching problem: Phase transitions and exact results
Journal article   Peer reviewed

The planted matching problem: Phase transitions and exact results

Mehrdad Moharrami, Cristopher Moore and Jiaming Xu
The Annals of applied probability, Vol.31(6), pp.2663-2720
12/01/2021
DOI: 10.1214/20-AAP1660

View Online

Abstract

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(λ)�=exp(�) and Q=exp(1/n)�=exp(1/�), in which case the maximum-likelihood estimator of M∗�∗ is the minimum-weight matching Mmin�min. We obtain precise results on the overlap between M∗�∗ and Mmin�min, that is, the fraction of edges they have in common. For λ≥4�≥4 we have almost perfect recovery, with overlap 1−o(1)1−�(1) with high probability. For λ<4�<4 the expected overlap is an explicit function α(λ)<1�(�)<1: we compute it by generalizing Aldous’ celebrated proof of the ζ(2)�(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.

Details

Metrics

71 Record Views
Logo image