Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7, p. 97 (corrected: 11δ-clean in the remaining graph) — every C′ⱼ lies inside some Aᵢ, and each Aᵢ is 11δ-clean

Proved
CorrClustBBC.Cautious.theorem_7

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

approximation-algorithmcorrelation-clusteringp2o-batch-pfp2ap2o-correctedp2o-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, producing clusters A1,A2,…A_1,A_2,\dotsA1​,A2​,…, where AiA_iAi​ is formed in the remaining graph on Ri=V∖(A1∪⋯∪Ai−1)R_i=V\setminus(A_1\cup\dots\cup A_{i-1})Ri​=V∖(A1​∪⋯∪Ai−1​). Then:

  1. every cluster Cj′C'_jCj′​ of DDD with at least two vertices satisfies Cj′⊆AiC'_j\subseteq A_iCj′​⊆Ai​ for some iii;
  2. every AiA_iAi​ is 11δ11\delta11δ-clean in the graph induced on RiR_iRi​:
∣NRi+(v)∩Ai∣≥(1−11δ)∣Ai∣and∣NRi+(v)∩(Ri∖Ai)∣≤11δ∣Ai∣(v∈Ai).|N^+_{R_i}(v)\cap A_i|\ge(1-11\delta)|A_i| \quad\text{and}\quad |N^+_{R_i}(v)\cap(R_i\setminus A_i)|\le 11\delta|A_i| \qquad (v\in A_i).∣NRi​+​(v)∩Ai​∣≥(1−11δ)∣Ai​∣and∣NRi​+​(v)∩(Ri​∖Ai​)∣≤11δ∣Ai​∣(v∈Ai​).

The theorem says that Cautious recovers every non-singleton cluster of OPT′\mathrm{OPT}'OPT′ and produces only clean clusters; it is the structural core of the approximation guarantee (Theorem 13).

Differences from the source:

  • correction: each Aᵢ is 11δ-clean (in G) → each Aᵢ is 11δ-clean in the remaining graph G \ (A₁ ∪ … ∪ Aᵢ₋₁) it was formed in; reason: false in G. Take n = 46, K = {0,…,43} a + clique, x = 44 adjacent (+) to {0,…,21} and to y = 45, all other pairs −; the run picking 30 and then x gives A₁ = K and A₂ = {x, y}, and in G x has 22 > 11δ·2 positive neighbours outside A₂. The proof (p. 99) argues in the remaining graph.
  • 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: the clusters A₁, A₂, … output by Cautious → the clusters recorded by any run of the run relation, over all pivot choices and removal orders; reason: the algorithm picks an arbitrary vertex and removes an arbitrary bad vertex, so the theorem holds for every choice.
Preamble
import Mathlib
import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem theorem_7 {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) :
    (∀ v, 2 ≤ (classOf D v).card → ∃ p ∈ L, classOf D v ⊆ p.2.1) ∧
      ∀ p ∈ L, IsClean G p.2.2 (11 * δ44) p.2.1 := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 97, Theorem 7 (proof pp. 98–99)
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