Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
Abstract
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 ≥ 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.
Related
- Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees
- Maximum spread of vertex degrees in a simple graph
- Short Paper No. 1: Relation between integer sequence A319433 and the maximum degrees of finite linear Jaco graphs
- Maximum Likelihood Degrees via One-Edge Chordal Completion
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
BibTeX
@misc{jing2026central,
title = {{Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees}},
author = {Shichen Jing and Wai-Kit Lam and Arnab Sen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39219},
eprint = {2609.39219},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39219},
}
RIS
TY - UNPB
TI - Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
AU - Shichen Jing
AU - Wai-Kit Lam
AU - Arnab Sen
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39219
UR - https://arxiv.org/abs/2609.39219
AB - 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 ≥ 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.
ER -