matroid_common_colorable_chromatic_number
The common chromatic number is attained: for two loopless matroids on a common finite ground set, the pair has a common coloring with exactly χ(M₁, M₂) colors; i.e. χ(M₁, M₂) is the least element of {k | matroid_common_colorable M₁ M₂ k}.
Statement
theorem matroid_common_colorable_chromatic_number {α : Type*} (M₁ M₂ : Matroid α) [Finite α] (h₁ : M₁.Loopless) (h₂ : M₂.Loopless) (hE : M₁.E = M₂.E) : matroid_common_colorable M₁ M₂ (matroid_common_chromatic_number M₁ M₂)
- Source
- step towards matroid_common_list_chromatic_le_add_const
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- matroid_common_list_colorable_of_ncard_leTwo loopless matroids on a common finite ground set E are k-list-colorable whenever k ≥ |E|: from lists of at least |E| colors one can…
- matroid_common_colorable_of_list_colorableIf (M₁, M₂) is k-list-colorable then it has a common coloring with k colors (take every list to be {0, …, k−1}); hence χ(M₁, M₂) ≤ χ_ℓ(M₁,…
- 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…
- matroid_common_chromatic_numberThe common chromatic number χ(M₁, M₂): the least k such that (M₁, M₂) has a common coloring with k colors.
The proof, explained
By definition, the common chromatic number χ(M₁, M₂) is the infimum of the set of natural numbers k for which M₁ and M₂ admit a common k-coloring. To show that this infimum is realized by an actual coloring, it suffices to prove that this set is nonempty, because every nonempty set of natural numbers contains its infimum. The proof exhibits the ground set cardinality |M₁.E| as an explicit witness, using the fact that any two loopless matroids on the same finite ground set admit a common list coloring (and thus a common coloring) whenever the list size is at least |M₁.E|.
Unfolding the definition shows it suffices to prove that the infimum of the set of colorable sizes k belongs to that set.
By definition, the common chromatic number χ(M₁, M₂) is sInf {k | matroid_common_colorable M₁ M₂ k}. The goal is therefore to show that this infimum is itself in the set of numbers of colors for which a common coloring exists.
unfold matroid_common_chromatic_numberThe set of integers k for which a common k-coloring exists is nonempty.
We provide the cardinality |M₁.E| of the ground set as an explicit witness. Since |M₁.E| ≤ |M₁.E| by reflexivity (le_refl), matroid_common_list_colorable_of_ncard_le implies that M₁ and M₂ admit a common list coloring with lists of size |M₁.E|. Any common list coloring gives rise to a common coloring via matroid_common_colorable_of_list_colorable, so |M₁.E| belongs to the set.
uses
matroid_common_colorable_of_list_colorable,matroid_common_list_colorable_of_ncard_le,le_reflhave hne : ({k | matroid_common_colorable M₁ M₂ k}).Nonempty := ⟨M₁.E.ncard, matroid_common_colorable_of_list_colorable M₁ M₂ _ (matroid_common_list_colorable_of_ncard_le M₁ M₂ h₁ h₂ hE _ (le_refl _))⟩The infimum χ(M₁, M₂) belongs to the set, so a common coloring with χ(M₁, M₂) colors exists.
Because the set of color numbers is a nonempty subset of ℕ, the well-ordering of the natural numbers implies that the set contains its own infimum (Nat.sInf_mem).
uses
Nat.sInf_memexact Nat.sInf_mem hne
matroid_common_colorable_of_list_colorable- If two matroids admit a common list coloring with list size k, then they admit a common k-coloring.
matroid_common_list_colorable_of_ncard_le- Two loopless matroids on the same finite ground set admit a common list coloring of size k whenever k is at least the cardinality of the ground set.
le_refl- The less-than-or-equal relation is reflexive: a ≤ a for any a.
Nat.sInf_mem- Every nonempty set of natural numbers contains its infimum (least element).
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.
/-- The common chromatic number χ(M₁,M₂) is realized by an actual common coloring. -/theorem matroid_common_colorable_chromatic_number {α : Type*} (M₁ M₂ : Matroid α) [Finite α] (h₁ : M₁.Loopless) (h₂ : M₂.Loopless) (hE : M₁.E = M₂.E) : matroid_common_colorable M₁ M₂ (matroid_common_chromatic_number M₁ M₂) := by unfold matroid_common_chromatic_number have hne : ({k | matroid_common_colorable M₁ M₂ k}).Nonempty := ⟨M₁.E.ncard, matroid_common_colorable_of_list_colorable M₁ M₂ _ (matroid_common_list_colorable_of_ncard_le M₁ M₂ h₁ h₂ hE _ (le_refl _))⟩ exact Nat.sInf_mem hne