math.CO — Combinatorics

A cubic variance bound for matching deficiency

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

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