matroid_sbo_common_list_chromatic_eq_of_le_two
For two loopless strongly base-orderable matroids on a common finite ground set whose common chromatic number is at most 2, the common list chromatic number equals the common chromatic number: χ(M₁, M₂) ≤ 2 implies χ_ℓ(M₁, M₂) = χ(M₁, M₂). This settles the open question χ_ℓ = χ for strongly base-orderable pairs in all cases with χ ≤ 2.
Statement
theorem matroid_sbo_common_list_chromatic_eq_of_le_two {α : Type*} (M₁ M₂ : Matroid α) [M₁.Finite] (h₁ : M₁.Loopless) (h₂ : M₂.Loopless) (hE : M₁.E = M₂.E) (hs₁ : matroid_strongly_base_orderable M₁) (hs₂ : matroid_strongly_base_orderable M₂) (h : matroid_common_chromatic_number M₁ M₂ ≤ 2) : matroid_common_list_chromatic_number M₁ M₂ = matroid_common_chromatic_number M₁ M₂
- Formalizes
- arXiv:2610.07318 (A note on the list chromatic number of two matroids), Corollary 2.3 ("in particular": χ = 2 implies χ_ℓ = 2), stated here with the chromatic numbers and including the cases χ = 0 and χ = 1; the paper's step through the 1976 common-chromatic-number theorem is not needed, since a common 2-coloring 2-colors each matroid.
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- matroid_sbo_common_list_colorable_two_of_common_colorable_twoIf two strongly base-orderable matroids on a common finite ground set have a common coloring with two colors, then they are…
- matroid_common_chromatic_le_list_chromaticFor two loopless matroids on a common finite ground set, the common chromatic number is at most the common list chromatic number: χ(M₁,…
- 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_list_colorable_one_of_colorable_oneIf (M₁, M₂) has a common coloring with one color (the whole ground set is independent in both), then it is 1-list-colorable: χ_ℓ = χ when…
- 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_strongly_base_orderableA matroid M is strongly base-orderable if for every two bases B₁, B₂ there is a bijection φ : B₁ → B₂ such that (B₁ \ X) ∪ φ(X) is a base…
- 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_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…
The proof, explained
The inequality χ(M₁, M₂) ≤ χ_ℓ(M₁, M₂) holds in general, so it suffices to show χ_ℓ(M₁, M₂) ≤ χ(M₁, M₂). Because χ(M₁, M₂) ≤ 2, the common chromatic number χ must be 0, 1, or 2. Since the pair is common χ-colorable, a case split on χ shows that common χ-colorability implies common list χ-colorability in all three cases, using the strong base-orderability hypothesis when χ = 2. It follows that χ_ℓ(M₁, M₂) ≤ χ(M₁, M₂), yielding equality.
It suffices to show that χ_ℓ(M₁, M₂) ≤ χ(M₁, M₂).
By antisymmetry of ≤ (`le_antisymm`), establishing equality reduces to two inequalities. The opposite inequality χ(M₁, M₂) ≤ χ_ℓ(M₁, M₂) is known unconditionally for loopless finite matroids on a common ground set (`matroid_common_chromatic_le_list_chromatic`).
uses
le_antisymm,matroid_common_chromatic_le_list_chromaticrefine le_antisymm ?_ (matroid_common_chromatic_le_list_chromatic M₁ M₂ h₁ h₂ hE)The set of integers k for which M₁ and M₂ are common k-colorable is nonempty.
Setting k = |M₁.E|, the pair is common list k-colorable by `matroid_common_list_colorable_of_ncard_le` using |M₁.E| ≤ |M₁.E| (`le_rfl`). Because any list-colorable pair is also colorable (`matroid_common_colorable_of_list_colorable`), |M₁.E| provides a witness that the set is nonempty.
uses
matroid_common_colorable_of_list_colorable,matroid_common_list_colorable_of_ncard_le,le_rflhave hne : {k | matroid_common_colorable M₁ M₂ k}.Nonempty := ⟨_, matroid_common_colorable_of_list_colorable M₁ M₂ _ (matroid_common_list_colorable_of_ncard_le M₁ M₂ h₁ h₂ hE _ le_rfl)⟩The pair (M₁, M₂) is common χ(M₁, M₂)-colorable.
By definition, the common chromatic number χ(M₁, M₂) is the infimum of the set of integers for which a common coloring exists. Because this set of natural numbers is nonempty, its infimum belongs to the set (`Nat.sInf_mem`).
uses
Nat.sInf_memhave hmem : matroid_common_colorable M₁ M₂ (matroid_common_chromatic_number M₁ M₂) := Nat.sInf_mem hneThe pair (M₁, M₂) is common list χ(M₁, M₂)-colorable.
Letting χ = χ(M₁, M₂), the hypothesis gives χ ≤ 2, so we analyze the three possible values χ ∈ {0, 1, 2}: - If χ = 0, the coloring hypothesis asserts that every element e ∈ M₁.E has color c(e) < 0, which is impossible in ℕ (`Nat.not_lt_zero`), so the list-coloring condition holds vacuously. - If χ = 1, common 1-colorability implies common list 1-colorability by `matroid_common_list_colorable_one_of_colorable_one`. - If χ = 2, common 2-colorability implies common list 2-colorability for strongly base-orderable matroids by `matroid_sbo_common_list_colorable_two_of_common_colorable_two`.
uses
Nat.not_lt_zero,matroid_common_list_colorable_one_of_colorable_one,matroid_sbo_common_list_colorable_two_of_common_colorable_twohave key : matroid_common_list_colorable M₁ M₂ (matroid_common_chromatic_number M₁ M₂) := by generalize matroid_common_chromatic_number M₁ M₂ = χ at h hmem ⊢ interval_cases χ · obtain ⟨c, hc, hind⟩ := hmem exact fun L _ => ⟨c, fun e he => absurd (hc e he) (Nat.not_lt_zero _), hind⟩ · exact matroid_common_list_colorable_one_of_colorable_one M₁ M₂ hmem · exact matroid_sbo_common_list_colorable_two_of_common_colorable_two M₁ M₂ hE hs₁ hs₂ hmem
χ_ℓ(M₁, M₂) ≤ χ(M₁, M₂), completing the proof.
The common list chromatic number χ_ℓ(M₁, M₂) is defined as the infimum of the set of integers k for which the pair is common list k-colorable. Since χ(M₁, M₂) belongs to this set, the infimum is at most χ(M₁, M₂) by `Nat.sInf_le`.
uses
Nat.sInf_leexact Nat.sInf_le key
le_antisymm- if a ≤ b and b ≤ a in a partial order, then a = b
matroid_common_chromatic_le_list_chromatic- for any loopless finite matroids M₁ and M₂ on a common ground set, χ(M₁, M₂) ≤ χ_ℓ(M₁, M₂)
matroid_common_colorable_of_list_colorable- if a pair of matroids is common list k-colorable, then it is common k-colorable
matroid_common_list_colorable_of_ncard_le- for loopless finite matroids M₁ and M₂ on a common ground set, if |M₁.E| ≤ k, then the pair is common list k-colorable
le_rfl- the inequality relation ≤ is reflexive: a ≤ a
Nat.sInf_mem- every nonempty set of natural numbers contains its infimum (minimum)
Nat.not_lt_zero- no natural number is strictly less than 0
matroid_common_list_colorable_one_of_colorable_one- if a pair of matroids is common 1-colorable, then it is common list 1-colorable
matroid_sbo_common_list_colorable_two_of_common_colorable_two- for two finite strongly base-orderable matroids on a common ground set, common 2-colorability implies common list 2-colorability
Nat.sInf_le- if a natural number m belongs to a set s ⊆ ℕ, then sInf s ≤ m
- The nonemptiness step (lines 7–9) is a formalization requirement: Lean's infimum on sets of natural numbers returns 0 for the empty set, so nonemptiness must be proved before invoking `Nat.sInf_mem`.
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_sbo_common_list_chromatic_eq_of_le_two {α : Type*} (M₁ M₂ : Matroid α) [M₁.Finite] (h₁ : M₁.Loopless) (h₂ : M₂.Loopless) (hE : M₁.E = M₂.E) (hs₁ : matroid_strongly_base_orderable M₁) (hs₂ : matroid_strongly_base_orderable M₂) (h : matroid_common_chromatic_number M₁ M₂ ≤ 2) : matroid_common_list_chromatic_number M₁ M₂ = matroid_common_chromatic_number M₁ M₂ := by refine le_antisymm ?_ (matroid_common_chromatic_le_list_chromatic M₁ M₂ h₁ h₂ hE) have hne : {k | matroid_common_colorable M₁ M₂ k}.Nonempty := ⟨_, matroid_common_colorable_of_list_colorable M₁ M₂ _ (matroid_common_list_colorable_of_ncard_le M₁ M₂ h₁ h₂ hE _ le_rfl)⟩ have hmem : matroid_common_colorable M₁ M₂ (matroid_common_chromatic_number M₁ M₂) := Nat.sInf_mem hne have key : matroid_common_list_colorable M₁ M₂ (matroid_common_chromatic_number M₁ M₂) := by generalize matroid_common_chromatic_number M₁ M₂ = χ at h hmem ⊢ interval_cases χ · obtain ⟨c, hc, hind⟩ := hmem exact fun L _ => ⟨c, fun e he => absurd (hc e he) (Nat.not_lt_zero _), hind⟩ · exact matroid_common_list_colorable_one_of_colorable_one M₁ M₂ hmem · exact matroid_sbo_common_list_colorable_two_of_common_colorable_two M₁ M₂ hE hs₁ hs₂ hmem exact Nat.sInf_le key