AFTD Auto-Formalizing Theoretical Domains

zero_forcing_poly_positive_coeff_interval

theoremverified

For any finite graph the positive coefficients of its zero forcing polynomial form an interval.

Statement

theorem zero_forcing_poly_positive_coeff_interval {V : Type*} [Fintype V] (G : SimpleGraph V) (i j k : ℕ) (hij : i ≤ j) (hjk : j ≤ k) (hi : 0 < (zero_forcing_poly G).coeff i) (hk : 0 < (zero_forcing_poly G).coeff k) : 0 < (zero_forcing_poly G).coeff j
Source
Helper for tree_zero_forcing_poly_unimodal, via log-concavity of its coefficient sequence.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • zero_forcing_polyGiven 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…
  • 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.
  • is_zero_forcing_set_monoIf S is a zero forcing set of a simple graph G and S is a subset of S', then S' is also a zero forcing set of G.
  • 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.

The proof, explained

The m-th coefficient of the zero forcing polynomial counts the zero forcing sets of size m, so a coefficient is strictly positive if and only if such a set exists. Given zero forcing sets Si of size i and Sk of size k with i ≤ j ≤ k, the graph has at least k ≥ j vertices. We can therefore expand Si by choosing j - i additional vertices from its complement. Because the zero forcing property is monotone under taking supersets, this enlarged set has size j and is also zero forcing, showing that the j-th coefficient is strictly positive.

  1. Positivity of a coefficient of the zero forcing polynomial is equivalent to the existence of a zero forcing set of that size.

    By `zero_forcing_poly_coeff`, each coefficient `(zero_forcing_poly G).coeff m` is the cardinality of the set of zero forcing sets of size m. Since the vertex set is finite, this collection of subsets is finite by `Set.toFinite`, and therefore by `Set.ncard_pos` its cardinality is strictly positive if and only if the collection is nonempty. Rewriting the hypotheses `hi`, `hk` and the goal reduces the problem to showing that there exists a zero forcing set of size j, given that zero forcing sets of sizes i and k exist.

    lines 2–8

    uses zero_forcing_poly_coeff, Set.toFinite, Set.ncard_pos

      classical
      rw [zero_forcing_poly_coeff] at hi hk ⊢
      have h_fin (m : ℕ) : ({S : Finset V | is_zero_forcing_set G (S : Set V) ∧ S.card = m} : Set (Finset V)).Finite :=
        Set.toFinite _
      rw [Set.ncard_pos (h_fin i)] at hi
      rw [Set.ncard_pos (h_fin k)] at hk
      rw [Set.ncard_pos (h_fin j)]
  2. There exist a zero forcing set Si of size i and a zero forcing set Sk of size k.

    From the nonemptiness of the sets of zero forcing sets of sizes i and k, we extract witness sets: a zero forcing set Si with |Si| = i, and a zero forcing set Sk with |Sk| = k.

    lines 9–10

      obtain ⟨Si, hSi_zf, hSi_card⟩ := hi
      obtain ⟨Sk, -, hSk_card⟩ := hk
  3. j ≤ |V|

    Because Sk is a subset of V, its size k = |Sk| is bounded by the total number of vertices |V| via `Finset.card_le_univ`. Combined with the assumption j ≤ k, linear arithmetic (`omega`) gives j ≤ |V|.

    lines 11–13

    uses Finset.card_le_univ

      have hjV : j ≤ Fintype.card V := by
        have : Sk.card ≤ Fintype.card V := Finset.card_le_univ Sk
        omega
  4. j - |Si| ≤ |Siᶜ|

    By `Finset.card_compl`, the complement of Si has cardinality |V| - |Si|. Since j ≤ |V| and |Si| = i ≤ j, linear integer arithmetic (`omega`) confirms j - |Si| ≤ |V| - |Si| = |Siᶜ|.

    lines 14–16

    uses Finset.card_compl

      have h_compl : j - Si.card ≤ (Siᶜ).card := by
        rw [Finset.card_compl]
        omega
  5. There exists a subset u of the complement Siᶜ of cardinality j - |Si|.

    Since j - |Si| ≤ |Siᶜ|, `Finset.exists_subset_card_eq` ensures there is a subset u ⊆ Siᶜ with exactly j - |Si| elements.

    line 17

    uses Finset.exists_subset_card_eq

      obtain ⟨u, hu_sub, hu_card⟩ := Finset.exists_subset_card_eq h_compl
  6. Si ∪ u is a zero forcing set of size j, which proves the goal.

    We take Si ∪ u as the required witness of size j. Because Si ⊆ Si ∪ u, the monotonicity lemma `is_zero_forcing_set_mono` implies that Si ∪ u is a zero forcing set since Si is. Furthermore, because u ⊆ Siᶜ, Si and u are disjoint (via `disjoint_compl_right`), so `Finset.card_union_of_disjoint` gives |Si ∪ u| = |Si| + |u| = |Si| + (j - |Si|) = j by linear arithmetic (`omega`).

    lines 18–20

    uses is_zero_forcing_set_mono, Finset.card_union_of_disjoint, disjoint_compl_right

      refine ⟨Si ∪ u, is_zero_forcing_set_mono G (by simp) hSi_zf, ?_⟩
      rw [Finset.card_union_of_disjoint (disjoint_compl_right.mono_right hu_sub), hu_card]
      omega
zero_forcing_poly_coeff
The k-th coefficient of the zero forcing polynomial of a graph equals the number of zero forcing sets of vertices of size k.
Set.toFinite
A subset of a type whose elements form a finite type is finite.
Set.ncard_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the total number of elements in the type.
Finset.card_compl
The cardinality of the complement of a subset is the total number of elements minus the cardinality of the subset.
Finset.exists_subset_card_eq
A finite set has a subset of any given size less than or equal to its own cardinality.
is_zero_forcing_set_mono
Any superset of a zero forcing set is also a zero forcing set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
disjoint_compl_right
Every set is disjoint from its complement.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem zero_forcing_poly_positive_coeff_interval {V : Type*} [Fintype V] (G : SimpleGraph V) (i j k : ℕ) (hij : i ≤ j) (hjk : j ≤ k) (hi : 0 < (zero_forcing_poly G).coeff i) (hk : 0 < (zero_forcing_poly G).coeff k) : 0 < (zero_forcing_poly G).coeff j := by  classical  rw [zero_forcing_poly_coeff] at hi hk ⊢  have h_fin (m : ℕ) : ({S : Finset V | is_zero_forcing_set G (S : Set V) ∧ S.card = m} : Set (Finset V)).Finite :=    Set.toFinite _  rw [Set.ncard_pos (h_fin i)] at hi  rw [Set.ncard_pos (h_fin k)] at hk  rw [Set.ncard_pos (h_fin j)]  obtain ⟨Si, hSi_zf, hSi_card⟩ := hi  obtain ⟨Sk, -, hSk_card⟩ := hk  have hjV : j ≤ Fintype.card V := by    have : Sk.card ≤ Fintype.card V := Finset.card_le_univ Sk    omega  have h_compl : j - Si.card ≤ (Siᶜ).card := by    rw [Finset.card_compl]    omega  obtain ⟨u, hu_sub, hu_card⟩ := Finset.exists_subset_card_eq h_compl  refine ⟨Si ∪ u, is_zero_forcing_set_mono G (by simp) hSi_zf, ?_⟩  rw [Finset.card_union_of_disjoint (disjoint_compl_right.mono_right hu_sub), hu_card]  omega
See it in the graphDiscuss this resultChallenge it