Title: Maximum weight matching on sparse graphs.
Abstract: We consider the maximum weight matching of a finite bounded degree graph whose edges have i.i.d. random weights. It is natural to ask whether the weight of the maximum weight matching follows a central limit theorem. We obtain an affirmative answer to the above question in the case when the weight distribution is exponential, and the graphs are locally tree-like. The key component of the proof involves a cavity analysis on arbitrary bounded degree trees, which yields a correlation decay for the maximum weight matching. The central limit theorem holds if we take the underlying graph to also be random with i.i.d. degree distribution (configuration model).
This is joint work with Wai-Kit Lam.
