matroid_common_chromatic_le_list_chromatic
For two loopless matroids on a common finite ground set, the common chromatic number is at most the common list chromatic number: χ(M₁, M₂) ≤ χ_ℓ(M₁, M₂). Hence the equality χ_ℓ = χ asked for strongly base-orderable pairs is equivalent to χ_ℓ ≤ χ.
Statement
theorem matroid_common_chromatic_le_list_chromatic {α : Type*} (M₁ M₂ : Matroid α) [M₁.Finite] (h₁ : M₁.Loopless) (h₂ : M₂.Loopless) (hE : M₁.E = M₂.E) : matroid_common_chromatic_number M₁ M₂ ≤ matroid_common_list_chromatic_number M₁ M₂
- Source
- Helper for arXiv:2610.07318, Question 3.2 (the inequality χ ≤ χ_ℓ that the paper uses implicitly). Proof: χ_ℓ is attained (the set is nonempty by matroid_common_list_colorable_of_ncard_le, Nat.sInf_mem), list-colorability with constant lists gives a coloring (matroid_common_colorable_of_list_colorable), then Nat.sInf_le.
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_chromatic_numberThe common chromatic number χ(M₁, M₂): the least k such that (M₁, M₂) has a common coloring with k colors.
- matroid_common_list_chromatic_numberThe common list chromatic number χ_ℓ(M₁, M₂): the least k such that (M₁, M₂) is k-list-colorable.
- matroid_common_list_colorableTwo matroids M₁, M₂ on a common ground set E are k-list-colorable: for every assignment of finite color lists L(e) with |L(e)| ≥ k for all…
- Used by 1
- matroid_sbo_common_list_chromatic_eq_of_le_twoFor two loopless strongly base-orderable matroids on a common finite ground set whose common chromatic number is at most 2, the common…
The proof, explained
The common chromatic and list chromatic numbers are defined as the infima of the natural numbers k for which the matroid pair admits a common k-coloring and a common k-list-coloring, respectively. Since the ground set is finite, a list coloring always exists when k is the ground set size, so the set of list-colorable integers is nonempty and attains its infimum at χ_ℓ. Because every list coloring problem specializes to standard coloring, χ_ℓ is also a valid ordinary color count, and therefore the infimum χ cannot exceed χ_ℓ.
The set of integers k for which (M₁, M₂) is common list colorable is nonempty.
Because M₁ is finite, loopless, and shares its ground set with the loopless matroid M₂, choosing k = |M₁.E| guarantees common list colorability by `matroid_common_list_colorable_of_ncard_le` with |M₁.E| ≤ |M₁.E| supplied by `le_rfl`. This produces a witness showing that the set of admissible list color counts is nonempty.
uses
matroid_common_list_colorable_of_ncard_le,le_rflhave hne : {k | matroid_common_list_colorable M₁ M₂ k}.Nonempty := ⟨_, matroid_common_list_colorable_of_ncard_le M₁ M₂ h₁ h₂ hE _ le_rfl⟩The common chromatic number of (M₁, M₂) is at most its common list chromatic number: χ(M₁, M₂) ≤ χ_ℓ(M₁, M₂).
The common list chromatic number χ_ℓ(M₁, M₂) is defined as the infimum of the nonempty set of list-colorable numbers, so `Nat.sInf_mem` shows that (M₁, M₂) is indeed common list colorable with k = χ_ℓ(M₁, M₂) colors. By `matroid_common_colorable_of_list_colorable`, any common list coloring specializes to an ordinary common coloring, meaning χ_ℓ(M₁, M₂) also belongs to the set of valid ordinary color counts. Finally, since the common chromatic number χ(M₁, M₂) is the infimum of ordinary color counts, `Nat.sInf_le` concludes that χ(M₁, M₂) ≤ χ_ℓ(M₁, M₂).
uses
Nat.sInf_le,matroid_common_colorable_of_list_colorable,Nat.sInf_memexact Nat.sInf_le (matroid_common_colorable_of_list_colorable M₁ M₂ _ (Nat.sInf_mem hne))
le_rfl- Every element in a preorder is less than or equal to itself: a ≤ a.
matroid_common_list_colorable_of_ncard_le- For two loopless matroids on the same finite ground set, they are common list colorable using k colors whenever k is at least the cardinality of the ground set.
matroid_common_colorable_of_list_colorable- If a pair of matroids is common list colorable with k colors, it is also common colorable with k colors (by choosing identical lists of size k for each element).
Nat.sInf_mem- A nonempty set of natural numbers contains its infimum (minimum).
Nat.sInf_le- If m is an element of a set of natural numbers s, then the infimum of s is at most m.
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 matroid_common_chromatic_le_list_chromatic {α : Type*} (M₁ M₂ : Matroid α) [M₁.Finite] (h₁ : M₁.Loopless) (h₂ : M₂.Loopless) (hE : M₁.E = M₂.E) : matroid_common_chromatic_number M₁ M₂ ≤ matroid_common_list_chromatic_number M₁ M₂ := by have hne : {k | matroid_common_list_colorable M₁ M₂ k}.Nonempty := ⟨_, matroid_common_list_colorable_of_ncard_le M₁ M₂ h₁ h₂ hE _ le_rfl⟩ exact Nat.sInf_le (matroid_common_colorable_of_list_colorable M₁ M₂ _ (Nat.sInf_mem hne))