The planted matching problem: sharp threshold and infinite-order phase transition

• 成果类型: Article; Early Access
• 署名作者: Ding, Jian; Wu, Yihong; Xu, Jiaming; Yang, Dana
• 署名单位: Peking University; Yale University; Duke University; Cornell University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-023-01208-6
• 发表日期: 2023
• 关键词: zeta(2) limit; PROOF

摘要

We study the problem of reconstructing a perfect matching M * hidden in a randomly weighted n xn bipartite graph. The edge set includes every node pair in M * and each of the n(n-1) node pairs not in M * independently with probability d/n. The weight of each edge e is independently drawn from the distributionPif e. M * and fromQif e /. M *. We show that if v dB(P, Q) = 1, where B(P, Q) stands for the Bhattacharyya coefficient, the reconstruction error (average fraction of misclassified edges) of the maximum likelihood estimator of M * v converges to 0 as n. 8. Conversely, if dB(P, Q) = 1 + for an arbitrarily small constant > 0, the reconstruction error for any estimator is shown to be bounded away from 0 for both the sparse (fixed d) and dense (growing d) regimes, resolving the conjecture in Moharrami et al. (Ann Appl Probab 31(6):2663-2720, 2021. https://doi.org/10.1214/20- AAP1660) and Semerjian et al. (Phys Rev E 102:022304, 2020. https://doi.org/ 10.1103/PhysRevE.102.022304). Furthermore, in the special case of complete exponentially weighted graph with d = n, P = exp(.), and Q = exp(1/n), for which the sharp threshold simplifies to. = 4,