Same-phase stability for graph polynomials

The multivariate independence polynomial of a finite graph is same-phase stable exactly when the graph is claw-free.

Results

A multivariate polynomial $P$ is same-phase stable if $P(w_1x,\dotsc,w_nx)$ is real-rooted in $x$ for every choice of nonnegative weights $w_i$.

Theorem (Leake–Ryder). For a finite graph $G$, the multivariate independence polynomial $\sum_S\prod_{v\in S}x_v$, summed over the independent sets $S$, is same-phase stable if and only if $G$ is claw-free. In particular the independence polynomial of a claw-free graph is real-rooted (the Chudnovsky–Seymour theorem, obtained by setting every variable equal to $x$).

Theorem (weights). If the weighted independence polynomial $\sum_S\prod_{v\in S}w_v\,x^{|S|}$ is real-rooted for every choice of nonnegative vertex weights $w$, then $G$ is claw-free. Weights $1$ on a claw and $0$ elsewhere give $1+4x+3x^2+x^3$, which has non-real roots.

Theorem (matchings). The edge-variable matching polynomial $\sum_M\prod_{e\in M}x_e$, summed over the matchings $M$ of $G$, is same-phase stable.

References

The first theorem is due to Leake and Ryder [LR19]. See also the discussion of same-phase stability on symmetricfunctions.com.

  1. [LR19] Jonathan D. Leake & Nick R. Ryder. Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial. Algebraic Combinatorics, 2(5), 781-802, 2019.
    BibTeX
    @article{LeakeRyder2019,
    	author = {Leake, Jonathan D. and Ryder, Nick R.},
    	title = {Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial},
    	journal = {Algebraic Combinatorics},
    	publisher = {MathOA foundation},
    	volume = {2},
    	number = {5},
    	year = {2019},
    	pages = {781-802},
    	doi = {10.5802/alco.63},
    	language = {en},
    	url={alco.centre-mersenne.org/item/ALCO_2019__2_5_781_0/}
    }

Definitions

  • Same-phase stability

    RealRooted.SamePhaseStablesource
    def SamePhaseStable {sigma : Type*} (P : MvPolynomial sigma ℝ) : Prop :=
      ∀ wt : sigma → ℝ, (∀ i, 0 ≤ wt i) → (commonPhaseRestriction wt P).Splits
  • Multivariate independence polynomial

    RealRooted.Graph.multivariateIndepPolysource
    def multivariateIndepPoly {V : Type u} [Fintype V]
        (G : _root_.SimpleGraph V) : MvPolynomial V ℝ := by
      classical
      exact ∑ s ∈ indepSetsOn G Finset.univ,
        ∏ v ∈ s, MvPolynomial.X v
  • Edge-variable matching polynomial

    RealRooted.Graph.multivariateMatchingPolynomialByEdgessource
    def multivariateMatchingPolynomialByEdges {V : Type u} [Fintype V]
        (G : _root_.SimpleGraph V) : MvPolynomial G.edgeSet ℝ := by
      classical
      exact ∑ M ∈ (Finset.univ.filter fun M : Finset G.edgeSet =>
          IsMatchingEdgeFinset G M),
        ∏ e ∈ M, MvPolynomial.X e

Theorems

  • Leake–Ryder: same-phase stable if and only if claw-freeMain result

    RealRooted.Graph.multivariateIndepPoly_samePhaseStable_iff_clawFreesource
    theorem multivariateIndepPoly_samePhaseStable_iff_clawFree
        {V : Type u} [Fintype V] (G : _root_.SimpleGraph V) :
        SamePhaseStable (multivariateIndepPoly G) ↔ ClawFree G
  • Chudnovsky–Seymour via Leake–Ryder

    RealRooted.Graph.ClawFree.indepPoly_splits_of_leakeRydersource
    theorem ClawFree.indepPoly_splits_of_leakeRyder
        {V : Type u} [Fintype V] [DecidableEq V]
        {G : _root_.SimpleGraph V} (hG : ClawFree G) :
        (indepPoly G).Splits
  • Real-rooted weighted independence polynomials force claw-freeness

    RealRooted.Graph.clawFree_of_weightedIndepPoly_splitssource
    theorem clawFree_of_weightedIndepPoly_splits
        {V : Type u} [Fintype V] [DecidableEq V]
        (G : _root_.SimpleGraph V) [DecidableRel G.Adj]
        (hall : ∀ wt : V → ℝ, (∀ v, 0 ≤ wt v) →
          (weightedIndepPoly G wt).Splits) :
        ClawFree G
  • The matching polynomial is same-phase stable

    RealRooted.Graph.multivariateMatchingPolynomialByEdges_samePhaseStablesource
    theorem multivariateMatchingPolynomialByEdges_samePhaseStable
        {V : Type u} [Fintype V]
        (G : _root_.SimpleGraph V) :
        SamePhaseStable (multivariateMatchingPolynomialByEdges G)

Lean source RealRooted/Challenges/Stability/LeakeRyder.lean at revision d6670742. Formalized 2026-09-06.