Journal article
The planted matching problem: Phase transitions and exact results
The Annals of applied probability, Vol.31(6), pp.2663-2720
12/01/2021
DOI: 10.1214/20-AAP1660
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
- Title: Subtitle
- The planted matching problem: Phase transitions and exact results
- Creators
- Mehrdad Moharrami - University of Illinois Urbana-ChampaignCristopher Moore - Santa Fe InstituteJiaming Xu - Duke University
- Resource Type
- Journal article
- Publication Details
- The Annals of applied probability, Vol.31(6), pp.2663-2720
- DOI
- 10.1214/20-AAP1660
- ISSN
- 1050-5164
- eISSN
- 2168-8737
- Language
- English
- Date published
- 12/01/2021
- Academic Unit
- Computer Science
- Record Identifier
- 9984446428902771
Metrics
1 Record Views