AFTD Auto-Formalizing Theoretical Domains

graph_min_color_sets

def

For a finite vertex type V, a simple graph G on V, and an integer m, graph_min_color_sets G m is the infimum sInf of the cardinalities (graph_color_sets G L).card over all admissible list assignments L : V → Finset ℕ of list size m on G.

Statement

noncomputable def graph_min_color_sets {V : Type*} [Fintype V]
    (G : SimpleGraph V) (m : ℕ) : ℕ
Defined in
arXiv:2611.07924, Section 1 and Section 2 (Lemma 2.1)
Verified
06 Nov 2026
Axioms
none listed
Built on 2
  • is_admissible_list_assignmentA list assignment L assigning to each vertex of a graph G a finite set of natural numbers is admissible for list size m if every list has…
  • graph_color_setsGiven a finite vertex type V, a simple graph G on V, and a list assignment L : V → Finset ℕ assigning each vertex a finite set of colors…

Read back from the Lean

Given a finite type $V$, a simple graph $G$ on $V$, and a natural number $m$, graph_min_color_sets G m is the minimum (infimum in $\mathbb{N}$) over all admissible list assignments $L : V \to \mathrm{Finset}\,\mathbb{N}$ of the number of distinct color sets (images $\varphi(V)$) achievable by proper $L$-colorings of $G$. An admissible list assignment $L$ requires each vertex to have a list of size $m$, and any two distinct vertices that are not adjacent in $G$ to have disjoint lists.

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 minimum number f'(G, m) of distinct color sets used by proper colorings of G from admissible m-element lists. -/
noncomputable def graph_min_color_sets {V : Type*} [Fintype V]
    (G : SimpleGraph V) (m : ℕ) : ℕ :=
  sInf { N : ℕ | ∃ L : V → Finset ℕ, is_admissible_list_assignment G m L ∧
    (graph_color_sets G L).card = N }
See it in the graphDiscuss this resultChallenge it