2019/12/18 by Moharrami, Mehrdad, Moore, Cristopher, Xu, Jiaming · 3 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Statistical Mechanics (cond-mat.stat-mech)
paper · doi:10.48550/arxiv.1912.08880
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, i.e., 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 un-planted 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.