Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.39219
curl -X POST /api/v1/records/arxiv/2609.39219/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.39219/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'