Complete signed graphs, partitions and disagreement costs
DefinitionDualSepClusterLP_SettingFinite vertices are labeled 0 through n−1. Upper-triangular signs give the complete graph and equal labels give the partition. The input encodes an accuracy index and the graph. The output records the partition by its equality matrix.
import Mathlib
import Mathlib.Computability.TuringMachine.Computable
namespace DualSepClusterLP
/-- Only entries i < j are used. True denotes a positive unordered edge. -/
abbrev Graph (n : ℕ) := Fin n → Fin n → Bool
/-- Equal labels define the blocks of the partition. -/
abbrev Clustering (n : ℕ) := Fin n → Fin n
def disagreements {n : ℕ} (G : Graph n) (C : Clustering n) : ℕ :=
∑ i : Fin n, ∑ j : Fin n,
if i < j ∧ G i j ≠ decide (C i = C j) then 1 else 0
def matrixBits {n : ℕ} (entry : Fin n → Fin n → Bool) : List Bool :=
(List.finRange n).flatMap fun i => (List.finRange n).map (entry i)
/-- The two self-delimiting unary fields give the accuracy index and size. -/
def graphInput {n : ℕ} (t : ℕ) (G : Graph n) : List Bool :=
List.replicate t true ++ [false] ++ List.replicate n true ++ [false] ++
matrixBits (fun i j => if i < j then G i j else false)
def partitionOutput {n : ℕ} (C : Clustering n) : List Bool :=
matrixBits fun i j => decide (C i = C j)
end DualSepClusterLP
Read-back
What the Lean code literally says, in plain math · Codex (GPT-6)
For each n, the upper triangle of a Boolean matrix stores pair signs. A clustering gives each vertex one of n labels. Its cost counts each positive separated pair and each negative internal pair once. Input consists of two unary fields with terminators for accuracy and vertex count, then the padded row-major graph matrix. Output is the equality matrix of the labels. For n=0 the output is empty.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.