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
- gt_total_forcing_poly_eqFor every integer t ≥ 24, the total forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
- star_graph_zero_forcing_poly_unimodalFor every natural number n, the complete bipartite graph K_{1, n} on Unit ⊕ Fin n has a unimodal zero forcing polynomial.
- tree_zero_forcing_poly_lower_half_monotoneFor any finite tree $T$ on a finite vertex set $V$, the coefficient of $X^i$ in the zero forcing polynomial of $T$ is less than or equal…
- zero_forcing_poly_ulc_implies_log_concaveFor any finite graph, ultra-log-concavity of its zero forcing coefficients implies ordinary log-concavity.
- gt_connected_forcing_poly_eqFor every integer t ≥ 24, the connected forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
- op_1400_counterexample_order_le_eightyOpen Problem OP-1400: there exists a natural number n ≤ 80 and a simple graph G on Fin n with decidable adjacency whose zero forcing…
- zero_forcing_poly_coeffThe coefficient of x^k in the zero forcing polynomial of G is the number of k-element vertex subsets that are zero forcing sets.
- zero_forcing_poly_positive_coeff_intervalFor any finite graph the positive coefficients of its zero forcing polynomial form an interval.
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