\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern,microtype,amsmath,amssymb,amsthm,mathtools} \usepackage[a4paper,hmargin=23mm,vmargin=25mm]{geometry} \usepackage{tikz} \usetikzlibrary{positioning} \usepackage{xcolor} \usepackage{hyperref} \hypersetup{pdftitle={A cubic variance bound for matching deficiency},pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark}\newtheorem{remark}[theorem]{Remark} \DeclareMathOperator{\Var}{Var}\DeclareMathOperator{\Cov}{Cov} \newcommand{\E}{\mathbb E}\newcommand{\PP}{\mathbb P} \title{A cubic variance bound for matching deficiency\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}} \author{Mat\v{e}j Kripner \qquad V\'aclav Rozho\v{n} \qquad Robert \v{S}\'amal\\[0.4em] Martin \v{S}indel\'a\v{r} \qquad Adri\'an Z\'ame\v{c}n\'ik}\date{} % Collection typography; mathematical statements and proofs are unchanged. \definecolor{BolzanoInk}{HTML}{24445C} \hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk, urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}} \urlstyle{same} \setlength{\emergencystretch}{2em} \let\BolzanoBibliography\thebibliography \renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright} \begin{document}\maketitle \begin{abstract} Let $M$ be a uniformly random matching of a finite graph, let $D=\nu-\E|M|$ be its expected deficiency from a maximum matching, and let $V=\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$. \end{abstract} \section{Introduction} \subsection{Background and the source problem} A uniformly chosen matching need not be close to a maximum matching. The quantity $D=\nu-\E|M|$ measures this gap, whereas $V=\Var(|M|)$ measures the fluctuations around the mean. These are different features of a distribution: concentration alone does not generally force its mean to approach the largest possible value. Kahn's normal law for matchings shows that graph structure nevertheless ties them together. The question addressed here is how large the gap can be when the fluctuations are prescribed. All graphs below are finite and simple; $\operatorname{Vert}(H)$ denotes the vertex set of a graph $H$. A matching is a set of pairwise vertex-disjoint edges, and the empty matching is included. Write $Z(G)$ for the number of matchings, $\nu(G)$ for the maximum matching size, and \[ \mu(G)=\E|M|,\qquad V(G)=\Var(|M|),\qquad D(G)=\nu(G)-\mu(G),\qquad \sigma(G)=\sqrt{V(G)}, \] where $M$ is uniform on all matchings of $G$. In the language of the monomer--dimer model, selected edges are dimers and uncovered vertices are monomers. Uniform sampling is the model at dimer activity one. The connection with normal approximation comes from the real-rootedness theorem of Heilmann and Lieb~\cite{HL}. The polynomial $Z_G(z)=\sum_M z^{|M|}$ has only negative real zeros. Factoring its normalized version into linear factors represents $|M|$ in distribution as a sum of independent Bernoulli variables. Godsil~\cite{GodsilNormal} used this representation to study asymptotic normality; the criterion, restated in \cite[Theorem~1.1]{Kahn}, is $V(G_n)\to\infty$. Kahn~\cite[Theorem~1.6]{Kahn} proved that this is equivalent to $D(G_n)\to\infty$. His quantitative argument passes through a weighted vertex-cover parameter and gives $D=O(V^4)$ when $V$ is bounded below \cite[Theorem~1.10 and discussion preceding (8)]{Kahn}. He proposed the sharper comparison below. \begin{conjecture}[Kahn, {\cite[(8)]{Kahn}}]\label{conj} For every fixed $c>0$ there is a constant $C_c$ such that every finite simple graph with $\sigma(G)\ge c$ satisfies $D(G)\le C_c\sigma(G)^6$. \end{conjecture} Kahn's Example~7.2 has $D=\Theta(V^3)$, so the proposed exponent is already necessary among general graphs. The lower bound on $\sigma$ is essential. The star $K_{1,m}$ has exactly $m+1$ matchings: the empty matching and its $m$ single-edge matchings. Its size is Bernoulli with parameter $m/(m+1)$, giving \begin{equation}\label{star} D=\frac1{m+1},\qquad V=\frac{m}{(m+1)^2}. \end{equation} Thus $D$ and $V$ have the same small order, while $D/V^3$ diverges. A uniform estimate must retain a lower-order term. \subsection{Main results} We prove Kahn's conjecture in the following uniform form. \begin{enumerate} \item Theorem~\ref{main} gives the uniform inequality $D\le41V+104V^2+64V^3$, and hence Conjecture~\ref{conj}. \item Lemma~\ref{deletion} gives $|V(G)-V(G-v)|\le1/4$, with the same sharp constant at every common positive dimer activity. \item Theorem~\ref{sharp} gives $D=\Theta(V^3)$ with $V\to\infty$ for connected bipartite graphs having perfect matchings. \end{enumerate} The last assertion locates the sharp exponent in a more restricted class than Kahn's original example. The universal deficiency inequality is proved for uniform matchings; the activity-general statement concerns the deletion lemma. \subsection{Related work} \emph{Matchings and the monomer--dimer model.} Matchings are a central object of combinatorics; see Lov\'asz and Plummer~\cite{LovaszPlummer} for the structural theory, including the Gallai--Edmonds decomposition, and Godsil~\cite{GodsilWalks} for the matching polynomial. Heilmann and Lieb~\cite{HL} introduced the real-rootedness of the matching polynomial in the study of monomer--dimer systems. Uniform and weighted random matchings are also central algorithmically: Jerrum and Sinclair~\cite{JS} showed that the monomer--dimer Markov chain mixes rapidly, giving approximate counting and sampling of matchings at every positive activity. \emph{Real-rooted distributions.} Harper~\cite{Harper} introduced the method of writing a random variable whose generating polynomial has only real zeros as a sum of independent Bernoulli variables, and used it to prove asymptotic normality of Stirling numbers. Pitman~\cite{Pitman} surveys the resulting probabilistic bounds on coefficients, means and modes of such distributions. Michelen and Sahasrabudhe show that central limit theorems persist when the zeros of the generating polynomial merely avoid a neighbourhood of $1$ in a suitable sense~\cite{MS}. The polynomial viewpoint supplies powerful limit theorems, but does not by itself settle the optimal comparison with deficiency. Lebowitz, Pittel, Ruelle and Speer~\cite[Theorem~3.1]{LPRS} obtain a normal-approximation error of order $V^{-1/2}$ for counting distributions whose generating polynomials have zeros in the closed left half-plane. Their framework includes matchings and more general graph-counting models. Du, Chao and Yeh~\cite{DCY} develop sufficient normality criteria based on coefficients, with applications to matching numbers and Laplacian coefficients. Zhang, Brunetti and Wang~\cite{ZBW} give further criteria for graph polynomials, including the Laplacian matching polynomial and characteristic polynomials of positive semidefinite graph matrices. This line of work supplies criteria for normal approximation. The present question is the quantitative comparison between $V$ and the deficiency $\nu-\mu$ in the uniform matching measure. More precise estimates are available under regularity assumptions. For a $d$-regular graph on $n$ vertices, Kahn and Kim \cite[Theorem~1.1]{KahnKim} show, uniformly as $d\to\infty$, that each monomer probability is asymptotic to $d^{-1/2}$ and that $V\sim n/(4\sqrt d)$. The situation changes for linear uniform hypergraphs: Lee~\cite[Theorem~1.4]{Lee} disproves the corresponding pointwise prediction for every uniformity at least three. Gupta~\cite[Theorems~1.1--1.2]{Gupta} gives quantitative bounds for the average vacancy in linear hypergraphs, including an order-uniform $O(\log\log d/\log d)$ bound in the regular case. These results concern degree-dependent occupancy estimates. The bound here applies to arbitrary finite simple graphs and uses only their matching-size variance. A separate recent development concerns another question in Kahn's paper. Let $F_M$ be the graph induced by the vertices uncovered by $M$, and set $\lambda(G)=\E\nu(F_M)$. Zheng et al.\ \cite[Appendix~C.7, Theorem~C.7.2 and Corollary~C.7.3]{FAR} construct graphs with $V/\lambda\to\infty$, disproving the universal comparability asked for in Kahn's Question~7.3. Their discussion also recalls Conjecture~\ref{conj}, which involves $D$ instead of $\lambda$. The cubic deficiency bound and the failure of the variance--residual-matching comparison concern these distinct parameter pairs. The proof below also uses classical tools explicitly. Godsil's path-tree identity~\cite{GodsilWalks} transfers a vertex-deletion ratio of matching polynomials to a rooted tree; this identity is restated in \cite[Theorem~3.1]{Lee}. Here its spectral representation yields the variance-deletion estimate in Lemma~\ref{deletion}. The fixed-matching estimates in Lemma~\ref{fixed} are already consequences of Kahn's Lemma~5.1 and Corollary~4.3. Their proofs are included to keep the argument self-contained. \subsection{Why the cubic bound appears} Write $p_v=\PP(v\text{ is uncovered})$ and $h_v=\mu(G)-\mu(G-v)$. Superimposing two independent matchings decomposes their difference into alternating paths and cycles. An odd path contributes one signed unit to the difference of their sizes. Counting these components gives the variance identity and the rooted relation $\sum_v p_vh_v=2V$ in Lemma~\ref{paths}. Truncating an even path at a root, together with the deletion estimate, then gives \[ h_v\ge1-(3/2+2V)p_v. \] Consequently, a vertex with sufficiently small monomer probability has $h_v\ge1/2$: deleting it lowers the mean by a definite amount. The sum identity forces the total monomer mass of all such vertices to be at most $4V$. For intuition, suppose $V\ge1$ and split the vertices at a threshold of order $V^{-1}$. On the low-probability side $L$, the preceding mass bound and the path covariance identity control the expected number of internal matching edges by $O(V^2)$. On the other side $H$, the endpoints of every edge of a fixed matching have product probability of order at least $V^{-2}$. Kahn's fixed-matching estimate bounds the sum of these products by $4V$, so $\nu(G[H])=O(V^3)$. Counting covered vertices in $L$ finally gives \[ D\le\sum_{v\in L}p_v+\E|M\cap E(G[L])|+\nu(G[H]). \] This directly combines terms of orders $V$, $V^2$ and $V^3$. Keeping the threshold $1/(3+4V)$ instead of its large-variance order produces the stated polynomial for all $V\ge0$. All monomer probabilities in this argument belong to the original graph, including when a matching is chosen inside $G[H]$. The sharpness construction uses a different imbalance. Two copies of $K_{t^4,t^4+t^3}$ are joined by $t^3$ disjoint edges between their larger parts. A perfect matching uses every joining edge, but a uniform matching uses only $O(t)$ of them on average. This leaves deficiency of order $t^3$, while the exact conditional distribution gives variance of order $t$. Theorem~\ref{sharp} makes both scales precise. Finally, the next proposition explains why a linear small-variance term is intrinsic to a uniform reformulation of the conjecture. \begin{proposition}\label{globalform} An absolute bound $D(G)\le CV(G)^3$ for graphs with $V(G)\ge1$ is equivalent, up to its constant, to an absolute bound $D(G)\le C'(V(G)+V(G)^3)$ for all graphs. \end{proposition} \begin{proof} The second bound gives the first with constant $2C'$. Conversely, deficiency and variance are additive under disjoint unions: the matching distribution of a disjoint union is the product of its component distributions. If $00$. \end{lemma} \begin{proof} Let $Z_H(z)=\sum_M z^{|M|}$ and use $\mu_H(z),V_H(z)$ for the corresponding mean and variance. With $\partial=z\,d/dz$, \[ \partial\log Z_H(z)=\mu_H(z),\qquad \partial\mu_H(z)=V_H(z). \] Put $p(z)=Z_{G-v}(z)/Z_G(z)$ and $h(z)=\mu_G(z)-\mu_{G-v}(z)$. Then $h=-\partial\log p$ and $\partial h=V_G(z)-V_{G-v}(z)$. We obtain a useful positive representation of $p$ directly. The matching recurrence at a vertex $x$ of $H$ gives \begin{equation}\label{recurrence} \frac{Z_{H-x}(z)}{Z_H(z)}= \left(1+z\sum_{y\in N_H(x)} \frac{Z_{H-x-y}(z)}{Z_{H-x}(z)}\right)^{-1}. \end{equation} Construct the rooted tree $T=T(G,v)$ whose vertices are simple paths starting at $v$, with adjacency defined by extending a path by one vertex. Its root $r$ is the length-zero path. The branch starting through $u$ is $T(G-v,u)$. Induction using \eqref{recurrence} and factorization over tree branches proves $p(z)=Z_{T-r}(z)/Z_T(z)$: both root ratios obey the same recurrence, and the single-vertex ratio is $1$. Let $A$ be the adjacency matrix of $T$. A Schur complement at the root shows that the root entry of $(I+i\sqrt z A)^{-1}$ obeys the same recurrence. Indeed, for branch matrices $A_j$ and branch roots $r_j$, it equals \[ \left(1+z\sum_j[(I+i\sqrt z A_j)^{-1}]_{r_jr_j}\right)^{-1}. \] These inverses exist because $A$ and the $A_j$ are real symmetric. Induction therefore identifies this entry with $p(z)$. Choose a real orthonormal eigenbasis of $A$, write its eigenvalues as $\theta_j$, and let $a_j$ be the squared root coordinates of the eigenvectors. Thus $a_j\ge0$ and $\sum_j a_j=1$. Taking real parts of the spectral decomposition gives, with $\lambda_j=\theta_j^2$, \begin{equation}\label{mixture} p(z)=\sum_j\frac{a_j}{1+z\lambda_j}. \end{equation} Define \[ \alpha_j=\frac{a_j/(1+z\lambda_j)}{p(z)},\qquad r_j=\frac{z\lambda_j}{1+z\lambda_j}. \] The $\alpha_j$ are probabilities and $0\le r_j\le1$. Differentiating \eqref{mixture} yields \[ h=\sum_j\alpha_jr_j,\quad \partial\alpha_j=\alpha_j(h-r_j),\quad \partial r_j=r_j(1-r_j). \] Consequently, \[ \partial h=h+h^2-2\sum_j\alpha_jr_j^2 =h(1-h)-2\Var_\alpha(r). \] Since $r_j^2\le r_j$, its variance lies between $0$ and $h(1-h)$. It follows that $|\partial h|\le h(1-h)\le1/4$, as required. \end{proof} \begin{remark} The constant $1/4$ in Lemma~\ref{deletion} is attained when $G=K_2$: the matching-size variance is $1/4$, and deleting a vertex leaves variance zero. Deletion need not decrease variance. For the two-edge star, $V(K_{1,2})=2/9$, whereas deleting a leaf leaves $K_2$ with variance $1/4$. Thus the sign of the difference cannot be fixed, even for trees. \end{remark} \begin{lemma}\label{truncation} For every vertex $v$, \[ h_v\ge1-p_v(1+2V(G-v))\ge1-(\tfrac32+2V(G))p_v. \] \end{lemma} \begin{proof} Deleting endpoint $v$ from a positive even path $P$ produces an odd path $Q$ in $G-v$, and $q_G(P)=p_vq_{G-v}(Q)$. Each unoriented $Q$ has at most two preimages, obtained by adjoining $v$ at one of its endpoints. Equations \eqref{oddvar} and \eqref{rooteven} give \[ p_v(1-p_v-h_v)\le2p_v^2V(G-v). \] Divide by $p_v>0$ and apply Lemma~\ref{deletion}. \end{proof} \section{A monomer partition and the deficiency bound} The first inequality in the next lemma is Kahn's fixed-matching bound \cite[Lemma 5.1]{Kahn}. Its short conditioning proof is included. The second inequality also follows from his Corollary 4.3; the path proof below keeps the argument within the identities already established here. \begin{lemma}\label{fixed} For every fixed matching $J$ in $G$, \[ \sum_{uv\in J}w_{uv}\le2V(G),\qquad \sum_{uv\in J}p_up_v\le4V(G). \] \end{lemma} \begin{proof} Condition on the exact outside matching $R=M\setminus J$. An edge of $J$ is available if neither endpoint meets $R$. Every subset of available edges is an equally likely completion, because $J$ is a matching. If $A(R)$ is their number, then $|M|\mid R\sim |R|+\operatorname{Bin}(A(R),1/2)$, whence $V(G)\ge\E A(R)/4$. An edge $uv\in J$ is available exactly when it is selected or both endpoints are unmatched. Both disjoint events have probability $w_{uv}$, so $\E A(R)=2\sum_{uv\in J}w_{uv}$. By \eqref{cov}, $p_up_v\le w_{uv}+c^-_{uv}$. To bound the even-path terms, orient each edge of $J$ once and for all. For an even path with endpoints forming an oriented edge $u\to v$ in $J$, delete $v$. The resulting path $Q$ is odd and $q_G(P)\le q_G(Q)$, since every matching avoiding $\operatorname{Vert}(P)$ also avoids $\operatorname{Vert}(Q)$. For a given unoriented $Q$, choose which endpoint is $u$. Its partner $v$ is forced by $J$, and the only possible preimage appends $v$ to the other endpoint of $Q$. There are at most two such choices. Hence $\sum_{uv\in J}c^-_{uv}\le2\sum_{Q\text{ odd}}q_G(Q)^2=2V(G)$. Combining the two estimates proves the second assertion. \end{proof} \begin{lemma}\label{internal} For any vertex set $S$, let $a(S)=\sum_{v\in S}p_v$. Then \[ \E|M\cap E(G[S])|\le\tfrac12a(S)^2+V(G). \] \end{lemma} \begin{proof} Equations \eqref{edgeprob} and \eqref{cov} give $w_{uv}\le p_up_v+c^+_{uv}$ for every edge. The sum of $p_up_v$ over edges in $S$ is at most $a(S)^2/2$. In the remaining sum each odd path is counted at most once, since it has a unique pair of endpoints. Its total is at most $V(G)$ by \eqref{oddvar}. \end{proof} The set of high-probability vertices can be arbitrarily large: isolated vertices all have monomer probability one. The appropriate quantity to control is its matching number, as supplied by Lemma~\ref{fixed}. \begin{theorem}\label{main} Every finite simple graph satisfies \begin{equation}\label{bound} D(G)\le41V(G)+104V(G)^2+64V(G)^3\le116(V(G)+V(G)^3). \end{equation} In particular, $D(G)\le209\sigma(G)^6$ if $V(G)\ge1$. More generally, for $\sigma(G)\ge c>0$, \[ D(G)\le(41c^{-4}+104c^{-2}+64)\sigma(G)^6. \] \end{theorem} \begin{proof} Write $V=V(G)$ and set $B=3/2+2V$, $\tau=1/(2B)$. Partition the vertices as \[ L=\{v:p_v\le\tau\},\qquad H=\operatorname{Vert}(G)\setminus L, \qquad A=\sum_{v\in L}p_v. \] By Lemma~\ref{truncation}, $h_v\ge1/2$ on $L$. Lemma~\ref{paths} therefore gives \begin{equation}\label{mass} A\le2\sum_{v\in L}p_vh_v\le4V. \end{equation} Take a maximum matching $J$ in $G[H]$. Its endpoints have ambient monomer probability exceeding $\tau$, so Lemma~\ref{fixed} implies \begin{equation}\label{high} \tau^2\nu(G[H])\le\sum_{uv\in J}p_up_v\le4V, \qquad \nu(G[H])\le16B^2V. \end{equation} All probabilities here are those of $G$, not of $G[H]$. Write $M_{LL},M_{LH},M_{HH}$ for matching edges in the two parts and across them. Lemma~\ref{internal} and \eqref{mass} give \begin{equation}\label{low} \E|M_{LL}|\le8V^2+V. \end{equation} Every matching has at most $|L|$ edges not entirely in $H$, hence $\nu(G)\le|L|+\nu(G[H])$. Counting covered vertices in $L$ also gives \[ |L|-A=2\E|M_{LL}|+\E|M_{LH}|, \] and therefore \[ \mu(G)=|L|-A-\E|M_{LL}|+\E|M_{HH}|. \] Subtracting and using \eqref{mass}--\eqref{low}, \begin{align*} D(G)&\le A+\E|M_{LL}|+\nu(G[H])\\ &\le4V+(8V^2+V)+16(3/2+2V)^2V\\ &=41V+104V^2+64V^3. \end{align*} The inequality $2V^2\le V+V^3$ gives the second bound in \eqref{bound}. If $V\ge c^2$, then $V\le c^{-4}V^3$ and $V^2\le c^{-2}V^3$, giving the last assertion. No division by $V$ occurred, so edgeless graphs are included. \end{proof} \section{A connected bipartite sharpness family} We give a quantitative construction to locate the optimal exponent within a more restricted class than required in Conjecture~\ref{conj}. \subsection{A one-dimensional variance estimate} \begin{lemma}\label{birth} Suppose $X$ is supported on $\{0,\ldots,N\}$ with positive probabilities $p_0,\ldots,p_N$, and set $B(r)=(r+1)p_{r+1}/p_r$ for $r