Acyclic sink polynomials of natural unit interval graphs

The acyclic sink polynomial of a natural unit interval graph, refined by ascents, is real-rooted.

Results

A natural unit interval graph on the vertices $0,\dots,n-1$ is given by left endpoints $\ell(0)\le\dots\le\ell(n-1)$ with $\ell(i)\le i$: two vertices $i<j$ are adjacent when $\ell(j)\le i$. For such a graph $G$ and a real number $q$, the ascent-refined acyclic sink polynomial is $$ S_G(t;q)=\sum_{O}q^{\operatorname{asc}(O)}\,t^{\operatorname{sink}(O)}, $$ summed over the acyclic orientations $O$ of $G$. Here $\operatorname{sink}(O)$ is the number of vertices with no outgoing edge and $\operatorname{asc}(O)$ is the number of edges directed from a smaller to a larger vertex.

Theorem. For every natural unit interval graph $G$ and every real $q\ge0$, the polynomial $S_G(t;q)$ is real-rooted.

Use

The statistic $\operatorname{asc}$ depends on the natural vertex order. At $q=1$ we obtain the ordinary acyclic sink polynomial. There the theorem is a special case of the result for chordal claw-free graphs, since the natural order is a reverse perfect elimination order and natural unit interval graphs are claw-free. See also the minima polynomial page.

Proof

After a positive normalization, $S_G(t+1;q)$ is a weighted independence polynomial of $G$ with nonnegative vertex weights. It is real-rooted by the weighted form of the Chudnovsky--Seymour theorem.

References

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

Definitions

  • Left-endpoint data of a natural unit interval graph

    RealRooted.UnitIntervalGraph.Datasource
    structure Data (n : ℕ) where
      /-- The left endpoint of the interval of the vertex `i`. -/
      left : Fin n → ℕ
      left_le : ∀ i, left i ≤ i.val
      monotone_left : Monotone left
  • The natural unit interval graph

    RealRooted.UnitIntervalGraph.Data.graphsource
    def graph : _root_.SimpleGraph (Fin n) where
      Adj i j :=
        i.val ≠ j.val ∧ a.left i ≤ j.val ∧ a.left j ≤ i.val
      symm.symm := by
        intro i j h
        exact ⟨h.1.symm, h.2.2, h.2.1⟩
      loopless.irrefl := by simp
  • Ascent-refined acyclic sink polynomial

    RealRooted.Graph.acyclicSinkPolynomialsource
    def acyclicSinkPolynomial (G : _root_.SimpleGraph V) (q : ℝ) : ℝ[X] := by
      classical
      exact ∑ O : Orientation.AcyclicOrientation G,
        orientationMonomial q O.1
  • Shifted weighted independence polynomial

    RealRooted.UnitIntervalGraph.acyclicSinkClosedFormsource
    def acyclicSinkClosedForm (a : Data n) (q : ℝ) : ℝ[X] :=
      C (normalization a q) *
        (Graph.weightedIndepPoly a.graph (weight a q)).comp (X - 1)

Theorems

  • The sink polynomial as a shifted weighted independence polynomialCoauthored paper

    RealRooted.UnitIntervalGraph.acyclicSinkPolynomial_eq_closedFormsource
    theorem acyclicSinkPolynomial_eq_closedForm
        (a : Data n) {q : ℝ} (hq : 0 ≤ q) :
        Graph.acyclicSinkPolynomial a.graph q = acyclicSinkClosedForm a q
  • Acyclic sink polynomials of natural unit interval graphs are real-rootedMain resultCoauthored paper

    RealRooted.UnitIntervalGraph.acyclicSinkPolynomial_splitssource
    theorem acyclicSinkPolynomial_splits
        (a : Data n) {q : ℝ} (hq : 0 ≤ q) :
        (Graph.acyclicSinkPolynomial a.graph q).Splits

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