Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 13, p. 100 — every run of Algorithm Cautious makes at most (9/δ² + 5)·m_OPT mistakes, δ = 1/44

Proved
CorrClustBBC.Cautious.theorem_13

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

approximation-algorithmcorrelation-clusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1signed-graph

Let GGG be a complete graph on a finite vertex set VVV whose edges are labelled +++ or −-−, and let δ=1/44\delta=1/44δ=1/44. Algorithm Cautious has at least one run on GGG, and every run — for every choice of pivot vertices and every order of removals in step 1(b) — outputs a clustering A\mathcal AA such that, for every clustering DDD of VVV,

mA ≤ (9δ2+5) mD.m_{\mathcal A}\ \le\ \Big(\frac{9}{\delta^2}+5\Big)\,m_D .mA​ ≤ (δ29​+5)mD​.

Equivalently, mCautious≤(9/δ2+5) mOPTm_{\mathrm{Cautious}}\le (9/\delta^2+5)\,m_{\mathrm{OPT}}mCautious​≤(9/δ2+5)mOPT​; numerically the factor is 17 42917\,42917429.

This is the first constant-factor approximation for minimizing disagreements in correlation clustering on complete graphs.

Formalization Note "mOPTm_{\mathrm{OPT}}mOPT​" is the least number of mistakes of any clustering, so a bound against every clustering DDD is the same statement. The first part of the statement, that a run exists, rules out a vacuous reading in which the bound holds because the algorithm never produces an output.

Differences from the source:

  • 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: m_Cautious, the cost of the output of Cautious → Cautious has a run on G, and the output of every run (every pivot choice, every removal order) satisfies the bound; reason: the algorithm picks an arbitrary vertex and removes an arbitrary bad vertex, so its cost is that of every run, and that it produces an output at all is implicit in calling it an algorithm.
  • 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_ℓ)".
Preamble
import Mathlib
import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem theorem_13 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :
    (∃ (L : List (Finset V × Finset V × Finset V)) (Z : Finset V), Run G Finset.univ L Z) ∧
      ∀ (L : List (Finset V × Finset V × Finset V)) (Z : Finset V), Run G Finset.univ L Z →
        ∀ D : Setoid V,
          (mistakes G (sameCluster L) : ℝ) ≤ (9 / δ44 ^ 2 + 5) * (mistakes G D.r : ℝ) := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 100, Theorem 13 (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