skew_zero_forcing_closure_subset_matroid_closure
Let V be a finite type ([Finite V]), let N : V → Set V be a symmetric neighborhood function satisfying u ∈ N v ↔ v ∈ N u for all u, v : V, and let M be a matroid on V with ground set M.E = Set.univ. If every neighborhood N v is cyclic in M (∀ v : V, Matroid.IsCyclic M (N v)), then for every subset S : Set V, the skew zero forcing closure is contained in the matroid closure: skew_zero_forcing_closure N S ⊆ M.closure S.
Statement
theorem skew_zero_forcing_closure_subset_matroid_closure {V : Type*} [Finite V] (N : V → Set V) (h_symm : ∀ u v : V, u ∈ N v ↔ v ∈ N u) (M : Matroid V) (hE : M.E = Set.univ) (h_cyc : ∀ v : V, Matroid.IsCyclic M (N v)) (S : Set V) : skew_zero_forcing_closure N S ⊆ M.closure S
- Source
- arXiv:2611.15741 Proposition 2.10
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- Matroid.IsCyclicA subset X of the ground set of a matroid M is cyclic if it is a union of circuits of M.
- skew_zero_forcing_closureThe skew zero forcing closure scl(S) of a subset S of vertices in a graph with neighborhood function N is the set of all vertices forced…
- SkewZeroForcedThe skew zero forcing closure predicate on vertices V: a vertex is forced from an initial set S under neighborhood function N if it is in…
Read back from the Lean
Let $V$ be a finite type. Let $N : V \to \text{Set } V$ be a neighborhood function on $V$ such that $N$ is symmetric (for all $u, v \in V$, $u \in N(v) \iff v \in N(u)$). Let $M$ be a matroid on ground type $V$ whose ground set $M.E$ is all of $V$ ($M.E = \text{Set.univ}$). Assume that for every vertex $v \in V$, its neighborhood $N(v)$ is a cyclic set in $M$ (Matroid.IsCyclic M (N v)). Then for any subset $S \subseteq V$, the skew zero forcing closure of $S$ with respect to $N$ is a subset of the matroid closure of $S$ in $M$ (M.closure 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 proof proceeds by induction on the derivation showing that a vertex is skew-zero-forced from $S$. Initial vertices in $S$ trivially belong to the matroid closure because the ground set is universal. In the inductive step, when a vertex $w'$ is forced by $u$, the cyclic assumption guarantees that the neighborhood $N(u)$ is a union of circuits, so $w'$ belongs to some circuit $C \subseteq N(u)$; since every other vertex in $C$ is already in the closure by induction, the circuit property $w' \in M.\operatorname{closure}(C \setminus \{w'\})$ together with monotonicity and idempotence of the closure operator forces $w' \in M.\operatorname{closure}(S)$.
To show that the skew zero forcing closure of $S$ is contained in $M.\operatorname{closure}(S)$, it suffices to prove by induction that every vertex forced from $S$ belongs to $M.\operatorname{closure}(S)$.
We introduce an arbitrary vertex $w$ that is skew-zero-forced from $S$ and proceed by structural induction on the derivation of `SkewZeroForced N S w`.
have _ := h_symm rintro w (hw : SkewZeroForced N S w) induction hw with
Every element of the initial set $S$ belongs to $M.\operatorname{closure}(S)$.
In the base case where $v \in S$, since the matroid ground set is the full universe ($M.E = \operatorname{Set.univ}$), $S \subseteq M.E$. Any element of $S$ therefore belongs to the matroid closure $M.\operatorname{closure}(S)$.
uses
M.mem_closure_of_mem| init v hv => exact M.mem_closure_of_mem hv (by simp [hE])For a vertex $w'$ forced by $u$, there is a circuit $C \subseteq N(u)$ that contains $w'$.
In the induction step, $w' \in N(u)$ is forced by $u$, meaning all other neighbors $x \in N(u) \setminus \{w'\}$ satisfy the induction hypothesis and lie in $M.\operatorname{closure}(S)$. Since $N(u)$ is cyclic in $M$, it is a union of circuits $\mathcal{S}$. Because $w' \in N(u)$, there is some circuit $C \in \mathcal{S}$ containing $w'$.
| step u w' hw' h_ih ih => obtain ⟨𝒮, hC, hU⟩ := h_cyc u have hw'U : w' ∈ ⋃₀ 𝒮 := by rwa [← hU] obtain ⟨C, hCin, hw'C⟩ := hw'U have hC_circ : M.IsCircuit C := hC C hCinThe circuit $C$ is contained in the neighborhood $N(u)$.
Since $N(u)$ is the union of the family $\mathcal{S}$ and $C \in \mathcal{S}$, any element of $C$ belongs to $\bigcup \mathcal{S} = N(u)$.
uses
Set.mem_sUnion_of_memhave hC_sub : C ⊆ N u := by intro x hx rw [hU] exact Set.mem_sUnion_of_mem hx hCin
The rest of the circuit $C \setminus \{w'\}$ is contained in $M.\operatorname{closure}(S)$.
Every element $x \in C \setminus \{w'\}$ belongs to $N(u)$ (since $C \subseteq N(u)$) and is distinct from $w'$. By the induction hypothesis, every such neighbor already belongs to $M.\operatorname{closure}(S)$.
have h_diff_sub : C \ {w'} ⊆ M.closure S := by intro x hx exact ih x (hC_sub hx.1) hx.2
The forced vertex $w'$ belongs to $M.\operatorname{closure}(S)$.
Because $C$ is a circuit containing $w'$, $w'$ is in the closure of $C \setminus \{w'\}$. By monotonicity of the closure operator applied to $C \setminus \{w'\} \subseteq M.\operatorname{closure}(S)$, we have $M.\operatorname{closure}(C \setminus \{w'\}) \subseteq M.\operatorname{closure}(M.\operatorname{closure}(S))$. Since the closure operator is idempotent, the right-hand side is $M.\operatorname{closure}(S)$, concluding that $w' \in M.\operatorname{closure}(S)$.
uses
hC_circ.mem_closure_sdiff_singleton_of_mem,M.closure_mono,M.closure_closurehave hw'_cl : w' ∈ M.closure (C \ {w'}) := hC_circ.mem_closure_sdiff_singleton_of_mem hw'C have h_le := M.closure_mono h_diff_sub rw [M.closure_closure S] at h_le exact h_le hw'_cl
M.mem_closure_of_mem- An element of a subset $X$ of the ground set belongs to the closure of $X$.
Set.mem_sUnion_of_mem- An element of a set in a collection of sets belongs to the union of that collection.
hC_circ.mem_closure_sdiff_singleton_of_mem- For any circuit $C$ and element $e \in C$, $e$ belongs to the closure of $C \setminus \{e\}$.
M.closure_mono- The matroid closure operator is monotone: if $X \subseteq Y$, then $\operatorname{closure}(X) \subseteq \operatorname{closure}(Y)$.
M.closure_closure- The matroid closure operator is idempotent: $\operatorname{closure}(\operatorname{closure}(X)) = \operatorname{closure}(X)$.
- The hypothesis `h_symm` (symmetry of the neighborhood relation) is assumed in the theorem statement and introduced on line 3, but is never used in the proof.
- On line 7, `simp [hE]` automatically discharges the side condition that $S \subseteq M.E$ using the assumption that the ground set $M.E$ is the entire universe.
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.
/-- Skew zero forcing closure is contained in matroid closure when every neighborhood is cyclic. -/theorem skew_zero_forcing_closure_subset_matroid_closure {V : Type*} [Finite V] (N : V → Set V) (h_symm : ∀ u v : V, u ∈ N v ↔ v ∈ N u) (M : Matroid V) (hE : M.E = Set.univ) (h_cyc : ∀ v : V, Matroid.IsCyclic M (N v)) (S : Set V) : skew_zero_forcing_closure N S ⊆ M.closure S := by have _ := h_symm rintro w (hw : SkewZeroForced N S w) induction hw with | init v hv => exact M.mem_closure_of_mem hv (by simp [hE]) | step u w' hw' h_ih ih => obtain ⟨𝒮, hC, hU⟩ := h_cyc u have hw'U : w' ∈ ⋃₀ 𝒮 := by rwa [← hU] obtain ⟨C, hCin, hw'C⟩ := hw'U have hC_circ : M.IsCircuit C := hC C hCin have hC_sub : C ⊆ N u := by intro x hx rw [hU] exact Set.mem_sUnion_of_mem hx hCin have h_diff_sub : C \ {w'} ⊆ M.closure S := by intro x hx exact ih x (hC_sub hx.1) hx.2 have hw'_cl : w' ∈ M.closure (C \ {w'}) := hC_circ.mem_closure_sdiff_singleton_of_mem hw'C have h_le := M.closure_mono h_diff_sub rw [M.closure_closure S] at h_le exact h_le hw'_cl