Weighted matchings of the square of a path and simplicial-clique deletion

Deleting a simplicial clique from a claw-free graph gives an interlacing weighted independence polynomial. For line graphs this is vertex deletion for weighted matching polynomials, and for the square of a path it makes consecutive weighted matching polynomials interlace.

Results

The square of the infinite path has vertex set $\mathbb N$ and edges $\{i,i+1\}$ (short) and $\{i,i+2\}$ (long). Give each short edge weight $u$ and each long edge weight $v$. Let $P_n(x)=P_n^{(u,v)}(x)$ be the weighted matching-generating polynomial of the path square on the vertices $0,\dots,n-1$. Then $P_0=P_1=1$, $P_2=1+ux$, $P_3=1+(2u+v)x$ and $$ P_{n+4}=P_{n+3}+u\,x\,P_{n+2}+v\,x\,P_{n+1}+v^2x^2P_n, $$ and this recurrence with these initial rows determines the family.

Theorem (path squares). If $u,v\ge0$, then every $P_n$ has constant term $1$, nonnegative coefficients and only real negative roots, and $P_n\ll P_{n+1}$ for all $n$. If $u>0$, then $\deg P_n=\lfloor n/2\rfloor$.

Theorem (simplicial-clique deletion). Let $G$ be a finite claw-free graph with weights $w(v)\ge0$, let $S$ be a vertex set, and let $K\subseteq S$ be a clique such that, for each $v\in K$, the neighbors of $v$ in $S\setminus K$ form a clique. Then the weighted independence polynomial of $G[S\setminus K]$ interlaces that of $G[S]$.

Corollary (vertex deletion). Let $G$ be a finite graph with edge weights $w(e)\ge0$ and let $v$ be a vertex. The weighted matching-generating polynomial of $G-v$ interlaces that of $G$.

Proof

The weighted matching-generating polynomial of $G$ is the weighted independence polynomial of the claw-free line graph $L(G)$. The edges at a vertex $v$ form a clique of $L(G)$ whose outside neighbors form a clique, so the clique deletion theorem gives the corollary. For path squares, delete the edges at the last vertex.

References

The clique deletion theorem refines the induction in [CS07]; see the Chudnovsky--Seymour page.

  1. [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

  • The weighted matching polynomial of the square of a path

    RealRooted.PathSquareEdge.polynomialsource
    @[expose] def polynomial (u v : ℝ) (n : ℕ) : ℝ[X] :=
      polynomialFrom u v 0 n
  • The weighted matching polynomial after deleting a vertex

    RealRooted.Graph.weightedMatchingGeneratingPolynomialDeleteVertexsource
    @[expose] def weightedMatchingGeneratingPolynomialDeleteVertex
        {V : Type u} [Fintype V] [DecidableEq V]
        (G : _root_.SimpleGraph V) (wt : G.edgeSet → ℝ) (v : V) : ℝ[X] := by
      classical
      exact weightedIndepPolyOn G.lineGraph
        (Finset.univ.filter fun e : G.edgeSet ↦ v ∉ (e : Sym2 V)) wt

Theorems

  • A four-term recurrence for the matching polynomials of path squaresRealRooted original

    RealRooted.PathSquareEdge.polynomial_add_foursource
    theorem polynomial_add_four (u v : ℝ) (n : ℕ) :
        polynomial u v (n + 4) =
          polynomial u v (n + 3) + C u * X * polynomial u v (n + 2) +
            C v * X * polynomial u v (n + 1) +
            C (v ^ 2) * X ^ 2 * polynomial u v n
  • The weighted matching polynomials of path squares are real-rootedRealRooted original

    RealRooted.PathSquareEdge.polynomial_splitssource
    theorem polynomial_splits {u v : ℝ} (hu : 0 ≤ u) (hv : 0 ≤ v) (n : ℕ) :
        (polynomial u v n).Splits
  • Consecutive matching polynomials of path squares interlaceMain resultRealRooted original

    RealRooted.PathSquareEdge.polynomial_strictInterl_succsource
    theorem polynomial_strictInterl_succ {u v : ℝ} (hu : 0 ≤ u) (hv : 0 ≤ v)
        (n : ℕ) : StrictInterl (polynomial u v n) (polynomial u v (n + 1))
  • All roots are negativeRealRooted original

    RealRooted.PathSquareEdge.isRoot_lt_zerosource
    theorem isRoot_lt_zero {u v r : ℝ} (hu : 0 ≤ u) (hv : 0 ≤ v) (n : ℕ)
        (hr : (polynomial u v n).IsRoot r) : r < 0
  • For u > 0 the n-th polynomial has degree ⌊n/2⌋RealRooted original

    RealRooted.PathSquareEdge.polynomial_natDegreesource
    theorem polynomial_natDegree {u v : ℝ} (hu : 0 < u) (hv : 0 ≤ v) :
        ∀ n, (polynomial u v n).natDegree = n / 2
  • The four-term recurrence with its initial rows characterizes the familyRealRooted original

    RealRooted.PathSquareEdge.eq_polynomial_of_satisfiesRecurrencesource
    theorem eq_polynomial_of_satisfiesRecurrence {u v : ℝ} {P : ℕ → ℝ[X]}
        (hP : SatisfiesRecurrence u v P) : ∀ n, P n = polynomial u v n
  • Deleting a simplicial clique interlaces the weighted independence polynomialRealRooted original

    RealRooted.Graph.strictInterl_weightedIndepPolyOn_sdiff_of_simplicialCliquesource
    theorem strictInterl_weightedIndepPolyOn_sdiff_of_simplicialClique
        {V : Type u} [DecidableEq V]
        {G : _root_.SimpleGraph V} [DecidableRel G.Adj] (hG : ClawFree G)
        (wt : V → ℝ) (hwt : ∀ v, 0 ≤ wt v) {S K : Finset V}
        (hK : IsSimplicialCliqueOn G S K) :
        StrictInterl (weightedIndepPolyOn G (S \ K) wt)
          (weightedIndepPolyOn G S wt)
  • Deleting a vertex: the weighted matching polynomial of G - v interlaces that of GRealRooted original

    RealRooted.Graph.matchingPolynomial_strictInterl_deleteVertexsource
    theorem matchingPolynomial_strictInterl_deleteVertex
        {V : Type u} [Fintype V] [DecidableEq V]
        (G : _root_.SimpleGraph V) (wt : G.edgeSet → ℝ)
        (hwt : ∀ e, 0 ≤ wt e) (v : V) :
        StrictInterl (weightedMatchingGeneratingPolynomialDeleteVertex G wt v)
          (weightedMatchingGeneratingPolynomial G wt)

Lean source RealRooted/Challenges/Graphs/PathSquareMatching.lean at revision d6670742. Formalized 2026-11-01.