AFTD Auto-Formalizing Theoretical Domains

edge_order_code

def

The binary encoding of a querying order (a list of edges of a graph on vertices 0..n-1): the edges in order, each edge {i, j} written as its smaller endpoint followed by its larger endpoint, each in the self-delimiting code nat_self_delimiting_code.

Statement

def edge_order_code {n : ℕ} {G : SimpleGraph (Fin n)} (π : List G.edgeSet) : List Bool
Source
Output encoding for the polynomial-time statement of OP-851 (arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 8, open question (1)).
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • nat_self_delimiting_codeThe self-delimiting binary code of a natural number m: each bit b of the binary expansion of m (least significant bit first, as in…
Used by 1
  • edge_order_code_top_twoThe order consisting of the single edge {1, 0} of the complete graph on two vertices is encoded as false (endpoint 0), then true, true,…

Lean source view module on GitHub

def edge_order_code {n : ℕ} {G : SimpleGraph (Fin n)} (π : List G.edgeSet) : List Bool :=
  π.flatMap fun e => Sym2.lift ⟨fun a b : Fin n =>
    nat_self_delimiting_code (min a b : Fin n) ++ nat_self_delimiting_code (max a b : Fin n),
    fun a b => by dsimp only; rw [min_comm, max_comm]⟩ e.1
See it in the graphDiscuss this resultChallenge it