AFTD Auto-Formalizing Theoretical Domains

zero_forcing_finset_iter_decides

theoremverified

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.

  1. 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.

    lines 2–3

    uses zero_forcing_finset_iter_of_stable

      apply zero_forcing_finset_iter_of_stable
      change zero_forcing_finset_step G ((zero_forcing_finset_step G)^[Fintype.card V] S) = _
  2. 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.

    line 4

    uses finset_inflationary_iter_stable_at_card

      apply finset_inflationary_iter_stable_at_card
  3. The 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.

    lines 5–6

    uses Finset.subset_union_left

      intro 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

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
See it in the graphDiscuss this resultChallenge it