simple_graph_is_multiple_choosable
A simple graph G is (a:b)-choosable if for every assignment L of a-element color lists (from ℕ) to the vertices of G, there exists an (L:b)-coloring: an assignment of a b-element subset φ(v) ⊆ L(v) to each vertex v such that adjacent vertices receive disjoint subsets. (Colors are natural numbers, which loses no generality since the lists are finite.)
Statement
def simple_graph_is_multiple_choosable {V : Type*} (G : SimpleGraph V) (a b : ℕ) : Prop
- Defined in
- arXiv:2611.03151, Section 1; Erdős, Rubin, Taylor (1979)
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 1
- simple_graph_is_choosableA simple graph G is k-choosable if it is (k:1)-choosable, i.e., for every assignment of k-element color lists to the vertices, there…
Read back from the Lean
For a type V, a simple graph G on V, and natural numbers a and b, the proposition asserts that: for every function L : V → Finset ℕ such that for all v : V, (L v).card = a, there exists a function φ : V → Finset ℕ such that:
1. for all v : V, φ v ⊆ L v and (φ v).card = b, and
2. for all vertices u, v : V, if u and v are adjacent in G, then φ u and φ v are disjoint.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A simple graph is (a:b)-choosable if every assignment of a-element color lists admits an (L:b)-coloring. -/ def simple_graph_is_multiple_choosable {V : Type*} (G : SimpleGraph V) (a b : ℕ) : Prop := ∀ L : V → Finset ℕ, (∀ v, (L v).card = a) → ∃ φ : V → Finset ℕ, (∀ v, φ v ⊆ L v ∧ (φ v).card = b) ∧ ∀ {u v}, G.Adj u v → Disjoint (φ u) (φ v)