AFTD Auto-Formalizing Theoretical Domains

matroid_common_list_chromatic_le_iff

theoremverified

For two loopless matroids on a common finite ground set, the common list chromatic number is at most k if and only if the pair is k-list-colorable: χ_ℓ(M₁, M₂) ≤ k ↔ matroid_common_list_colorable M₁ M₂ k. This is the exact dictionary between a numeric bound on χ_ℓ and the list-colorability predicate used throughout the additive-gap argument.

Statement

theorem matroid_common_list_chromatic_le_iff {α : Type*} (M₁ M₂ : Matroid α) [Finite α] (h₁ : M₁.Loopless) (h₂ : M₂.Loopless) (hE : M₁.E = M₂.E) (k : ℕ) :
    (matroid_common_list_chromatic_number M₁ M₂ ≤ k ↔ matroid_common_list_colorable M₁ M₂ k)
Source
step towards matroid_common_list_chromatic_le_add_const
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

The common list chromatic number χ_ℓ(M₁, M₂) is defined as the infimum of the set of integers k for which the pair of matroids is k-list-colorable. For the forward direction, assigning distinct colors to all elements of the finite ground set E shows that the pair is |E|-list-colorable, ensuring the set is nonempty and its infimum is attained; monotonicity of list-colorability then implies k-list-colorability. Conversely, if the pair is k-list-colorable, k belongs to the set, so the infimum is at most k by definition.

  1. To prove the forward implication, suppose χ_ℓ(M₁, M₂) ≤ k; it suffices to show that the pair is k-list-colorable.

    The equivalence is split into forward and reverse directions. For the forward direction, we assume the list chromatic number bound χ_ℓ(M₁, M₂) ≤ k.

    lines 4–5

      constructor
      · intro h
  2. The set of list-colorable integers {m ∈ ℕ | (M₁, M₂) is m-list-colorable} is nonempty.

    For loopless matroids on a shared finite ground set, any list size at least |M₁.E| guarantees common list-colorability (`matroid_common_list_colorable_of_ncard_le`), since each element can simply receive a unique color. In particular, choosing m = |M₁.E| (with |M₁.E| ≤ |M₁.E| by `le_rfl`) witnesses that the set is nonempty.

    lines 6–7

    uses matroid_common_list_colorable_of_ncard_le, le_rfl

        have hne : ({k | matroid_common_list_colorable M₁ M₂ k} : Set ℕ).Nonempty :=
          ⟨M₁.E.ncard, matroid_common_list_colorable_of_ncard_le M₁ M₂ h₁ h₂ hE _ le_rfl⟩
  3. The pair (M₁, M₂) is k-list-colorable, completing the forward direction.

    Because the set of list-colorable integers is nonempty, it contains its infimum (`Nat.sInf_mem`), which is by definition χ_ℓ(M₁, M₂). Since list-colorability is monotone in list size (`matroid_common_list_colorable_mono`), the hypothesis χ_ℓ(M₁, M₂) ≤ k implies that (M₁, M₂) is also k-list-colorable.

    lines 8–9

    uses Nat.sInf_mem, matroid_common_list_colorable_mono

        have hmem := Nat.sInf_mem hne
        exact matroid_common_list_colorable_mono M₁ M₂ h hmem
  4. Conversely, if (M₁, M₂) is k-list-colorable, then χ_ℓ(M₁, M₂) ≤ k.

    Assuming (M₁, M₂) is k-list-colorable, k is an element of the set of colorable list sizes. By the defining property of the infimum in ℕ (`Nat.sInf_le`), the infimum χ_ℓ(M₁, M₂) is at most k.

    lines 10–11

    uses Nat.sInf_le

      · intro h
        exact Nat.sInf_le h
le_rfl
In any preorder, every element is less than or equal to itself: a ≤ a.
matroid_common_list_colorable_of_ncard_le
Two loopless matroids on the same finite ground set are k-list-colorable for any integer k ≥ |E|.
matroid_common_list_colorable_mono
If a pair of matroids is k-list-colorable and k ≤ k', then it is also k'-list-colorable.
Nat.sInf_mem
Every nonempty set of natural numbers contains its infimum.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in the set.

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

/-- χ_ℓ(M₁,M₂) ≤ k iff the pair is k-list-colorable. -/theorem matroid_common_list_chromatic_le_iff {α : Type*} (M₁ M₂ : Matroid α) [Finite α] (h₁ : M₁.Loopless) (h₂ : M₂.Loopless) (hE : M₁.E = M₂.E) (k : ℕ) :    (matroid_common_list_chromatic_number M₁ M₂ ≤ k ↔ matroid_common_list_colorable M₁ M₂ k) := by  constructor  · intro h    have hne : ({k | matroid_common_list_colorable M₁ M₂ k} : Set ℕ).Nonempty :=      ⟨M₁.E.ncard, matroid_common_list_colorable_of_ncard_le M₁ M₂ h₁ h₂ hE _ le_rfl⟩    have hmem := Nat.sInf_mem hne    exact matroid_common_list_colorable_mono M₁ M₂ h hmem  · intro h    exact Nat.sInf_le h
See it in the graphDiscuss this resultChallenge it