zero_forcing_boundary_monotonicity
Let 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 cardinality of ∂B_{i+1} is at most that of ∂B_i for every i ≥ 0. In particular, the extended cardinality of ∂B_i is at most that of S for every i ≥ 0, and the extended cardinality of ∂cl(S) is at most that of S.
Statement
theorem zero_forcing_boundary_monotonicity {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S (i + 1))).encard ≤ (zero_forcing_boundary G (zero_forcing_seq G S i)).encard) ∧ (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S i)).encard ≤ S.encard) ∧ (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard
- Formalizes
- arXiv:2611.13244, Proposition 2.9 -- Stabilization of the zero forcing number of generalized Petersen graphs
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- zero_forcing_boundaryFor a simple graph G and a subset X of vertices, the boundary ∂X is the set of all vertices x in X that have a neighbor outside X.
- zero_forcing_seqThe sequence of vertex subsets B_i in a simple graph G starting with B_0 = S and iteratively defined by adding all unique outside…
- 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_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_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
Let $V$ be a type, $G$ be a simple graph on $V$, and $S \subseteq V$ be a finite set of vertices. Then all three of the following hold: 1. For all $i \in \mathbb{N}$, the extended cardinality of the zero-forcing boundary of the $(i + 1)$-th step of the zero-forcing sequence of $S$ in $G$ is less than or equal to the extended cardinality of the zero-forcing boundary of the $i$-th step. 2. For all $i \in \mathbb{N}$, the extended cardinality of the zero-forcing boundary of the $i$-th step of the zero-forcing sequence of $S$ in $G$ is less than or equal to the extended cardinality of $S$. 3. The extended cardinality of the zero-forcing boundary of the zero-forcing closure of $S$ in $G$ is less than or equal to the extended cardinality of $S$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem combines three boundary monotonicity properties of zero forcing into a single statement: the boundary size cannot increase from one step to the next, each intermediate boundary size is bounded by |S|, and the boundary size of the closure cl(S) is bounded by |S|. The proof directly constructs the 3-tuple of conjunctions from three constituent lemmas proved earlier.
The boundary monotonicity properties hold: |∂B_{i+1}| ≤ |∂B_i| for all i ≥ 0, |∂B_i| ≤ |S| for all i ≥ 0, and |∂cl(S)| ≤ |S|.
The claim is a conjunction of three statements, proved by pairing together three previously established theorems: `zero_forcing_boundary_mono` gives step-by-step non-expansion of the boundary, `zero_forcing_boundary_cl_le_seq_le` bounds the boundary at each finite step by |S|, and `zero_forcing_boundary_cl_le` bounds the boundary of the closure cl(S) by |S|.
uses
zero_forcing_boundary_mono,zero_forcing_boundary_cl_le_seq_le,zero_forcing_boundary_cl_letheorem zero_forcing_boundary_monotonicity {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S (i + 1))).encard ≤ (zero_forcing_boundary G (zero_forcing_seq G S i)).encard) ∧ (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S i)).encard ≤ S.encard) ∧ (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard := ⟨zero_forcing_boundary_mono G hS, zero_forcing_boundary_cl_le_seq_le G hS, zero_forcing_boundary_cl_le G hS⟩
zero_forcing_boundary_mono- For any finite vertex subset S of a graph G and any index i, the extended cardinality of the boundary of the (i+1)-th zero forcing set is at most that of the i-th zero forcing set.
zero_forcing_boundary_cl_le_seq_le- For any finite vertex subset S of a graph G and any index N, the extended cardinality of the boundary of the N-th zero forcing set is at most the cardinality of S.
zero_forcing_boundary_cl_le- For any finite vertex subset S of a graph G, the extended cardinality of the boundary of the zero forcing closure cl(S) is at most the cardinality of S.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Boundary monotonicity along the zero forcing process: |∂B_{i+1}| ≤ |∂B_i| for all i, |∂B_i| ≤ |S| for all i, and |∂cl(S)| ≤ |S|. -/theorem zero_forcing_boundary_monotonicity {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S (i + 1))).encard ≤ (zero_forcing_boundary G (zero_forcing_seq G S i)).encard) ∧ (∀ i : ℕ, (zero_forcing_boundary G (zero_forcing_seq G S i)).encard ≤ S.encard) ∧ (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard := ⟨zero_forcing_boundary_mono G hS, zero_forcing_boundary_cl_le_seq_le G hS, zero_forcing_boundary_cl_le G hS⟩