matroid_realization_via_circuit_neighborhoods_szf
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. Suppose that 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), and 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 equals the matroid closure: skew_zero_forcing_closure N S = M.closure S.
Statement
theorem matroid_realization_via_circuit_neighborhoods_szf {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) (h_cyc : ∀ v : V, Matroid.IsCyclic M (N v)) (S : Set V) : skew_zero_forcing_closure N S = M.closure S
- Formalizes
- 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 that is symmetric (for all $u, v \in V$, $u \in N(v) \iff v \in N(u)$). Let $M$ be a matroid on $V$ whose ground set is the full type ($M.E = \text{Set.univ}$). Suppose that:
1. Every circuit of $M$ is the neighborhood of some element: for every $C \subseteq V$, if $C$ is a circuit of $M$ (M.IsCircuit C), then there exists $v \in V$ such that $N(v) = C$.
2. For every $v \in V$, the neighborhood $N(v)$ is a cyclic set of $M$ (Matroid.IsCyclic M (N v)).
Then for any subset $S \subseteq V$, the skew zero forcing closure of $S$ with respect to $N$ (skew_zero_forcing_closure N S) is equal to 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 mutual set inclusion. For the forward inclusion, induction on the definition of skew zero forcing shows that forced elements remain in the matroid closure: the base elements of S are already in the closure, and for any forcing step where u forces w', the cyclicity of N u provides a circuit C ⊆ N u containing w', placing w' in the closure of the remaining circuit elements which already lie in M.closure S. For the reverse inclusion, any element e in M.closure S \ S belongs to a circuit C ⊆ S ∪ {e}, which by hypothesis equals some vertex neighborhood N v; all other vertices of N v belong to S and are thus already forced, allowing v to force e in a single step.
It suffices to show mutual inclusion between the skew zero forcing closure and the matroid closure of S.
We reduce the set equality to two inclusions using anti-symmetry of subsets: skew_zero_forcing_closure N S ⊆ M.closure S and M.closure S ⊆ skew_zero_forcing_closure N S.
uses
Set.Subset.antisymmhave _ := h_symm apply Set.Subset.antisymm
Elements initially in S lie in the matroid closure of S.
We prove the forward inclusion by induction on the definition of SkewZeroForced. For the base case, if v ∈ S, then v is in M.closure S because S is contained in the matroid ground set M.E, which equals univ.
uses
M.mem_closure_of_mem· rintro w hw induction hw with | init v hv => exact M.mem_closure_of_mem hv (by simp [hE])In the inductive forcing step, there is a circuit contained in the neighborhood of the forcing vertex that contains the newly forced vertex.
For the induction step, vertex w' ∈ N u is forced because all other neighbors in N u \ {w'} are already forced (and thus in M.closure S by induction hypothesis). By cyclicity of N u, N u is a union of circuits 𝒮. Because w' ∈ N u, there exists a circuit C ∈ 𝒮 containing w', and C ⊆ N u by the definition of set union.
uses
Set.mem_sUnion_of_mem| 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 hCinThe newly forced vertex w' belongs to the matroid closure of S, completing the forward inclusion.
Every element of C \ {w'} is a neighbor of u distinct from w', hence lies in M.closure S by the induction hypothesis, so C \ {w'} ⊆ M.closure S. Since C is a circuit containing w', w' lies in M.closure (C \ {w'}). Monotonicity and idempotence of the closure operator then imply w' ∈ M.closure (M.closure S) = M.closure S.
uses
hC_circ.mem_closure_sdiff_singleton_of_mem,M.closure_mono,M.closure_closurehave 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
Any element of M.closure S that already belongs to S is in the skew zero forcing closure.
For the reverse inclusion M.closure S ⊆ skew_zero_forcing_closure N S, we consider an arbitrary e ∈ M.closure S and split into cases on whether e ∈ S. If e ∈ S, it is forced immediately by the base rule.
uses
SkewZeroForced.init· intro e he by_cases heS : e ∈ S · exact SkewZeroForced.init e heS
When e ∉ S, there is a vertex v whose neighborhood N v is a circuit containing e and contained in S ∪ {e}.
By the circuit characterization of matroid closure, e ∈ M.closure S with e ∉ S implies the existence of a circuit C ⊆ S ∪ {e} with e ∈ C. By the circuit-neighborhood hypothesis, C = N v for some vertex v, so N v ⊆ S ∪ {e} and e ∈ N v.
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 e is skew zero forced by v, completing the reverse inclusion.
To force e from v using SkewZeroForced.step, we show every other neighbor x ∈ N v \ {e} is already forced. Since N v ⊆ S ∪ {e} and x ≠ e, x must belong to S, so x is initially forced. Hence v forces e in one step, 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
Set.Subset.antisymm- Two sets are equal if each is a subset of the other.
M.mem_closure_of_mem- If X ⊆ M.E, every element of X belongs to the matroid closure of X.
Set.mem_sUnion_of_mem- If an element belongs to a member of a collection of sets, it belongs to the union of the collection.
hC_circ.mem_closure_sdiff_singleton_of_mem- If C is a circuit of a matroid and e ∈ C, then e is in the closure of C \ {e}.
M.closure_mono- The matroid closure operator is monotone: X ⊆ Y implies M.closure X ⊆ M.closure Y.
M.closure_closure- The matroid closure operator is idempotent: M.closure (M.closure X) = M.closure X.
SkewZeroForced.init- Every element of the initial set S is skew zero forced.
Matroid.mem_closure_iff_exists_isCircuit- For an element e ∉ X, e is in 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 skew zero forced, then w is skew zero forced.
False.elim- From a contradiction (False), any proposition follows.
- The hypothesis that the neighborhood function is symmetric (h_symm) is introduced on line 3 but is never used in the argument.
- On line 8, `simp [hE]` automatically discharges the ground-set containment requirement S ⊆ M.E using the assumption that M.E is the universal set.
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 realization via circuit neighborhoods in skew zero forcing (Proposition 2.10). -/theorem matroid_realization_via_circuit_neighborhoods_szf {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) (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 apply Set.Subset.antisymm · rintro w hw 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 · 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