Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 10, p. 98 — after the removal step, A(v) never holds vertices of two distinct non-singleton clusters of OPT′

Proved
CorrClustBBC.Cautious.corollary_10

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmcorrelation-clusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let δ=1/44\delta=1/44δ=1/44 and let GGG be a complete ±\pm±-labelled graph on a finite vertex set VVV. Let DDD be a clustering of VVV whose clusters with at least two vertices are δ\deltaδ-clean in GGG (for instance OPT′\mathrm{OPT}'OPT′ of Lemma 6). Consider any run of Algorithm Cautious on GGG, with any choice of pivots and any removal order, producing clusters A1,A2,…A_1, A_2,\dotsA1​,A2​,…, and let Ai′A'_iAi′​ be the set left after the removal step 1(b) in the iteration that produced AiA_iAi​. Then for every iii and all u,v∈Ai′u,v\in A'_iu,v∈Ai′​ whose clusters in DDD have at least two vertices,

D(u)=D(v).D(u)=D(v).D(u)=D(v).

Corollary 10 is the key step of Theorem 7's proof: each set produced by the removal step meets at most one non-singleton cluster of OPT′\mathrm{OPT}'OPT′.

Formalization Note The statement covers every iteration that produced a nonempty cluster. An iteration in the final phase, which produces ∅\emptyset∅, has an empty removal result, for which the claim is vacuous.

Differences from the source:

  • generalization: OPT′ → every clustering D whose clusters with at least two vertices are δ-clean in G; reason: the proof uses only this property of OPT′, which OPT′ has by Lemma 6.
  • reading: "repeat until no vertices are left or until all the produced sets A(v) are empty" → the run may stop exactly when every remaining vertex, tried as the pivot, has some execution of steps 1(a)–(c) producing ∅; reason: the phrase is ambiguous; this is the reading under which "all the produced sets are empty" refers to every remaining vertex.
  • reading: N⁺(v), δ-goodness and the "y ∈ V" of step 1(c) in every iteration after the first → taken in the graph induced on the vertices not yet clustered (the current set R of the run); reason: step 2 deletes A(v) "from the set of vertices" before repeating, and the proof of Theorem 7 (p. 99) argues in "the remaining graph G \ (⋃_{ℓ<i} A_ℓ)".
  • encoding: "after every application of the removal step 1b" → for the removal result A′ᵢ recorded with every produced cluster of a run of the run relation, over all pivot choices and removal orders; reason: the algorithm is nondeterministic; iterations producing ∅ have A′ = ∅, where the claim is vacuous.
Preamble
import Mathlib
import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem corollary_10 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (D : Setoid V) (hD : NonsingletonClean G δ44 D)
    (L : List (Finset V × Finset V × Finset V)) (Z : Finset V) (hrun : Run G Finset.univ L Z) :
    ∀ p ∈ L, ∀ u ∈ p.1, ∀ v ∈ p.1, 2 ≤ (classOf D u).card → 2 ≤ (classOf D v).card →
      D.r u v := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 98, Corollary 10 (Algorithm Cautious p. 97)
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me