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