Shi-Chen Jing

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 flu...