A cubic variance bound for matching deficiency
Let $M$ be a uniformly random matching of a finite graph, let $D=\nu-\mathbb E|M|$ be its expected deficiency from a maximum matching, and let $V=\operatorname{Var}(|M|)$. Kahn showed that $D$ and $V$ tend to infinity together, proved $D=O(V^4)$ when $V$ is bounded below, and conjectured $D=O(V^3)$. We prove $D\le41V+104V^2+64V^3$ for every graph, confirming the conjecture, and show that the exponent is attained by connected bipartite graphs with perfect matchings. The proof combines alternating-path identities for monomer probabilities with the sharp estimate $|V(G)-V(G-v)|\le1/4$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00240
curl -X POST /api/v1/records/hexagon/2610.00240/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00240/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'