Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4, p. 95 — a clustering whose clusters are all δ-clean (δ ≤ 1/4) makes at most 4∑rᵢ mistakes for some fractional packing

Proved
CorrClustBBC.Cautious.lemma_4

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

correlation-clusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1triangle-packing

Let GGG be a complete ±\pm±-labelled graph on a finite vertex set VVV, let δ≤1/4\delta\le 1/4δ≤1/4 be real, and let DDD be a clustering of VVV in which every cluster is δ\deltaδ-clean (in GGG). Then there is a fractional packing www of erroneous triangles such that

mD ≤ 4∑Tw(T).m_D\ \le\ 4\sum_T w(T).mD​ ≤ 4T∑​w(T).

Combined with Lemma 3 this shows that a clustering made of clean clusters is within a factor 444 of optimal (Corollary 5); the construction of the packing is what the analysis of Algorithm Cautious charges its internal mistakes to.

Formalization Note "Every cluster is δ\deltaδ-clean" is stated as: for every vertex vvv, the cluster of vvv is δ\deltaδ-clean with respect to the whole vertex set.

Differences from the source:

  • encoding: a finite list of erroneous triangles with positive weights rᵢ → a weight function w on vertex sets, nonnegative and nonzero only on erroneous triangles; reason: the same packings, absent triangles having weight 0.
  • encoding: a clustering of V → a setoid on V, its clusters being the classes; reason: a clustering is a partition, and partitions are setoids.
Preamble
import Mathlib
import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem lemma_4 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (δ : ℝ) (hδ : δ ≤ 1 / 4) (D : Setoid V)
    (hD : ∀ v, IsClean G Finset.univ δ (classOf D v)) :
    ∃ w : Finset V → ℝ, IsFracPacking G w ∧ (mistakes G D.r : ℝ) ≤ 4 * ∑ T, w T := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 95, Lemma 4
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