Sink polynomials of all orientations of claw-free graphs

The sink polynomial summed over all orientations of a claw-free graph is real-rooted.

Results

For a finite graph $G$, the sink polynomial is $$ S_G(t)=\sum_{O}t^{\operatorname{sink}(O)}, $$ summed over all $2^{|E(G)|}$ orientations $O$ of $G$, where $\operatorname{sink}(O)$ is the number of vertices with no outgoing edge; isolated vertices are sinks.

Identity. For every finite graph $G$, $$ S_G(t+1)=2^{|E(G)|}\sum_{S}\ \prod_{v\in S}2^{-\deg v}\,t^{|S|}, $$ summed over the independent sets $S$ of $G$.

Theorem. If $G$ is a finite claw-free graph, then $S_G(t)$ is real-rooted.

Use

For acyclic orientations see natural unit interval graphs and chordal claw-free graphs.

Proof

Expand $(t+1)^{\operatorname{sink}(O)}$ over the subsets of sinks. The orientations in which every vertex of $S$ is a sink exist only if $S$ is independent, and then there are $2^{|E(G)|-\sum_{v\in S}\deg v}$ of them. This gives the identity. Its right-hand side is a weighted independence polynomial with positive weights, hence real-rooted for claw-free $G$ by the weighted form of the Chudnovsky--Seymour theorem.

References

P. Alexandersson and L. Saud Maia Leite, manuscript (2026). Background on claw-free graphs is on the Chudnovsky--Seymour and Leake--Ryder pages, and on symmetricfunctions.com.

Definitions

  • Sink polynomial over all orientations

    RealRooted.Graph.allOrientationSinkPolynomialsource
    def allOrientationSinkPolynomial (G : _root_.SimpleGraph V) : ℝ[X] := by
      classical
      exact ∑ O : Orientation G, (X : ℝ[X]) ^ O.sinkCount
  • The shifted model: 2^{|E|} times a weighted independence polynomial

    RealRooted.Graph.allOrientationSinkPolynomialShiftedModelsource
    def allOrientationSinkPolynomialShiftedModel
        (G : _root_.SimpleGraph V) : ℝ[X] := by
      classical
      exact C ((2 : ℝ) ^ allOrientationEdgeCount G) *
        weightedIndepPoly G (fun v => ((2 : ℝ)⁻¹) ^ allOrientationDegree G v)

Theorems

  • The shifted sink polynomial as a weighted independence polynomialCoauthored paper

    RealRooted.Graph.allOrientationSinkPolynomial_comp_X_add_onesource
    theorem allOrientationSinkPolynomial_comp_X_add_one {V : Type u} [Fintype V]
        [DecidableEq V] (G : _root_.SimpleGraph V) :
        (allOrientationSinkPolynomial G).comp (X + C 1) =
          allOrientationSinkPolynomialShiftedModel G
  • Claw-free graphs have real-rooted sink polynomialsMain resultCoauthored paper

    RealRooted.Graph.allOrientationSinkPolynomial_splits_of_clawFreesource
    theorem allOrientationSinkPolynomial_splits_of_clawFree {V : Type u} [Fintype V]
        (G : _root_.SimpleGraph V) (hG : ClawFree G) :
        (allOrientationSinkPolynomial G).Splits

Lean source RealRooted/Challenges/Graphs/ClawFreeOrientationSinks.lean at revision d6670742. Formalized 2026-09-12.