matroid_common_list_chromatic_le_iff
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
- matroid_common_list_colorable_list_chromatic_numberThe common list chromatic number is attained: for two loopless matroids on a common finite ground set, the pair is k-list-colorable at k =…
- matroid_common_list_colorable_monoIf a pair of matroids is k-list-colourable then it is k'-list-colourable for every k' ≥ k: lists that are at least as long are only easier…
- 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_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…
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.
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.
constructor · intro h
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.
uses
matroid_common_list_colorable_of_ncard_le,le_rflhave 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⟩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.
uses
Nat.sInf_mem,matroid_common_list_colorable_monohave hmem := Nat.sInf_mem hne exact matroid_common_list_colorable_mono M₁ M₂ h hmem
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.
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.
- In Lean, `sInf` on `Set ℕ` is defined so that `sInf ∅ = 0`. Consequently, `Nat.sInf_mem` requires a proof that the set is nonempty to ensure that the infimum actually belongs to the set, a detail that on paper is often taken for granted.
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.
/-- χ_ℓ(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