Matchings on infinite graphs
From MaRDI portal
Publication:377529
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5485551 (Why is no real title available?)
- scientific article; zbMATH DE number 1354815 (Why is no real title available?)
- scientific article; zbMATH DE number 1139976 (Why is no real title available?)
- scientific article; zbMATH DE number 2042286 (Why is no real title available?)
- A new approach to the orientation of random hypergraphs
- A survey of max-type recursive distributional equations
- Asymptotic Enumeration of Spanning Trees
- Borel oracles. An analytical approach to constant-time algorithms
- Homogeneous multivariate polynomials with the half-plane property
- Karp-Sipser on random graphs with a fixed degree sequence
- Left and right convergence of graphs with bounded degree
- Matching theory
- Matchings and walks in graphs
- Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
- On limits of finite graphs
- Processes on unimodular random networks
- Recurrence of distributional limits of finite planar graphs
- Resolvent of large random graphs
- Sharp load thresholds for cuckoo hashing
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- The number of matchings in random graphs
- The rank of diluted random graphs
- Theory of monomer-dimer systems
- Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
Cited in
(26)- The rank of sparse random matrices
- 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
- Atoms of the matching measure
- The planted k-factor problem
- Matchings in Benjamini-Schramm convergent graph sequences
- Aggregation models on hypergraphs
- Matchable infinite graphs
- Finite-size corrections for the attractive mean-field monomer-dimer model
- 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
- scientific article; zbMATH DE number 7535269 (Why is no real title available?)
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)
