zero_forcing_poly_positive_coeff_interval
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.
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.
uses
zero_forcing_poly_coeff,Set.toFinite,Set.ncard_posclassical 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)]
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.
obtain ⟨Si, hSi_zf, hSi_card⟩ := hi obtain ⟨Sk, -, hSk_card⟩ := hk
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|.
uses
Finset.card_le_univhave hjV : j ≤ Fintype.card V := by have : Sk.card ≤ Fintype.card V := Finset.card_le_univ Sk omega
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ᶜ|.
uses
Finset.card_complhave h_compl : j - Si.card ≤ (Siᶜ).card := by rw [Finset.card_compl] omega
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.
uses
Finset.exists_subset_card_eqobtain ⟨u, hu_sub, hu_card⟩ := Finset.exists_subset_card_eq h_complSi ∪ 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`).
uses
is_zero_forcing_set_mono,Finset.card_union_of_disjoint,disjoint_compl_rightrefine ⟨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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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