Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12, p. 100 (corrected: negative mistakes only) — the negative mistakes of Cautious are at most 4·m_OPT

Proved
CorrClustBBC.Cautious.lemma_12

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

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

Let GGG be a complete ±\pm±-labelled graph on a finite vertex set VVV. Consider any run of Algorithm Cautious (δ=1/44\delta=1/44δ=1/44) on GGG, with output clustering A\mathcal AA. Then for every clustering DDD of VVV,

mA− ≤ 4 mD,m^-_{\mathcal A}\ \le\ 4\,m_D ,mA−​ ≤ 4mD​,

where mA−m^-_{\mathcal A}mA−​ is the number of negative mistakes of A\mathcal AA (pairs labelled −-− placed in a common cluster). Equivalently, mA−≤4 mOPTm^-_{\mathcal A}\le 4\,m_{\mathrm{OPT}}mA−​≤4mOPT​.

Every negative mistake of Cautious is internal, since the vertices of ZZZ are singletons. With Lemma 11 (positive mistakes) and Lemma 6, this bound gives Theorem 13.

Differences from the source:

  • correction: the internal mistakes of Cautious are ≤ 4·m_OPT → the negative mistakes of Cautious are ≤ 4·m_OPT; reason: the printed statement is false. Take n = 18, K = {0,…,14} a + clique, u = 15 adjacent (+) to all of K and to y₁ = 16, y₂ = 17, with y₁y₂ also +, all other pairs −. Picking 0 first, u is the only 3δ-bad vertex of N⁺(0) = K ∪ {u}, so A′₁ = K; u is not 7δ-good w.r.t. K, so A₁ = K; then A₂ = {u, y₁, y₂} and Z = ∅. The run makes 15 internal mistakes (u–K), while {K ∪ {u}, {y₁, y₂}} makes 2, and 15 > 4·2. The printed proof applies Corollary 5 to clusters that are clean only in their own remaining graphs. The printed constant 4 is kept.
  • encoding: m_OPT → m_D for every clustering D; reason: m_OPT is the minimum over all clusterings, so the two statements are equivalent.
  • 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 output of Cautious → the output clustering of any run of the run relation, over all pivot choices and removal orders; reason: the algorithm's choices are arbitrary, so the lemma holds for every choice.
Preamble
import Mathlib
import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem lemma_12 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (L : List (Finset V × Finset V × Finset V)) (Z : Finset V) (hrun : Run G Finset.univ L Z)
    (D : Setoid V) :
    negMistakes G (sameCluster L) ≤ 4 * mistakes G D.r := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 100, Lemma 12
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