matroid_common_colorable
def
Two matroids M₁, M₂ on a common ground set E have a common coloring with k colors: a map c : E → {0, …, k−1} each of whose color classes is independent in both M₁ and M₂.
Statement
def matroid_common_colorable {α : Type*} (M₁ M₂ : Matroid α) (k : ℕ) : Prop
- Defined in
- arXiv:2610.07318 (A note on the list chromatic number of two matroids), Sec. 1 (coloring of a pair of matroids)
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 13
- matroid_common_colorable_freeOn_oneA free matroid paired with itself has a common coloring with one color.
- 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_common_colorable_chromatic_numberThe common chromatic number is attained: for two loopless matroids on a common finite ground set, the pair has a common coloring with…
- 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_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_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_chromatic_numberThe common chromatic number χ(M₁, M₂): the least k such that (M₁, M₂) has a common coloring with k colors.
- 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.
- not_matroid_common_colorable_loopyOn_zeroA nonempty ground set has no common coloring with zero colors.
- 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).
Lean source view module on GitHub
/-- `(M₁, M₂)` has a common coloring with `k` colors: a map `c` giving each element of the ground set of `M₁` a color in `{0, …, k - 1}` such that every color class is independent in both matroids. -/ def matroid_common_colorable {α : Type*} (M₁ M₂ : Matroid α) (k : ℕ) : Prop := ∃ c : α → ℕ, (∀ e ∈ M₁.E, c e < k) ∧ ∀ γ : ℕ, M₁.Indep {e | e ∈ M₁.E ∧ c e = γ} ∧ M₂.Indep {e | e ∈ M₁.E ∧ c e = γ}