Matchings on infinite graphs

Charles Bordenave 1 Marc Lelarge 2, 3, 4 Justin Salez 5
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
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.
Type de document :
Article dans une revue
Probability Theory and Related Fields, Springer Verlag, 2013, 157 (1-2), pp.183-208. <10.1007/s00440-012-0453-0>
Liste complète des métadonnées

https://hal.inria.fr/hal-00917419
Contributeur : Marc Lelarge <>
Soumis le : mercredi 11 décembre 2013 - 18:36:11
Dernière modification le : mardi 11 octobre 2016 - 14:04:50

Identifiants

Collections

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>

Partager

Métriques

Consultations de la notice

196