edge_list_bool_encode
def
Encodes 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 :: (List.replicate e.2 true ++ [false]), i.e. each number k is written in unary as k copies of true then false, and the codes of the pairs are concatenated in order.
Statement
def edge_list_bool_encode (es : List (ℕ × ℕ)) : List Bool- Source
- Input encoding for the decision problem of arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs), Sec. 1 (H-coloring of connected cubic graphs): a unary edge-list encoding, polynomially equivalent to the usual binary ones
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Used by 3
- h_coloring_cubic_languageFor 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…
- petersen_coloring_languageThe P10-coloring decision problem as a language over Bool (Language Bool): the set of words w such that there exist n : ℕ and es : List (ℕ…
- edge_list_bool_encode_injectiveThe unary encoding edge_list_bool_encode of edge lists as Bool words is injective: different edge lists get different words.
Lean source view module on GitHub
/-- Unary encoding of an edge list as a Bool word. -/ def edge_list_bool_encode (es : List (ℕ × ℕ)) : List Bool := es.flatMap (fun e => List.replicate e.1 true ++ false :: (List.replicate e.2 true ++ [false]))