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.

  1. [HL72] Ole J. Heilmann & Elliott H. Lieb. 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}
    }
  2. [Eng07] Alexander Engström. 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}
    }
  3. [CS07] Maria Chudnovsky & Paul Seymour. 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}
    }

Definitions

  • Matching-generating polynomial

    RealRooted.Graph.matchingPolynomialByEdgessource
    def matchingPolynomialByEdges {V : Type u} [Fintype V]
        (G : _root_.SimpleGraph V) : ℝ[X] := by
      classical
      exact ∑ M ∈ (Finset.univ.filter fun M : Finset G.edgeSet =>
          IsMatchingEdgeFinset G M),
        (X : ℝ[X]) ^ M.card
  • Edge-weighted matching-generating polynomial

    RealRooted.Graph.weightedMatchingPolynomialByEdgessource
    def weightedMatchingPolynomialByEdges
        {V : Type u} [Fintype V]
        (G : _root_.SimpleGraph V) (wt : G.edgeSet → ℝ) : ℝ[X] := by
      classical
      exact ∑ M ∈ (Finset.univ.filter fun M : Finset G.edgeSet =>
          IsMatchingEdgeFinset G M),
        (∏ e ∈ M, C (wt e)) * (X : ℝ[X]) ^ M.card
  • Vertex-weighted independence polynomial

    RealRooted.Graph.weightedIndepPolysource
    def weightedIndepPoly {V : Type u} [Fintype V] [DecidableEq V]
        (G : _root_.SimpleGraph V) [DecidableRel G.Adj]
        (wt : V → ℝ) : ℝ[X] :=
      weightedIndepPolyOn G Finset.univ wt
  • Matching polynomial μ_S(x) of the induced subgraph G[S]

    SimpleGraph.matchingPolyOnsource
    noncomputable def matchingPolyOn (S : Finset V) : ℝ[X] :=
      ∑ M ∈ G.matchingsOn S, (-1 : ℝ[X]) ^ M.card * X ^ (S.card - 2 * M.card)
  • Rank-two binomial transform

    RealRooted.Graph.rankTwoBinomialTransformsource
    def rankTwoBinomialTransform (p : ℝ[X]) (M : ℕ) : ℝ[X] :=
      ∑ k ∈ Finset.range (M + 1),
        monomial k
          ((k.factorial : ℝ) *
            ∑ j ∈ Finset.range (p.natDegree + 1),
              p.coeff j * (Nat.choose j k : ℝ) * (Nat.choose (M - j) k : ℝ))
  • Rank-two edge weights a_i b_j + a_j b_i on a complete graph

    RealRooted.Graph.completeGraphRankTwoWeightsource
    def completeGraphRankTwoWeight (a b : V → ℝ) :
        (_root_.SimpleGraph.completeGraph V).edgeSet → ℝ :=
      fun e ↦ Sym2.lift ⟨fun i j ↦ a i * b j + a j * b i, by
        intro i j
        ring⟩ e.1
    
    omit [Fintype V] [DecidableEq V] in

Theorems

  • Heilmann–Lieb: the matching polynomial is real-rooted

    RealRooted.Graph.matchingPolynomialByEdges_splitssource
    theorem matchingPolynomialByEdges_splits
        {V : Type u} [Fintype V] (G : _root_.SimpleGraph V) :
        (matchingPolynomialByEdges G).Splits
  • Deleting a vertex interlaces the matching polynomial

    RealRooted.interlaces_matchingPolyOn_erasesource
    theorem interlaces_matchingPolyOn_erase (S : Finset V) {v : V} (hv : v ∈ S) :
        Interlaces (G.matchingPolyOn (S.erase v)) (G.matchingPolyOn S)
  • Heilmann–Lieb: μ_S is real-rooted

    RealRooted.splits_matchingPolyOnsource
    theorem splits_matchingPolyOn (S : Finset V) : (G.matchingPolyOn S).Splits
  • Heilmann–Lieb root bound |x| ≤ 2√(Δ − 1)

    RealRooted.abs_le_of_isRoot_matchingPolyOnsource
    theorem abs_le_of_isRoot_matchingPolyOn {Δ : ℕ} (hΔ : 2 ≤ Δ) (S : Finset V)
        (hS : ∀ w ∈ S, (S.filter (G.Adj w)).card ≤ Δ) {r : ℝ}
        (hr : (G.matchingPolyOn S).IsRoot r) : |r| ≤ 2 * Real.sqrt (Δ - 1)
  • Engström: weighted independence polynomials of claw-free graphs are real-rooted

    RealRooted.Graph.weightedIndepPoly_splits_of_clawFreesourcestatement on symmetricfunctions.com
    theorem _root_.RealRooted.Graph.weightedIndepPoly_splits_of_clawFree
        {V : Type*} [Fintype V] [DecidableEq V]
        {G : SimpleGraph V} [DecidableRel G.Adj] (hG : Graph.ClawFree G) (wt : V → ℝ)
        (hwt : ∀ v, 0 ≤ wt v) :
        (Graph.weightedIndepPoly G wt).Splits
  • Weighted matching polynomials are real-rootedMain result

    RealRooted.Graph.weightedMatchingPolynomialByEdges_splitssource
    theorem weightedMatchingPolynomialByEdges_splits
        {V : Type u} [Fintype V]
        (G : _root_.SimpleGraph V) (wt : G.edgeSet → ℝ)
        (hwt : ∀ e, 0 ≤ wt e) :
        (weightedMatchingPolynomialByEdges G wt).Splits
  • Weighted matching polynomials are PF polynomials

    RealRooted.Graph.weightedMatchingPolynomialByEdges_isPFPolynomialsource
    theorem weightedMatchingPolynomialByEdges_isPFPolynomial
        {V : Type u} [Fintype V]
        (G : _root_.SimpleGraph V) (wt : G.edgeSet → ℝ)
        (hwt : ∀ e, 0 ≤ wt e) :
        IsPFPolynomial (weightedMatchingPolynomialByEdges G wt)
  • The rank-two binomial transform preserves PF polynomials

    RealRooted.Graph.rankTwoBinomialTransform_isPFsource
    theorem rankTwoBinomialTransform_isPF
        {p : ℝ[X]} (hp : IsPFPolynomial p) (hconst : p.coeff 0 = 1)
        {M : ℕ} (hdegree : p.natDegree ≤ M) :
        IsPFPolynomial (rankTwoBinomialTransform p M)
  • A PF polynomial is a rank-two weighted matching polynomial of K_M

    RealRooted.Graph.exists_nonneg_completeGraphRankTwoWeight_eq_coeff_sumsource
    theorem exists_nonneg_completeGraphRankTwoWeight_eq_coeff_sum
        {p : ℝ[X]} (hp : IsPFPolynomial p) (hconst : p.coeff 0 = 1)
        {M : ℕ} (hdegree : p.natDegree ≤ M) :
        ∃ a b : Fin M → ℝ,
          (∀ i, 0 ≤ a i) ∧
            (∀ i, 0 ≤ b i) ∧
              ∀ k,
                p.eval 1 * weightedMatchingNumber
                    (_root_.SimpleGraph.completeGraph (Fin M))
                    (completeGraphRankTwoWeight a b) k =
                  (k.factorial : ℝ) *
                    ∑ j ∈ Finset.range (p.natDegree + 1),
                      p.coeff j * (Nat.choose j k : ℝ) *
                        (Nat.choose (M - j) k : ℝ)
  • Rank-two weighted matching numbers of a complete graph

    RealRooted.Graph.weightedMatchingNumber_completeGraph_rankTwosource
    theorem weightedMatchingNumber_completeGraph_rankTwo
        (a b : V → ℝ) (k : ℕ) :
        weightedMatchingNumber (_root_.SimpleGraph.completeGraph V)
            (completeGraphRankTwoWeight a b) k =
          (k.factorial : ℝ) *
            RankTwoMatchingModel.disjointSubsetWeight a b k

Lean source RealRooted/Challenges/Graphs/HeilmannLieb.lean at revision d6670742. Formalized 2026-10-06.