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\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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.14337
curl -X POST /api/v1/records/arxiv/2610.14337/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.14337/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'