matroid_closure_subset_skew_zero_forcing_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 circuit C of M is the neighborhood of some vertex v : V with N v = C (∀ C, M.IsCircuit C → ∃ v : V, N v = C), then for every subset S : Set V, the matroid closure is contained in the skew zero forcing closure: M.closure S ⊆ skew_zero_forcing_closure N S.
Statement
theorem matroid_closure_subset_skew_zero_forcing_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_circ : ∀ C, M.IsCircuit C → ∃ v : V, N v = C) (S : Set V) : M.closure S ⊆ skew_zero_forcing_closure N S
- Source
- arXiv:2611.15741 Proposition 2.10
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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 such that the relation is symmetric (for all $u, v \in V$, $u \in N(v) \leftrightarrow v \in N(u)$). Let $M$ be a matroid on $V$ whose ground set is all of $V$ ($M.E = \text{Set.univ}$). Assume that every circuit of $M$ is the neighborhood of some vertex (for all $C \subseteq V$, if $C$ is a circuit of $M$, then there exists $v \in V$ such that $N(v) = C$). Then for every subset $S \subseteq V$, the matroid closure of $S$ in $M$ is a subset of the skew zero forcing closure of $S$ with respect to $N$.
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
To show that the matroid closure of S is contained in its skew zero forcing closure, let e belong to the matroid closure of S. If e is already in S, it is forced by definition. Otherwise, by the circuit characterization of matroid closure, there is a circuit C containing e with C ⊆ S ∪ {e}; because every circuit is the neighborhood of some vertex v, all neighbors of v other than e belong to S and are thus already forced, allowing v to force e in a single step.
To prove M.closure S ⊆ skew_zero_forcing_closure N S, it suffices to show that an arbitrary element e ∈ M.closure S is skew-zero-forced.
We introduce an arbitrary element e and the hypothesis that e belongs to the closure of S. (The assumptions of symmetry and universal ground set are also acknowledged here.)
have _ := h_symm have _ := hE intro e he
If e ∈ S, then e is in the skew zero forcing closure.
We perform a case analysis on whether e ∈ S. If e ∈ S, it is forced immediately by the base case of the inductive definition of skew zero forcing (SkewZeroForced.init).
uses
SkewZeroForced.initby_cases heS : e ∈ S · exact SkewZeroForced.init e heS
If e ∉ S, there exists a vertex v such that e ∈ N v and N v ⊆ S ∪ {e}.
Since e ∉ S and e is in the matroid closure of S, by Matroid.mem_closure_iff_exists_isCircuit there exists a circuit C ⊆ S ∪ {e} containing e. By the hypothesis that every circuit is a neighborhood (h_circ), C = N v for some vertex v. Substituting this neighborhood for C gives e ∈ N v and N v ⊆ S ∪ {e}.
uses
Matroid.mem_closure_iff_exists_isCircuit· rw [Matroid.mem_closure_iff_exists_isCircuit heS] at he obtain ⟨C, hCsub, hC, heC⟩ := he obtain ⟨v, hv⟩ := h_circ C hC rw [← hv] at heC hCsub
The vertex v forces e, so e belongs to the skew zero forcing closure.
We apply the forcing step rule at v to force e (SkewZeroForced.step): e is a neighbor of v, and for any other neighbor x ∈ N v with x ≠ e, the inclusion N v ⊆ S ∪ {e} implies that x must be in S (the alternative x = e is ruled out by False.elim). Thus each other neighbor x is initially forced (SkewZeroForced.init). Because all other neighbors of v are forced, v forces e, placing e in the skew zero forcing closure.
uses
SkewZeroForced.step,False.elim,SkewZeroForced.inithave h_step : SkewZeroForced N S e := by apply SkewZeroForced.step v e heC intro x hx hxne have hxS : x ∈ S := by have := hCsub hx cases this with | inl h => exact False.elim (hxne h) | inr h => exact h exact SkewZeroForced.init x hxS exact h_step
SkewZeroForced.init- Any element of the initial set S is skew-zero-forced.
Matroid.mem_closure_iff_exists_isCircuit- For an element e not in X, e belongs to the matroid closure of X if and only if there exists a circuit C ⊆ X ∪ {e} containing e.
SkewZeroForced.step- If w is a neighbor of u and every other neighbor of u is already forced, then w becomes forced.
False.elim- From a contradiction (a proof of False), any proposition follows.
- The hypotheses `h_symm` (symmetry of the neighborhood relation) and `hE` (the matroid ground set is `Set.univ`) are included in the theorem signature and placed into scope on lines 3–4, but neither is actually used in the argument.
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.
/-- Matroid closure is contained in skew zero forcing closure when every circuit is a neighborhood. -/theorem matroid_closure_subset_skew_zero_forcing_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_circ : ∀ C, M.IsCircuit C → ∃ v : V, N v = C) (S : Set V) : M.closure S ⊆ skew_zero_forcing_closure N S := by have _ := h_symm have _ := hE intro e he by_cases heS : e ∈ S · exact SkewZeroForced.init e heS · rw [Matroid.mem_closure_iff_exists_isCircuit heS] at he obtain ⟨C, hCsub, hC, heC⟩ := he obtain ⟨v, hv⟩ := h_circ C hC rw [← hv] at heC hCsub have h_step : SkewZeroForced N S e := by apply SkewZeroForced.step v e heC intro x hx hxne have hxS : x ∈ S := by have := hCsub hx cases this with | inl h => exact False.elim (hxne h) | inr h => exact h exact SkewZeroForced.init x hxS exact h_step