Heilmann–Lieb theorem
Matching polynomials are real-rooted, and deleting a vertex gives an interlacing polynomial; the same holds for weighted matching polynomials and for weighted independence polynomials of claw-free graphs.
Results
Let $G$ be a finite simple graph. Its matching-generating polynomial is $$ m_G(x)=\sum_{M}x^{|M|}, $$ where $M$ ranges over the matchings of $G$, that is, the sets of pairwise disjoint edges. For edge weights $w\colon E(G)\to\mathbb R$, the weighted version replaces $x^{|M|}$ by $x^{|M|}\prod_{e\in M}w(e)$. The signed form is $$ \mu_G(x)=\sum_k(-1)^k m_k\,x^{n-2k}, $$ where $m_k$ is the number of $k$-matchings and $n=|V(G)|$; for a vertex set $S$ we write $\mu_S$ for the polynomial of the induced subgraph $G[S]$. Heilmann and Lieb use the signed form $\mu_G$.
Theorem (Heilmann--Lieb). [HL72, Thm. 4.2] The polynomial $m_G(x)$ is real-rooted. If all edge weights are nonnegative, the weighted polynomial is real-rooted with nonnegative coefficients and nonpositive roots, that is, it is a Pólya frequency polynomial.
Theorem (vertex deletion; Heilmann--Lieb, Godsil). For every $S$ and $v\in S$, $\mu_{S\setminus\{v\}}\ll\mu_S$. In particular $\mu_S$ is real-rooted.
Theorem (root bound). Let $\Delta\ge2$ and suppose every vertex of $G[S]$ has degree at most $\Delta$. Then every root $r$ of $\mu_S$ satisfies $|r|\le2\sqrt{\Delta-1}$. Heilmann and Lieb prove the strict inequality.
Theorem (Engström). [Eng07, Thm. 2.5] Let $G$ be a finite claw-free graph and let $w\colon V(G)\to\mathbb R$ be nonnegative. Then $$ I(G,w,x)=\sum_{A}x^{|A|}\prod_{v\in A}w(v), $$ summed over the independent sets $A$ of $G$, is real-rooted.
Theorem (rank-two binomial transform). Let $p$ be a Pólya frequency polynomial with $p(0)=1$, and let $M\ge\deg p$. Then $$ \sum_{k=0}^{M}k!\Bigl(\sum_{j=0}^{\deg p}p_j\binom jk\binom{M-j}k\Bigr)x^k $$ is a Pólya frequency polynomial. Its coefficient of $x^k$ is $p(1)$ times the weighted number of $k$-matchings of the complete graph $K_M$ with edge weights $a_ib_j+a_jb_i\ge0$, for suitable nonnegative vectors $a,b$ determined by $p$.
Proof
The matchings of $G$ are the independent sets of the claw-free line graph $L(G)$, so the weighted matching polynomial of $G$ is a weighted independence polynomial of $L(G)$ and Engström's theorem applies. Engström's theorem is the weighted form of the Chudnovsky--Seymour theorem, proved by the same induction on vertex subsets.
For vertex deletion, use $\mu_S=x\mu_{S\setminus v}-\sum_{u\sim v}\mu_{S\setminus\{v,u\}}$. By induction each $\mu_{S\setminus\{v,u\}}$ interlaces $\mu_{S\setminus v}$, hence so does their sum, and the three-term step gives $\mu_{S\setminus v}\ll\mu_S$. The same recurrence gives the root bound.
For the transform, orienting each edge of a matching of $K_M$ shows that the weighted $k$-matching number with weights $a_ib_j+a_jb_i$ is $k!$ times a sum over pairs of disjoint $k$-subsets. Writing the coefficients of $p$ in this form with nonnegative $a,b$ gives that the transform is $p(1)$ times a weighted matching polynomial of $K_M$.
References
[HL72, Thm. 4.2]; C. D. Godsil, "Matchings and walks in graphs," J. Graph Theory 5 (1981), 285–297; [Eng07, Thm. 2.5]; [CS07]. Background on the matching polynomial and the weighted independence polynomial is on symmetricfunctions.com.
- [HL72] Theory of monomer-dimer systems. Communications in Mathematical Physics, 25(3), 190-232, 1972.
BibTeX
@article{HeilmannLieb1972, doi = {10.1007/bf01877590}, url2 = {https://doi.org/10.1007/bf01877590}, year = {1972}, month = sep, publisher = {Springer Science and Business Media {LLC}}, volume = {25}, number = {3}, pages = {190--232}, author = {Ole J. Heilmann and Elliott H. Lieb}, title = {Theory of monomer-dimer systems}, journal = {Communications in Mathematical Physics} } - [Eng07] Inequalities on well-distributed point sets on circles. Journal of Inequalities in Pure and Applied Mathematics, 8(2), 1-5, 2007.
BibTeX
@article{Engstrom2007, author = {Engström, Alexander}, year = {2007}, pages = {1--5}, number = {2}, eid = {34}, url = {https://emis.de/ft/14440}, title = {Inequalities on well-distributed point sets on circles}, volume = {8}, journal = {Journal of Inequalities in Pure and Applied Mathematics} } - [CS07] The roots of the independence polynomial of a clawfree graph. Journal of Combinatorial Theory, Series B, 97(3), 350-357, 2007.
BibTeX
@article{ChudnovskySeymour2007, doi = {10.1016/j.jctb.2006.06.001}, url2 = {https://doi.org/10.1016/j.jctb.2006.06.001}, year = {2007}, month = may, publisher = {Elsevier {BV}}, volume = {97}, number = {3}, pages = {350--357}, author = {Maria Chudnovsky and Paul Seymour}, title = {The roots of the independence polynomial of a clawfree graph}, journal = {Journal of Combinatorial Theory, Series B} }