zero_forcing_finset_iter_decides
A blue set is zero forcing exactly when the executable parallel forcing process colors every vertex after at most the number of vertices many iterations.
Statement
theorem zero_forcing_finset_iter_decides {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : is_zero_forcing_set G (S : Set V) ↔ zero_forcing_finset_iter G S (Fintype.card V) = Finset.univ
- Source
- Filed by the prover as a step towards another result
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- zero_forcing_finset_stepOne executable parallel zero forcing step from a finite blue set: include each vertex with a blue neighbor whose other neighbors are blue.
- zero_forcing_finset_iterThe finite blue set obtained by iterating the executable parallel zero forcing step k times.
- zero_forcing_finset_iter_of_stableIf a finite parallel forcing iteration has stabilized, the original blue set is zero forcing exactly when the stabilized set is all…
- finset_inflationary_iter_stable_at_cardAn inflationary operation on subsets of a finite n-element set is stationary after n iterations.
- 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
A set S is zero forcing if and only if its parallel color-change process eventually colors every vertex; once the process reaches a fixed point, it cannot color any further vertices (zero_forcing_finset_iter_of_stable). Because the color-change step is inflationary—vertices are only ever added, never removed—the sequence of colored sets must stabilize within at most |V| iterations (finset_inflationary_iter_stable_at_card). Therefore, computing exactly |V| iterations is guaranteed to reach the fixed point, deciding whether S is zero forcing.
To show that S is a zero forcing set if and only if its |V|-th iterate colors all vertices, it suffices to show that the iteration stabilizes at or before step |V|.
By zero_forcing_finset_iter_of_stable, once an iterate of the zero forcing step operator reaches a fixed point, S is zero forcing if and only if that iterate is the entire vertex set Finset.univ. Unfolding the definition of zero_forcing_finset_iter rewrites the goal into showing that the |V|-th iterate of the step operator zero_forcing_finset_step G is indeed a fixed point.
uses
zero_forcing_finset_iter_of_stableapply zero_forcing_finset_iter_of_stable change zero_forcing_finset_step G ((zero_forcing_finset_step G)^[Fintype.card V] S) = _
It suffices to show that the zero forcing step operator is inflationary.
By finset_inflationary_iter_stable_at_card, any operator on subsets of a finite set V that only grows (colored ⊆ step(colored)) is guaranteed to stabilize after at most |V| iterations.
uses
finset_inflationary_iter_stable_at_cardapply finset_inflationary_iter_stable_at_cardThe zero forcing step operator is inflationary: every set of colored vertices is a subset of the set produced by the step.
Let colored be any set of vertices. The step operator is defined as colored ∪ (newly forced vertices). By Finset.subset_union_left, any set is a subset of its union with another set.
uses
Finset.subset_union_leftintro colored exact Finset.subset_union_left
zero_forcing_finset_iter_of_stable- If the k-th iterate of the parallel zero forcing step operator on S is a fixed point, then S is a zero forcing set if and only if that k-th iterate equals the entire vertex set Finset.univ.
finset_inflationary_iter_stable_at_card- For any function f on finite sets of vertices that is inflationary (satisfying S ⊆ f(S) for all S), iterating f at least |V| times reaches a fixed point: f(f^[|V|](S)) = f^[|V|](S).
Finset.subset_union_left- For any finite sets s₁ and s₂, s₁ is a subset of s₁ ∪ s₂.
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_finset_iter_decides {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : is_zero_forcing_set G (S : Set V) ↔ zero_forcing_finset_iter G S (Fintype.card V) = Finset.univ := by apply zero_forcing_finset_iter_of_stable change zero_forcing_finset_step G ((zero_forcing_finset_step G)^[Fintype.card V] S) = _ apply finset_inflationary_iter_stable_at_card intro colored exact Finset.subset_union_left