three_k4_partition_matroid_indep
A set is independent in the partition matroid M₂ exactly when the class map is injective on it.
Statement
theorem three_k4_partition_matroid_indep (S : Set (Fin 3 × Fin 6)) :
three_k4_partition_matroid.Indep S ↔ Set.InjOn three_k4_partition_class 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 2
- three_k4_partition_matroidThe unit-capacity partition matroid M₂ whose independent sets meet every class of three_k4_partition_class at most once.
- three_k4_partition_classThe nine classes of the partition matroid M₂: in copy i the opposite pair a_i (edges 01, 23) is a class, and the classes {b_i⁺, c_{i+1}⁻}…
- 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 partition matroid `three_k4_partition_matroid` is defined as the pullback (via `Matroid.comap`) of the free matroid on `Fin 9` along `three_k4_partition_class`. Independence in a pullback matroid requires that the image be independent in the base matroid and that the pullback map be injective on the subset. Because every subset of the universe is independent in the free matroid, the first condition is trivially satisfied, leaving injectivity of the map as the exact condition for independence.
A subset S ⊆ Fin 3 × Fin 6 is independent in three_k4_partition_matroid if and only if three_k4_partition_class is injective on S. automation
By definition, three_k4_partition_matroid is the pullback of the free matroid on the universal set of Fin 9 under the map three_k4_partition_class. A set S is independent in such a pullback matroid if and only if its image is independent in the base matroid and the map is injective on S. Since every subset of the universal set is independent in the free matroid, the image condition holds trivially, so independence is equivalent to injectivity of three_k4_partition_class on S. The simp tactic unfolds the definition and evaluates these equivalences automatically.
uses
three_k4_partition_matroidsimp [three_k4_partition_matroid]
three_k4_partition_matroid- the partition matroid on Fin 3 × Fin 6, defined by pulling back (comap) the free matroid on the universal set of Fin 9 along three_k4_partition_class
- The single tactic `simp` silently combines several standard library lemmas: it unfolds the definition of `three_k4_partition_matroid`, applies `Matroid.comap_indep_iff` (independence in a pullback matroid reduces to injectivity on the set and independence of the image) and `Matroid.freeOn_indep_iff` (subsets of the universe are independent in the free matroid), and simplifies the resulting trivial subset condition.
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 three_k4_partition_matroid_indep (S : Set (Fin 3 × Fin 6)) : three_k4_partition_matroid.Indep S ↔ Set.InjOn three_k4_partition_class S := by simp [three_k4_partition_matroid]