AFTD Auto-Formalizing Theoretical Domains

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]))
See it in the graphDiscuss this resultChallenge it