{"id":"arxiv/2610.14337","url":"https://arxiv.org/abs/2610.14337","tags":["math.PR"],"score":0,"title":"Variance Bounds for Minimum Perfect Matching Problem by Random Walk on Multinomial Distribution","domain":"math.PR","source":"arxiv","authors":["Shi Feng"],"reviews":0,"subject":"math.PR","summary":"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\\ge2$. We prove $$\\operatorname{Var}(H_n)\\le C d n^{1-2/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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-09","reactions":{}}