Variance Bounds for Minimum Perfect Matching Problem by Random Walk on Multinomial Distribution

We establish variance upper bounds for the minimum perfect matching problem in general metric spaces under a geometric partition condition. As a principal application, let $H_n$ be the minimum perfect matching cost of $n$ independent uniform points in $[0,1{]}^d$, where $n$ is even and $d\ge 2$. We prove $$\mathrm{Var}(H_n)\le Cd{n}^{1-2\mathrm{/}d},$$ where $C$ is independent of $n$ and $d$. This removes the logarithmic losses in earlier upper bounds in every dimension (Talagrand, 1995); in particular, the variance remains bounded in dimension two, answering an open question (Rhee, 1994). The proof relies on constructing a rapidly mixing Markov process with a multinomial stationary distribution.