Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
We establish an annealed central limit theorem for the maximum weight matching in random graphs with prescribed, uniformly bounded degrees and i.i.d. exponential edge weights, specifically including $d$-regular graphs for $d \ge 2$. The proof decomposes fluctuations into those from edge weights, handled by correlation decay, and those from graph structure, addressed via a novel perturbative correlation decay estimate. This latter estimate, combined with a variance bound, reduces the graph-induced fluctuations to a known CLT for local statistics of the configuration model.
Maximum weight matching in random graphs exhibits Gaussian fluctuations, even when graph structure dominates edge weight randomness.
We prove an annealed central limit theorem for the weight of the maximum weight matching on uniformly random simple graphs with prescribed, uniformly bounded degrees and i.i.d. exponential edge weights. In particular, the result applies to random $d$-regular graphs for every fixed $d \ge 2$. The proof separates the fluctuations arising from the edge weights from those arising from the graph. The correlation decay estimate of Lam and Sen (arXiv:2511.18861) yields Gaussian fluctuations for the former. The main difficulty is to analyze the fluctuations of the conditional mean of the optimal weight given the graph. To address this, we prove a stronger perturbative correlation decay estimate that, together with a variance bound, reduces the problem to the central limit theorem of Barbour and Röllin [Ann. Appl. Probab. 29(2) (2019)] for local statistics of the configuration model.