AFTD Auto-Formalizing Theoretical Domains

zero_forcing_seq

def

The sequence of vertex subsets B_i in a simple graph G starting with B_0 = S and iteratively defined by adding all unique outside neighbors of vertices in B_i.

Statement

def zero_forcing_seq {V : Type*} (G : SimpleGraph V) (S : Set V) : ℕ → Set V
Defined in
arXiv:2611.13244, Section 1 and Section 2 -- Stabilization of the zero forcing number of generalized Petersen graphs
Verified
12 Nov 2026
Axioms
none listed
Used by 4
  • zero_forcing_boundary_monoLet G be a simple graph and S a finite subset of vertices. Then for every natural number i, the extended cardinality of the boundary…
  • zero_forcing_clThe zero forcing closure cl(S) of a subset S of vertices in a simple graph G is the union over all natural numbers i of B_i.
  • zero_forcing_boundary_monotonicityLet G be a simple graph, and let S be a finite subset of vertices. In the zero forcing sequence B_0 = S ⊆ B_1 ⊆ ..., the extended…
  • zero_forcing_boundary_cl_leLet G be a simple graph and S a finite subset of vertices. Then the extended cardinality of the boundary of the closure cl(S) is at most…

Read back from the Lean

For any type V, simple graph G on V, and initial subset S of V, zero_forcing_seq G S is the sequence of vertex subsets of V indexed by ℕ defined recursively by: - At index 0, it is S. - At index n + 1, it is the union of zero_forcing_seq G S n and the set of all vertices w : V for which there exists a vertex x ∈ zero_forcing_seq G S n such that G.neighborSet x \ zero_forcing_seq G S n = {w} (that is, w is the unique neighbor of x not belonging to zero_forcing_seq G S n).

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

/-- The sequence of vertex subsets B_i obtained by iteratively applying the zero forcing color change rule starting from S. -/
def zero_forcing_seq {V : Type*} (G : SimpleGraph V) (S : Set V) : ℕ → Set V
| 0 => S
| n + 1 => (zero_forcing_seq G S n) ∪ {w : V | ∃ x ∈ zero_forcing_seq G S n, G.neighborSet x \ zero_forcing_seq G S n = {w}}
See it in the graphDiscuss this resultChallenge it