Matchings on infinite graphs

• 成果类型: Article
• 署名作者: Bordenave, Charles; Lelarge, Marc; Salez, Justin
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Paris Cite
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-012-0453-0
• 发表日期: 2013
• 页码: 183-208
• 关键词: maximum matchings; karp-sipser; LIMITS

摘要

Elek and Lippner (Proc. Am. Math. Soc. 138(8), 2939-2947, 2010) showed that the convergence of a sequence of bounded-degree graphs implies the existence of a limit for the proportion of vertices covered by a maximum matching. We provide a characterization of the limiting parameter via a local recursion defined directly on the limit of the graph sequence. Interestingly, the recursion may admit multiple solutions, implying non-trivial long-range dependencies between the covered vertices. We overcome this lack of correlation decay by introducing a perturbative parameter (temperature), which we let progressively go to zero. This allows us to uniquely identify the correct solution. In the important case where the graph limit is a unimodular Galton-Watson tree, the recursion simplifies into a distributional equation that can be solved explicitly, leading to a new asymptotic formula that considerably extends the well-known one by Karp and Sipser for ErdAs-R,nyi random graphs.