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