AFTD Auto-Formalizing Theoretical Domains

h_coloring_cubic_language

def

For a type W (implicit, W : Type) and H : SimpleGraph W, h_coloring_cubic_language H : Language Bool is the set of Bool words w such that there exist n : ℕ and an edge list es : List (ℕ × ℕ) with w = edge_list_bool_encode es, edge_list_connected_cubic n es, and edge_list_h_colorable H n es.

Statement

def h_coloring_cubic_language {W : Type} (H : SimpleGraph W) : Language Bool
Defined in
arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs), Sec. 1-2: the H-coloring problem on cubic graphs (loopless, parallel edges allowed)
Verified
30 Oct 2026
Axioms
none listed
Built on 3
  • edge_list_bool_encodeEncodes an edge list es : List (ℕ × ℕ) as a word over Bool: es.flatMap of the map sending a pair e to List.replicate e.1 true ++ false ::…
  • edge_list_connected_cubicTakes n : ℕ and an edge list es : List (ℕ × ℕ), read as a multigraph on the vertices v < n whose edges are the indices i : Fin es.length,…
  • edge_list_h_colorableWith W : Type implicit, takes, in this order, H : SimpleGraph W, n : ℕ and an edge list es : List (ℕ × ℕ) (edge i : Fin es.length joins…

Read back from the Lean

For a type W and a simple graph H on W, h_coloring_cubic_language H is the formal language (a Set (List Bool)) consisting of all boolean lists w such that there exist a natural number n and a list of pairs of natural numbers es : List (ℕ × ℕ) satisfying three conditions: 1. **Encoding:** w is the boolean encoding of es, obtained by flat-mapping each pair (u, v) in es to u copies of true, followed by false, followed by v copies of true, followed by false. 2. **Connected cubic graph:** es represents a connected cubic graph on vertex set {0, ..., n - 1}: - For every index i : Fin es.length, both endpoints of es[i] are strictly less than n, and es[i] is not a self-loop (es[i].1 ≠ es[i].2). - For every vertex v < n, the number of edge indices i : Fin es.length incident to v (i.e., where es[i].1 = v or es[i].2 = v) is exactly 3. - The simple graph on Fin n formed from the relation ∃ i : Fin es.length, es[i].1 = u.val ∧ es[i].2 = v.val via SimpleGraph.fromRel is connected. 3. **H-colorability:** There exists an edge-coloring function f : Fin es.length → H.edgeSet such that for every vertex v < n, there exists a vertex x : W such that the image under f (viewed as elements of Sym2 W) of the set of indices incident to v ({i : Fin es.length | es[i].1 = v ∨ es[i].2 = v}) is equal to H.incidenceSet x (the set of edges in H incident to x).

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 H-coloring problem on connected cubic (loopless multi)graphs as a language of Bool words: the unary edge-list encodings `edge_list_bool_encode es` of edge lists `es` on vertices `v < n` that are connected and cubic and admit an H-coloring. -/
def h_coloring_cubic_language {W : Type} (H : SimpleGraph W) : Language Bool :=
  {w | ∃ (n : ℕ) (es : List (ℕ × ℕ)), w = edge_list_bool_encode es ∧
    edge_list_connected_cubic n es ∧ edge_list_h_colorable H n es}
See it in the graphDiscuss this resultChallenge it