matroid_common_colorable_freeOn_one
A free matroid paired with itself has a common coloring with one color.
Statement
theorem matroid_common_colorable_freeOn_one {α : Type*} (E : Set α) : matroid_common_colorable (Matroid.freeOn E) (Matroid.freeOn E) 1
- Source
- sanity check of matroid_common_colorable
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- matroid_common_colorableTwo matroids M₁, M₂ on a common ground set E have a common coloring with k colors: a map c : E → {0, …, k−1} each of whose color classes…
The proof, explained
To show that the free matroid on E is common 1-colorable with itself, we assign every element the color 0. The color constraint 0 < 1 is satisfied by Nat.zero_lt_one, and each monochromatic subset is automatically a subset of the ground set E, hence independent in the free matroid by Matroid.freeOn_indep_iff.
The constant coloring c(e) = 0 exhibits a valid 1-coloring for the pair of free matroids on E.
We witness the existential definition of common 1-colorability with the constant function c(e) = 0. The color bound holds because every element has color 0, which is strictly less than 1 by Nat.zero_lt_one. For any color γ, the monochromatic subset {e ∈ E | c(e) = γ} is contained in the ground set E by definition (extracted by h.1). By Matroid.freeOn_indep_iff, every subset of E is independent in Matroid.freeOn E, so this set is independent in both copies of the matroid.
uses
Nat.zero_lt_one,Matroid.freeOn_indep_iff⟨fun _ => 0, fun _ _ => Nat.zero_lt_one, fun _ => ⟨(Matroid.freeOn_indep_iff).2 fun _ h => h.1, (Matroid.freeOn_indep_iff).2 fun _ h => h.1⟩⟩
Nat.zero_lt_one- Zero is strictly less than one.
Matroid.freeOn_indep_iff- A subset I is independent in the free matroid on ground set E if and only if I ⊆ E.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem matroid_common_colorable_freeOn_one {α : Type*} (E : Set α) : matroid_common_colorable (Matroid.freeOn E) (Matroid.freeOn E) 1 := ⟨fun _ => 0, fun _ _ => Nat.zero_lt_one, fun _ => ⟨(Matroid.freeOn_indep_iff).2 fun _ h => h.1, (Matroid.freeOn_indep_iff).2 fun _ h => h.1⟩⟩