szf_circuit_flat_has_vertex_neighborhood
Let M be a matroid on a finite ground set V with M.E = Set.univ. If M is SZF-realized by a graph with symmetric neighborhood function N (u ∈ N v ↔ v ∈ N u), then for every circuit-flat C of M (a subset C ⊆ V that is both a circuit and a flat of M), there exists a vertex v ∈ V such that N v = C.
Statement
theorem szf_circuit_flat_has_vertex_neighborhood {V : Type*} [Finite V] (M : Matroid V) (hE : M.E = Set.univ) (N : V → Set V) (h_symm : ∀ u v, u ∈ N v ↔ v ∈ N u) (h_realize : ∀ S : Set V, skew_zero_forcing_closure N S = M.closure S) (C : Set V) (hC : M.IsCircuit C ∧ M.IsFlat C) : ∃ v : V, N v = C
- Formalizes
- scout/2611-15741-skew-zero-forcing-matroids.md:268
- 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…
- Used by 1
- not_szf_realizable_of_lt_circuit_flat_cardLet M be a finite matroid on ground set V with M.E = Set.univ. If the number of circuit-flats of M strictly exceeds the number of elements…
Read back from the Lean
Let $V$ be a finite type. Let $M$ be a matroid on $V$ whose ground set is the universe of $V$ ($M.E = \mathrm{Set.univ}$). Let $N : V \to \mathrm{Set}\ V$ be a symmetric neighborhood relation on $V$ (for all $u, v \in V$, $u \in N(v) \iff v \in N(u)$). Assume that for every subset $S \subseteq V$, the skew zero forcing closure of $S$ with respect to $N$ coincides with the matroid closure of $S$ in $M$ (skew_zero_forcing_closure N S = M.closure S). If $C \subseteq V$ is both a circuit and a flat of $M$, then there exists some vertex $v \in V$ such that $N(v) = C$.
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 every circuit-flat C is the neighborhood N u of some vertex u, we pick an element e ∈ C. Because C is both a circuit and a flat, removing e yields a set whose closure is all of C, so by SZF-realizability e must be skew zero forced from C \ {e}. Since e ∉ C \ {e}, it must be forced by a step at some vertex u whose other neighbors are already forced, which implies N u ⊆ C. If N u were a proper subset of C, it would be independent, precluding e from lying in the closure of N u \ {e}, yet u forces e from N u \ {e} in a single step; this contradiction forces N u = C.
The circuit C is nonempty, so there exists e ∈ C, and e ∈ M.closure (C \ {e}).
Since C is a circuit of the matroid M, it cannot be empty; let e ∈ C. In any matroid circuit, removing any element leaves a set whose closure contains that element, so e ∈ M.closure (C \ {e}).
have _ := h_symm have _ := hE obtain ⟨e, he⟩ := hC.1.nonempty have he_cl : e ∈ M.closure (C \ {e}) := hC.1.mem_closure_sdiff_singleton_of_mem he
M.closure (C \ {e}) = C.
We establish the equality by double containment using Set.Subset.antisymm. For the forward direction, C \ {e} ⊆ C by Set.sdiff_subset, and since closure is monotone and C is a flat (meaning M.closure C = C), M.closure (C \ {e}) ⊆ C. For the reverse direction, consider any x ∈ C: if x = e, then x belongs to M.closure (C \ {e}) by the previous step; if x ≠ e, then x ∈ C \ {e}, so it is in M.closure (C \ {e}) trivially.
uses
Set.Subset.antisymm,Set.sdiff_subsethave h_cl_eq : M.closure (C \ {e}) = C := by apply Set.Subset.antisymm · have h_sub : C \ {e} ⊆ C := Set.sdiff_subset have h_le := M.closure_mono h_sub rw [hC.2.closure] at h_le exact h_le · intro x hx by_cases hxe : x = e · subst hxe exact he_cl · exact M.mem_closure_of_mem ⟨hx, hxe⟩
e is skew zero forced from C \ {e}, yet e ∉ C \ {e}.
Since e ∈ C and M.closure (C \ {e}) = C, the SZF-realizability hypothesis implies that e belongs to the skew zero forcing closure of C \ {e}, meaning e is skew zero forced from C \ {e}. At the same time, e ∉ C \ {e} by definition of set difference.
have he_szf : SkewZeroForced N (C \ {e}) e := by have h_mem : e ∈ skew_zero_forcing_closure N (C \ {e}) := by rw [h_realize, h_cl_eq] exact he exact h_mem have he_not_in : e ∉ C \ {e} := by simp
There exists a vertex u ∈ V such that e ∈ N u and every neighbor x ∈ N u with x ≠ e is skew zero forced from C \ {e}.
We case-split on the derivation of the forcing relation for e. It cannot be the base case (SkewZeroForced.init), as that would assert e ∈ C \ {e}, contradicting e ∉ C \ {e} via False.elim. Hence e must be forced by a step rule from some vertex u: e is a neighbor of u, and all other neighbors of u are already skew zero forced from C \ {e}. This u is our candidate vertex.
uses
False.elimcases he_szf with | init _ h_in => exact False.elim (he_not_in h_in) | step u _ heNu h_all => use u
N u ⊆ C.
Let x ∈ N u. If x = e, then x ∈ C because e ∈ C. If x ≠ e, then by the forcing step at u, x is skew zero forced from C \ {e}. By SZF-realizability, x is in the matroid closure of C \ {e}, which equals C. In either case, x ∈ C.
have hNu_sub : N u ⊆ C := by intro x hx by_cases hxe : x = e · subst hxe exact he · have hx_szf : SkewZeroForced N (C \ {e}) x := h_all x hx hxe have hx_cl : x ∈ skew_zero_forcing_closure N (C \ {e}) := hx_szf rw [h_realize, h_cl_eq] at hx_cl exact hx_cl
N u = C.
By Set.Subset.antisymm, it remains to show C ⊆ N u. Suppose for contradiction that C ⊈ N u, so N u is a proper subset of C. Any proper subset of a circuit is an independent set, so N u is independent in M, which implies e ∉ M.closure (N u \ {e}). On the other hand, applying SkewZeroForced.step at u, every other neighbor x ∈ N u \ {e} is in the seed set and hence forced by SkewZeroForced.init; thus e is skew zero forced from N u \ {e}. By SZF-realizability, e ∈ M.closure (N u \ {e}), a contradiction. Thus N u = C.
uses
Set.Subset.antisymm,SkewZeroForced.step,SkewZeroForced.initapply Set.Subset.antisymm hNu_sub by_contra h_not have h_ssub : N u ⊂ C := ⟨hNu_sub, h_not⟩ have h_indep : M.Indep (N u) := hC.1.ssubset_indep h_ssub have h_not_cl : e ∉ M.closure (N u \ {e}) := h_indep.notMem_closure_sdiff_of_mem heNu have h_szf : SkewZeroForced N (N u \ {e}) e := by apply SkewZeroForced.step u e heNu intro x hx hxne exact SkewZeroForced.init x ⟨hx, hxne⟩ have h_cl : e ∈ M.closure (N u \ {e}) := by have h_mem : e ∈ skew_zero_forcing_closure N (N u \ {e}) := h_szf rwa [h_realize] at h_mem exact h_not_cl h_cl
Set.Subset.antisymm- If two sets are each contained in the other, they are equal.
Set.sdiff_subset- The set difference s \ t is a subset of s.
False.elim- From a contradiction (a proof of False), any goal follows.
SkewZeroForced.init- Any vertex belonging to the seed set S is skew zero forced from S.
SkewZeroForced.step- A vertex w in the neighborhood of u is skew zero forced from S if every other neighbor of u is already skew zero forced from S.
- Lines 8 and 9 record the hypotheses `h_symm` and `hE`; `h_symm` is not explicitly invoked in the proof, while `hE : M.E = Set.univ` is discharged automatically by Lean as a typeclass/autoParam hypothesis for matroid ground set containment.
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.
/-- Every circuit-flat of an SZF-realizable matroid is the neighborhood of some vertex. -/theorem szf_circuit_flat_has_vertex_neighborhood {V : Type*} [Finite V] (M : Matroid V) (hE : M.E = Set.univ) (N : V → Set V) (h_symm : ∀ u v, u ∈ N v ↔ v ∈ N u) (h_realize : ∀ S : Set V, skew_zero_forcing_closure N S = M.closure S) (C : Set V) (hC : M.IsCircuit C ∧ M.IsFlat C) : ∃ v : V, N v = C := by have _ := h_symm have _ := hE obtain ⟨e, he⟩ := hC.1.nonempty have he_cl : e ∈ M.closure (C \ {e}) := hC.1.mem_closure_sdiff_singleton_of_mem he have h_cl_eq : M.closure (C \ {e}) = C := by apply Set.Subset.antisymm · have h_sub : C \ {e} ⊆ C := Set.sdiff_subset have h_le := M.closure_mono h_sub rw [hC.2.closure] at h_le exact h_le · intro x hx by_cases hxe : x = e · subst hxe exact he_cl · exact M.mem_closure_of_mem ⟨hx, hxe⟩ have he_szf : SkewZeroForced N (C \ {e}) e := by have h_mem : e ∈ skew_zero_forcing_closure N (C \ {e}) := by rw [h_realize, h_cl_eq] exact he exact h_mem have he_not_in : e ∉ C \ {e} := by simp cases he_szf with | init _ h_in => exact False.elim (he_not_in h_in) | step u _ heNu h_all => use u have hNu_sub : N u ⊆ C := by intro x hx by_cases hxe : x = e · subst hxe exact he · have hx_szf : SkewZeroForced N (C \ {e}) x := h_all x hx hxe have hx_cl : x ∈ skew_zero_forcing_closure N (C \ {e}) := hx_szf rw [h_realize, h_cl_eq] at hx_cl exact hx_cl apply Set.Subset.antisymm hNu_sub by_contra h_not have h_ssub : N u ⊂ C := ⟨hNu_sub, h_not⟩ have h_indep : M.Indep (N u) := hC.1.ssubset_indep h_ssub have h_not_cl : e ∉ M.closure (N u \ {e}) := h_indep.notMem_closure_sdiff_of_mem heNu have h_szf : SkewZeroForced N (N u \ {e}) e := by apply SkewZeroForced.step u e heNu intro x hx hxne exact SkewZeroForced.init x ⟨hx, hxne⟩ have h_cl : e ∈ M.closure (N u \ {e}) := by have h_mem : e ∈ skew_zero_forcing_closure N (N u \ {e}) := h_szf rwa [h_realize] at h_mem exact h_not_cl h_cl