AFTD Auto-Formalizing Theoretical Domains

petersen_coloring_language

def

The P10-coloring decision problem as a language over Bool (Language Bool): the set of words w such that there exist n : ℕ and es : List (ℕ × ℕ) with w = edge_list_bool_encode es ∧ edge_list_connected_cubic n es ∧ edge_list_h_colorable petersen_graph n es.

Statement

def petersen_coloring_language : Language Bool
Defined in
arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs), Sec. 1 and Sec. 4: the H-coloring problem for H = P10 (given a connected cubic graph G, decide whether P10 ≺ G), as the language of encoded YES-instances
Verified
30 Oct 2026
Axioms
none listed
Built on 4
  • 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…
  • petersen_graphThe Petersen graph P10, as the Kneser graph K(5,2): a SimpleGraph on the vertex type {s : Finset (Fin 5) // s.card = 2} of 2-element…

Read back from the Lean

petersen_coloring_language is the formal language (set of lists of booleans) consisting of all words w : List Bool for which there exist a natural number n : ℕ and an edge list es : List (ℕ × ℕ) such that: 1. w is the boolean encoding of es via edge_list_bool_encode; 2. es defines a connected cubic graph on n vertices (satisfying edge_list_connected_cubic n es); and 3. the graph defined by es admits a Petersen coloring (satisfying edge_list_h_colorable petersen_graph n es).

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

/-- Words encoding connected cubic multigraphs that admit a Petersen coloring. -/
def petersen_coloring_language : Language Bool :=
  {w | ∃ (n : ℕ) (es : List (ℕ × ℕ)), w = edge_list_bool_encode es ∧
    edge_list_connected_cubic n es ∧ edge_list_h_colorable petersen_graph n es}
See it in the graphDiscuss this resultChallenge it