AFTD Auto-Formalizing Theoretical Domains

szf_circuit_flat_has_vertex_neighborhood

theoremverifiedformalization

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

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.

  1. 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}).

    lines 8–11

      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
  2. 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.

    lines 12–22

    uses Set.Subset.antisymm, Set.sdiff_subset

      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⟩
  3. 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.

    lines 23–28

      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
  4. 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.

    lines 29–32

    uses False.elim

      cases he_szf with
      | init _ h_in => exact False.elim (he_not_in h_in)
      | step u _ heNu h_all =>
        use u
  5. 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.

    lines 33–41

        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
  6. 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.

    lines 42–54

    uses Set.Subset.antisymm, SkewZeroForced.step, SkewZeroForced.init

        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
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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it