Matchings on infinite graphs

DOI10.1007/S00440-012-0453-0zbMATH Open1278.60018arXiv1102.0712OpenAlexW2060019200MaRDI QIDQ377529FDOQ377529

Authors: Charles Bordenave, Marc Lelarge, Justin Salez 

Publication date: 6 November 2013

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1102.0712

Recommendations

• Matchings in Benjamini-Schramm convergent graph sequences
• Statistical Matching Theory
• A normal law for matchings
• Markovian online matching algorithms on large bipartite random graphs
• Atoms of the matching measure

zbMATH Keywords

matchinglocal weak convergenceHeilmann-Lieb theoremrandom sparse graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Title not available (Why is that?)
• Theory of monomer-dimer systems
• Asymptotic Enumeration of Spanning Trees
• Homogeneous multivariate polynomials with the half-plane property
• Processes on unimodular random networks
• Matching theory
• Title not available (Why is that?)
• A survey of max-type recursive distributional equations
• Left and right convergence of graphs with bounded degree
• On limits of finite graphs
• Resolvent of large random graphs
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
• The rank of diluted random graphs
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Karp-Sipser on random graphs with a fixed degree sequence
• Sharp load thresholds for cuckoo hashing
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• Title not available (Why is that?)
• Borel oracles. An analytical approach to constant-time algorithms
• Matchings and walks in graphs
• Title not available (Why is that?)
• The number of matchings in random graphs
• A new approach to the orientation of random hypergraphs

Cited In (26)

• The densest subgraph problem in sparse random graphs
• Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
• Controllability, matching ratio and graph convergence
• Tilings in graphons
• The planted k-factor problem
• Atoms of the matching measure
• Matchings in Benjamini-Schramm convergent graph sequences
• Aggregation models on hypergraphs
• Finite-size corrections for the attractive mean-field monomer-dimer model
• Matchable infinite graphs
• Mean-field monomer-dimer models. A review
• Inverse problem for the mean-field monomer-dimer model with attractive interaction
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• A mean-field monomer-dimer model with randomness: exact solution and rigorous results
• The rank of diluted random graphs
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• A mean-field monomer-dimer model with attractive interaction: exact solution and rigorous results
• Sparse expanders have negative curvature
• First steps in combinatorial optimization on graphons: matchings
• Minimal contagious sets in random regular graphs
• Random-link matching problems on random regular graphs
• Towards an optimal contention resolution scheme for matchings
• Matching polytons
• Matchings in infinite graphs
• Title not available (Why is that?)
• The rank of sparse random matrices

This page was built for publication: Matchings on infinite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q377529)