AFTD Auto-Formalizing Theoretical Domains

matroid_common_chromatic_le_list_chromatic

theoremverified

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
Used by 1

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

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

    lines 4–5

    uses matroid_common_list_colorable_of_ncard_le, le_rfl

      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⟩
  2. 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₂).

    line 6

    uses Nat.sInf_le, matroid_common_colorable_of_list_colorable, Nat.sInf_mem

      exact 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

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