AFTD Auto-Formalizing Theoretical Domains

is_admissible_list_assignment

def

A 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 cardinality m and the lists assigned to distinct nonadjacent vertices are disjoint.

Statement

def is_admissible_list_assignment {V : Type*}
    (G : SimpleGraph V) (m : ℕ) (L : V → Finset ℕ) : Prop
Defined in
arXiv:2611.07924, Section 1
Verified
06 Nov 2026
Axioms
none listed
Used by 1
  • graph_min_color_setsFor 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…

Read back from the Lean

For a simple graph G on a vertex type V, a natural number m, and a list assignment L : V → Finset ℕ, is_admissible_list_assignment G m L asserts that: 1. For every vertex v : V, the size of L v is m. 2. For all vertices u, v : V, if u and v are adjacent in the complement graph Gᶜ (that is, u ≠ v and u is not adjacent to v in G), then the sets L u and L 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 list assignment L of m-element subsets of ℕ on a simple graph G is admissible if L(u) and L(v) are disjoint whenever u and v are distinct nonadjacent vertices. -/
def is_admissible_list_assignment {V : Type*}
    (G : SimpleGraph V) (m : ℕ) (L : V → Finset ℕ) : Prop :=
  (∀ v : V, (L v).card = m) ∧ (∀ u v : V, Gᶜ.Adj u v → Disjoint (L u) (L v))
See it in the graphDiscuss this resultChallenge it