Minima polynomial of local edge orders

The number of local edge orders of a finite graph, counted by mutual minima, is a real-rooted polynomial.

Results

A local order of a finite graph $G$ chooses, at every vertex $v$, a linear order of the $\deg v$ edges at $v$. An edge is a mutual minimum if it comes first at both endpoints. The minima polynomial is $$ M_G(t)=\sum_{L}t^{\operatorname{mm}(L)}, $$ summed over the $\prod_v\deg v!$ local orders $L$, where $\operatorname{mm}(L)$ is the number of mutual minima.

Identity. For every finite graph $G$, $$ M_G(t+1)=\prod_v\deg v!\ \sum_{S}\ \prod_{uv\in S}\frac{1}{\deg u\,\deg v}\,t^{|S|}, $$ summed over the matchings $S$ of $G$.

Theorem. For every finite graph $G$, $M_G(t)$ is real-rooted.

Theorem (forests). If $F$ is a finite forest, then $M_F(t)$ is the acyclic sink polynomial of the line graph $L(F)$. In particular that polynomial is real-rooted.

Use

For sinks of acyclic orientations see chordal claw-free graphs and all orientations of claw-free graphs.

Proof

The mutual minima of a local order form a matching. For a matching $S$, a fraction $\prod_{uv\in S}1/(\deg u\deg v)$ of the local orders has every edge of $S$ first at both of its endpoints. Summing over the subsets of the mutual minima gives the identity. The right-hand side is a matching polynomial with positive edge weights, hence real-rooted by the Heilmann--Lieb theorem; equivalently, a weighted independence polynomial of the claw-free line graph $L(G)$ (see the Chudnovsky--Seymour and Leake--Ryder pages).

For a forest, the edges at a vertex form a clique of $L(F)$, so local orders are the orientations of $L(F)$ that are acyclic on these cliques, and every cycle of $L(F)$ lies in such a clique. Hence local orders are exactly the acyclic orientations of $L(F)$, and the mutual minima are the sinks.

References

P. Alexandersson and L. Saud Maia Leite, manuscript (2026).

Definitions

  • Local order

    RealRooted.Graph.LocalOrdersource
    def LocalOrder (G : _root_.SimpleGraph V) : Type u :=
      (v : V) → (G.neighborSet v ≃ Fin (minimaDegree G v))
  • Mutual minima

    RealRooted.Graph.LocalOrder.mutualMinimasource
    def mutualMinima (L : LocalOrder G) : Finset G.edgeSet := by
      classical
      exact univ.filter fun e => ∃ (a b : V) (h : G.Adj a b), e.1 = s(a, b) ∧
        (L a ⟨b, h⟩).val = 0 ∧ (L b ⟨a, h.symm⟩).val = 0
  • Minima polynomial

    RealRooted.Graph.minimaPolynomialsource
    def minimaPolynomial (G : _root_.SimpleGraph V) : ℝ[X] :=
      ∑ L : LocalOrder G, X ^ L.mutualMinima.card
  • The weighted matching model

    RealRooted.Graph.minimaPolynomialShiftedModelsource
    def minimaPolynomialShiftedModel (G : _root_.SimpleGraph V) : ℝ[X] :=
      C (minimaNormalization G) *
        weightedMatchingGeneratingPolynomial G (minimaEdgeWeight G)

Theorems

  • The shifted minima polynomial as a weighted matching polynomialCoauthored paper

    RealRooted.Graph.minimaPolynomial_comp_X_add_onesource
    theorem minimaPolynomial_comp_X_add_one (G : _root_.SimpleGraph V) :
        (minimaPolynomial G).comp (X + C 1) = minimaPolynomialShiftedModel G
  • Minima polynomials are real-rootedMain resultCoauthored paper

    RealRooted.Graph.minimaPolynomial_splitssource
    theorem minimaPolynomial_splits (G : _root_.SimpleGraph V) :
        (minimaPolynomial G).Splits
  • Forests: the minima polynomial is the acyclic sink polynomial of the line graphCoauthored paper

    RealRooted.Graph.minimaPolynomial_eq_ordinaryAcyclicSinkPolynomial_lineGraphsource
    theorem minimaPolynomial_eq_ordinaryAcyclicSinkPolynomial_lineGraph
        (F : _root_.SimpleGraph V) (hF : F.IsAcyclic) :
        letI : Fintype F.edgeSet
  • Line graphs of forests have real-rooted acyclic sink polynomialsCoauthored paper

    RealRooted.Graph.ordinaryAcyclicSinkPolynomial_lineGraph_splitssource
    theorem ordinaryAcyclicSinkPolynomial_lineGraph_splits {W : Type u} [Finite W]
        (F : _root_.SimpleGraph W) (hF : F.IsAcyclic) :
        letI : Fintype F.edgeSet

Lean source RealRooted/Challenges/Graphs/MinimaPolynomial.lean at revision d6670742. Formalized 2026-10-02.