colorsUsed
def
The number of distinct colors assigned by a vertex coloring c : Fin n → ℕ is the cardinality of the image of c on Finset.univ.
Statement
def colorsUsed {n : ℕ} (c : Fin n → ℕ) : ℕ- Defined in
- arXiv:2610.41516 Section 1
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Used by 3
- op869_online_coloring_clique_exactFor any natural number k, any coloring algorithm A : SimpleGraph (Fin k) → (Fin k → ℕ) that properly colors k-colorable graphs uses…
- op869_adversary_forces_soundA winning one-fold adversary position, whose recorded earlier colors agree with a proper online algorithm on the current predecessor…
- op869_three_colorable_bound_implies_deterministic_lower_boundIf the three-colorable deterministic online coloring lower bound of arXiv:2610.41516 Theorem 1.1 holds in the stated finite-graph model,…
Read back from the Lean
For a natural number $n$ and a function $c : \mathrm{Fin}(n) \to \mathbb{N}$, colorsUsed c is defined as the cardinality of the image of the universal finset of $\mathrm{Fin}(n)$ under $c$, which is the number of distinct values (colors) attained by $c$.
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
/-- The number of distinct colors assigned by a vertex coloring c on Fin n. -/ def colorsUsed {n : ℕ} (c : Fin n → ℕ) : ℕ := (Finset.univ.image c).card