k4_cycle_matroid_indep
A set of edges is independent in M(K₄) exactly when it is a forest.
Statement
theorem k4_cycle_matroid_indep (S : Set (Fin 6)) [DecidablePred (· ∈ S)] :
k4_cycle_matroid.Indep S ↔ k4_forest (Finset.univ.filter (· ∈ S))- Source
- step towards matroid_common_list_colorable_two_not_of_colorable_two (arXiv:2610.07318 (A note on the list chromatic number of two matroids), Theorem 1.1)
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- k4_cycle_matroidThe cycle matroid M(K₄) on the six edges of K₄.
- k4_forestThe independent sets of the cycle matroid of K₄, with the six edges numbered 01, 23, 02, 13, 03, 12 (so {0,1}, {2,3}, {4,5} are the pairs…
- k4_forest_subsetSubsets of forests of K₄ are forests.
- k4_forest_augThe forests of K₄ satisfy the matroid augmentation axiom.
- Used by 1
- matroid_common_list_colorable_two_not_of_colorable_twoThere are two loopless matroids M₁, M₂ on a common finite ground set (M₁ graphic: three disjoint copies of K₄; M₂ a unit-capacity…
The proof, explained
The cycle matroid M(K₄) is constructed from finite independent sets using the forest predicate `k4_forest`. The general characterization lemma `IndepMatroid.ofFinset_indep` shows that a finset of edges is independent in the matroid if and only if it is a forest. Extensionality identifies the coerced finset of edges in S with S itself, yielding the claimed equivalence.
The finset of elements of S, regarded as a set, is independent in M(K₄) if and only if it is a K₄-forest.
The cycle matroid M(K₄) is defined via `IndepMatroid.ofFinset` with independence given by `k4_forest`. Instantiating the general characterization `IndepMatroid.ofFinset_indep` for the finset I = {x ∈ Fin 6 | x ∈ S} gives the equivalence between matroid independence of ↑I and the forest predicate `k4_forest I`. The four required matroid conditions are supplied: the empty set is a forest (verified computationally by `decide`), forests are closed under taking subsets (`k4_forest_subset`), forests satisfy the augmentation axiom (`k4_forest_aug`), and every finset is contained in the universal ground set (`Set.subset_univ`).
uses
IndepMatroid.ofFinset_indep,k4_forest_subset,k4_forest_aug,Set.subset_univhave h := IndepMatroid.ofFinset_indep (α := Fin 6) Set.univ k4_forest (by decide) k4_forest_subset k4_forest_aug (fun _ _ => Set.subset_univ _) (I := Finset.univ.filter (· ∈ S))
The finset of elements of S, coerced to a set, equals S.
By set extensionality (`ext x`), an edge x belongs to the finset filter {x ∈ Fin 6 | x ∈ S} if and only if x ∈ S, which simplifies directly to an identity.
have hS : ((Finset.univ.filter (· ∈ S) : Finset (Fin 6)) : Set (Fin 6)) = S := by ext x; simp
S is independent in M(K₄) if and only if the finset of elements of S is a K₄-forest.
Substituting the set equality hS into the equivalence h replaces the coerced finset with S, completing the proof.
rw [hS] at h exact h
IndepMatroid.ofFinset_indep- For a matroid constructed from finite sets via `IndepMatroid.ofFinset`, a subset coerced from a finset I is independent in the matroid if and only if I satisfies the independence predicate.
k4_forest_subset- If J is a K₄-forest and I ⊆ J, then I is also a K₄-forest.
k4_forest_aug- If I and J are K₄-forests with |I| < |J|, then there exists an edge e ∈ J \ I such that I ∪ {e} is also a K₄-forest.
Set.subset_univ- Every set is a subset of the universal set.
- On paper, a subset of edges in a finite graph is already finite; in Lean, S is typed as an arbitrary set (`Set (Fin 6)`), while `k4_forest` is defined on finite sets (`Finset (Fin 6)`). The proof must explicitly filter the universal finset by S and prove this coercion equals 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
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.
theorem k4_cycle_matroid_indep (S : Set (Fin 6)) [DecidablePred (· ∈ S)] : k4_cycle_matroid.Indep S ↔ k4_forest (Finset.univ.filter (· ∈ S)) := by have h := IndepMatroid.ofFinset_indep (α := Fin 6) Set.univ k4_forest (by decide) k4_forest_subset k4_forest_aug (fun _ _ => Set.subset_univ _) (I := Finset.univ.filter (· ∈ S)) have hS : ((Finset.univ.filter (· ∈ S) : Finset (Fin 6)) : Set (Fin 6)) = S := by ext x; simp rw [hS] at h exact h