Compacting any partition equivalence relation recovers exactly its blocks
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.exact_relation_labelsalgorithmsclusteringcomputational-complexity
The least-index representative of each equivalence class lies in that block. Assign consecutive labels by ranking these representatives to recover the unordered exact-k partition.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_LargeBallSearch import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.exact_relation_labels {n k : ℕ} (O : Partition n)
(ho : Feasible Finset.univ k O) (r : ℕ → ℕ → Bool)
(hr : ∀ x y : Fin n, r x.val y.val = true ↔ ∃ C∈O, x∈C ∧ y∈C) :
let l := fromRelation (List.range n) r
l.length=n ∧ labelsPartition n k l=O := by
sorry
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Lemma 3.8, Section 4 Branch A and Branch B, Appendix A.5, and Proposition C.4. https://arxiv.org/abs/2611.03547