petersen_coloring_language
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}