Optimal unimodular matchings

• 成果类型: Article
• 署名作者: Enriquez, Nathanael; Liu, Mike; Menard, Laurent; Perchet, Vianney
• 署名单位: Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Institut Polytechnique de Paris; ENSAE Paris; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051; 1432-2064
• DOI: 10.1007/s00440-025-01429-x
• 发表日期: 2026-04
• 页码: 1849-1916
• 关键词: Optimal matchings; sparse random graphs; Unimodularity; local convergence

摘要

We consider sequences of finite weighted random graphs that converge locally to unimodular i.i.d. weighted random trees. When the weights are atomless, we prove that the matchings of maximal weight converge locally to a matching on the limiting tree. For this purpose, we introduce and study unimodular matchings on weighted unimodular random trees as well as a notion of optimality for these objects. In this context, we prove that, in law, there is a unique optimal unimodular matching for a given unimodular tree. We then prove that this law is the local limit of the sequence of matchings of maximal weight. Along the way, we also show that this law is characterised by an equation derived from a message-passing algorithm.