matroid_common_list_colorable
def
Two 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 e ∈ E, there is an L-coloring, i.e. c(e) ∈ L(e) for all e and every color class independent in both matroids. (Colors are natural numbers, which loses nothing since only finitely many colors occur.)
Statement
def matroid_common_list_colorable {α : Type*} (M₁ M₂ : Matroid α) (k : ℕ) : Prop
- Defined in
- arXiv:2610.07318 (A note on the list chromatic number of two matroids), Sec. 1 (list coloring of a pair of matroids); lists of size at least k instead of exactly k, which is equivalent by shrinking lists
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 17
- matroid_sbo_common_list_chromatic_eq_of_le_twoFor two loopless strongly base-orderable matroids on a common finite ground set whose common chromatic number is at most 2, the common…
- matroid_sbo_common_list_colorable_three_of_common_colorable_twoIf two finite strongly base-orderable matroids have a common coloring with two colors, they are 3-list-colorable (immediate from…
- 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_colorable_two_not_of_colorable_twoThere are two loopless matroids M₁, M₂ on a common finite ground set (M₁ graphic: three disjoint copies of K₄; M₂ a unit-capacity…
- matroid_common_list_colorable_of_reductionIf N₁ is a reduction of M₁ (every N₁-independent set is M₁-independent, on the same ground set) and N₂ is a reduction of M₂, then…
- 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_le_iffFor 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…
- 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_sbo_list_colorable_two_of_colorable_twoIf M₁ and M₂ are strongly base-orderable matroids on a common finite ground set and each of them is 2-colorable (its ground set is the…
- 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_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_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_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_list_colorable_one_of_colorable_zeroIf two matroids have a common coloring with 0 colors, then their ground set is empty, so they are 1-list-colorable.
- matroid_common_list_colorable_two_of_colorable_oneIf two matroids have a common coloring with 1 color, then they are 2-list-colorable (immediate from 1-list-colorability and monotonicity).
- matroid_common_list_colorable_iff_lists_card_eqA pair of matroids is k-list-colourable if and only if it has an L-colouring for every list assignment whose lists have cardinality…
Lean source view module on GitHub
/-- `(M₁, M₂)` is `k`-list-colorable: for every assignment of finite lists of colors (natural numbers) with at least `k` colors to every element of the ground set, there is a choice of a color from each element's list such that every color class is independent in both matroids. -/ def matroid_common_list_colorable {α : Type*} (M₁ M₂ : Matroid α) (k : ℕ) : Prop := ∀ L : α → Finset ℕ, (∀ e ∈ M₁.E, k ≤ (L e).card) → ∃ c : α → ℕ, (∀ e ∈ M₁.E, c e ∈ L e) ∧ ∀ γ : ℕ, M₁.Indep {e | e ∈ M₁.E ∧ c e = γ} ∧ M₂.Indep {e | e ∈ M₁.E ∧ c e = γ}