Correlation Decay for Maximum Weight Matchings on Sparse Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915820822593536 |
|---|---|
| author | Lam, Wai-Kit Sen, Arnab |
| author_facet | Lam, Wai-Kit Sen, Arnab |
| contents | We study correlation decay for the maximum weight matching problem on sparse graphs with i.i.d. edge weights. We show exponential decay of correlations when the underlying graphs are locally tree-like with uniformly bounded degree and the edge weights are exponential. We also prove a polynomial rate of decay of correlations for any finite graph with maximum degree at most three, again for exponential edge weights. As consequences of the correlation decay property, we obtain the existence of the maximum weight matching on infinite graphs, local weak convergence of the maximum weight matching, and a law of large numbers for its total weight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_18861 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Correlation Decay for Maximum Weight Matchings on Sparse Graphs Lam, Wai-Kit Sen, Arnab Probability We study correlation decay for the maximum weight matching problem on sparse graphs with i.i.d. edge weights. We show exponential decay of correlations when the underlying graphs are locally tree-like with uniformly bounded degree and the edge weights are exponential. We also prove a polynomial rate of decay of correlations for any finite graph with maximum degree at most three, again for exponential edge weights. As consequences of the correlation decay property, we obtain the existence of the maximum weight matching on infinite graphs, local weak convergence of the maximum weight matching, and a law of large numbers for its total weight. |
| title | Correlation Decay for Maximum Weight Matchings on Sparse Graphs |
| topic | Probability |
| url | https://arxiv.org/abs/2511.18861 |