Mathematics – Probability
Scientific paper
2011-02-03
Mathematics
Probability
23 pages
Scientific paper
Elek and Lippner (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\"os-R\'enyi random graphs.
Bordenave Charles
Lelarge Marc
Salez Justin
No associations
LandOfFree
Matchings on infinite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Matchings on infinite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matchings on infinite graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-427926