
























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。