Matchings on infinite graphs

Abstract : 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 Erdős-Rényi random graphs.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-00917419
Contributor : Marc Lelarge <>
Submitted on : Wednesday, December 11, 2013 - 6:36:11 PM
Last modification on : Thursday, October 17, 2019 - 12:36:04 PM

Links full text

Identifiers

Citation

Charles Bordenave, Marc Lelarge, Justin Salez. Matchings on infinite graphs. Probability Theory and Related Fields, Springer Verlag, 2013, 157 (1-2), pp.183-208. ⟨10.1007/s00440-012-0453-0⟩. ⟨hal-00917419⟩

Share

Metrics

Record views

704