AFTD Auto-Formalizing Theoretical Domains

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

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 = γ}
See it in the graphDiscuss this resultChallenge it