AFTD Auto-Formalizing Theoretical Domains

matroid_sbo_common_list_chromatic_eq_of_le_two

theoremverifiedformalization

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

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.

  1. 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`).

    line 6

    uses le_antisymm, matroid_common_chromatic_le_list_chromatic

      refine le_antisymm ?_ (matroid_common_chromatic_le_list_chromatic M₁ M₂ h₁ h₂ hE)
  2. 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.

    lines 7–9

    uses matroid_common_colorable_of_list_colorable, matroid_common_list_colorable_of_ncard_le, le_rfl

      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)⟩
  3. 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`).

    lines 10–11

    uses Nat.sInf_mem

      have hmem : matroid_common_colorable M₁ M₂ (matroid_common_chromatic_number M₁ M₂) :=
        Nat.sInf_mem hne
  4. The 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`.

    lines 12–18

    uses Nat.not_lt_zero, matroid_common_list_colorable_one_of_colorable_one, matroid_sbo_common_list_colorable_two_of_common_colorable_two

      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
  5. χ_ℓ(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`.

    line 19

    uses Nat.sInf_le

      exact 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

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

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
See it in the graphDiscuss this resultChallenge it