AFTD Auto-Formalizing Theoretical Domains

zero_forcing_poly

def

Given a finite type V and a simple graph G on V, zero_forcing_poly G is the polynomial in Polynomial ℕ defined as the sum over all subsets S : Finset V of (if is_zero_forcing_set G (S : Set V) then Polynomial.X ^ S.card else 0).

Statement

noncomputable def zero_forcing_poly {V : Type*} [Fintype V] (G : SimpleGraph V) : Polynomial ℕ
Defined in
arXiv:2611.11352 Section 1, Equation (1)
Verified
10 Nov 2026
Axioms
none listed
Built on 1
  • is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
Used by 8

Read back from the Lean

Given a finite type V and a simple graph G on V, zero_forcing_poly G is the polynomial with natural coefficients (Polynomial ℕ) defined as the sum over all finsets S of V of X ^ S.card if S is a zero forcing set in G (meaning every vertex v : V satisfies ZeroForced G S v), and 0 otherwise.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Zero forcing polynomial of a graph. -/
noncomputable def zero_forcing_poly {V : Type*} [Fintype V] (G : SimpleGraph V) : Polynomial ℕ := open scoped Classical in
  ∑ S : Finset V, if is_zero_forcing_set G (S : Set V) then Polynomial.X ^ S.card else 0
See it in the graphDiscuss this resultChallenge it