not_szf_realizable_of_lt_circuit_flat_card
Let 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 in M, then M is not SZF-realizable by any graph with symmetric neighborhood function.
Statement
theorem not_szf_realizable_of_lt_circuit_flat_card {V : Type*} [Fintype V] (M : Matroid V) (hE : M.E = Set.univ) (h : Fintype.card V < {C : Set V | M.IsCircuit C ∧ M.IsFlat C}.ncard) : ¬ ∃ (N : V → Set V) (_ : ∀ u v, u ∈ N v ↔ v ∈ N u), ∀ S : Set V, skew_zero_forcing_closure N S = M.closure S
- Formalizes
- scout/2611-15741-skew-zero-forcing-matroids.md:277
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- szf_circuit_flat_has_vertex_neighborhoodLet 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…
- 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…
Read back from the Lean
Let $V$ be a finite type, and let $M$ be a matroid on $V$ whose ground set is the entire type ($M.E = \mathrm{Set.univ}$). Suppose that the cardinality of $V$ is strictly less than the number of circuit-flats of $M$ (i.e., subsets $C \subseteq V$ that are simultaneously a circuit and a flat of $M$). Then there does not exist a symmetric neighborhood function $N : V \to \mathrm{Set}(V)$ (satisfying $u \in N(v) \leftrightarrow v \in N(u)$ for all $u, v \in V$) such that for every subset $S \subseteq V$, the skew zero forcing closure of $S$ with respect to $N$ equals the matroid closure $M.\mathrm{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 contradiction. If M were SZF-realized by a symmetric neighborhood function N, then every circuit-flat of M would have to be the neighborhood of some vertex in the graph. This forces the set of circuit-flats to be contained in the range of N, which implies that the number of circuit-flats is at most |range(N)| ≤ |V|, contradicting the hypothesis that M has strictly more circuit-flats than elements.
Assume, for contradiction, that M is SZF-realized by some symmetric neighborhood function N.
We unpack the negated existential statement by assuming there exists a neighborhood function N : V → Set V that is symmetric (u ∈ N(v) ↔ v ∈ N(u)) and whose skew zero forcing closure matches the matroid closure of M on every subset of V.
rintro ⟨N, h_symm, h_realize⟩
Every circuit-flat of M is in the range of N, so the set of circuit-flats is a subset of range(N).
For any set C ⊆ V that is both a circuit and a flat of M, szf_circuit_flat_has_vertex_neighborhood yields a vertex v ∈ V such that N(v) = C. Hence, C belongs to range(N).
uses
szf_circuit_flat_has_vertex_neighborhoodhave hsub : {C : Set V | M.IsCircuit C ∧ M.IsFlat C} ⊆ Set.range N := by rintro C hC obtain ⟨v, hv⟩ := szf_circuit_flat_has_vertex_neighborhood M hE N h_symm h_realize C hC exact ⟨v, hv⟩
The number of circuit-flats of M is at most the cardinality of range(N).
Because V is a finite type, the range of N is finite by Set.finite_range. Since the set of circuit-flats is a subset of this finite set, its cardinality is at most |range(N)| by Set.ncard_le_ncard.
uses
Set.finite_range,Set.ncard_le_ncardhave hfin : (Set.range N).Finite := Set.finite_range N have hle1 : {C : Set V | M.IsCircuit C ∧ M.IsFlat C}.ncard ≤ (Set.range N).ncard := Set.ncard_le_ncard hsub hfin
The cardinality of range(N) is at most |V|.
Using Set.image_univ, range(N) is rewritten as the image N(univ) of the universal set. By Set.ncard_image_le, the cardinality of an image is at most the cardinality of its domain, which is |V| because univ has cardinality card(V). Linear arithmetic (omega) then concludes that |range(N)| ≤ |V|.
uses
Set.image_univ,Set.ncard_image_lehave hle2 : (Set.range N).ncard ≤ Fintype.card V := by rw [← Set.image_univ] have hle := Set.ncard_image_le (s := Set.univ) (f := N) have huni : (Set.univ : Set V).ncard = Fintype.card V := by simp omega
A contradiction is reached between the cardinality bounds.
Combining the hypothesis |V| < |{circuit-flats}| with the derived bounds |{circuit-flats}| ≤ |range(N)| and |range(N)| ≤ |V| produces |V| < |V|, which is impossible. Linear arithmetic (omega) derives False to conclude the proof.
omega
szf_circuit_flat_has_vertex_neighborhood- If a symmetric neighborhood function N SZF-realizes a finite matroid M on ground set V (with M.E = V), then every circuit-flat of M is the neighborhood N(v) of some vertex v.
Set.finite_range- The range of a function whose domain is finite is a finite set.
Set.ncard_le_ncard- If s ⊆ t and t is finite, then the cardinality of s is at most the cardinality of t.
Set.image_univ- The image of the universal set under a function f is equal to the range of f.
Set.ncard_image_le- The cardinality of the image of a finite set under a function is at most the cardinality of the set itself.
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.
/-- A finite matroid whose number of circuit-flats exceeds its ground set cardinality is not SZF-realizable. -/theorem not_szf_realizable_of_lt_circuit_flat_card {V : Type*} [Fintype V] (M : Matroid V) (hE : M.E = Set.univ) (h : Fintype.card V < {C : Set V | M.IsCircuit C ∧ M.IsFlat C}.ncard) : ¬ ∃ (N : V → Set V) (_ : ∀ u v, u ∈ N v ↔ v ∈ N u), ∀ S : Set V, skew_zero_forcing_closure N S = M.closure S := by rintro ⟨N, h_symm, h_realize⟩ have hsub : {C : Set V | M.IsCircuit C ∧ M.IsFlat C} ⊆ Set.range N := by rintro C hC obtain ⟨v, hv⟩ := szf_circuit_flat_has_vertex_neighborhood M hE N h_symm h_realize C hC exact ⟨v, hv⟩ have hfin : (Set.range N).Finite := Set.finite_range N have hle1 : {C : Set V | M.IsCircuit C ∧ M.IsFlat C}.ncard ≤ (Set.range N).ncard := Set.ncard_le_ncard hsub hfin have hle2 : (Set.range N).ncard ≤ Fintype.card V := by rw [← Set.image_univ] have hle := Set.ncard_image_le (s := Set.univ) (f := N) have huni : (Set.univ : Set V).ncard = Fintype.card V := by simp omega omega