Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3, p. 94 — the weight of any fractional packing of erroneous triangles is at most the number of mistakes of any clustering

Proved
CorrClustBBC.Cautious.lemma_3

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

correlation-clusteringlower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1triangle-packing

Let GGG be a complete graph on a finite vertex set VVV whose edges are labelled +++ or −-−. Let www be a fractional packing of erroneous triangles: nonnegative weights on triangles with two positive edges and one negative edge, such that the triangles containing any fixed pair of vertices carry total weight at most 111. Then for every clustering DDD of VVV, with mDm_DmD​ mistakes,

∑Tw(T) ≤ mD.\sum_{T} w(T)\ \le\ m_D .T∑​w(T) ≤ mD​.

In particular the weight of every packing is a lower bound on mOPTm_{\mathrm{OPT}}mOPT​, the number of mistakes of an optimal clustering.

This is the lower bound on OPT against which the mistakes of clean clusterings are charged (Lemma 4, Corollary 5) and through which the negative mistakes of Algorithm Cautious are bounded (Lemma 12).

Formalization Note A packing is a weight function on all vertex subsets that is nonnegative and nonzero only on erroneous triangles; triangles of weight zero are absent from the page's list.

Differences from the source:

  • generalization: ∑ rᵢ ≤ OPT (an optimal clustering) → ∑ w(T) ≤ m_D for every clustering D; reason: the proof only uses that every clustering makes a mistake on each erroneous triangle; D = OPT is the page's statement.
  • 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.
Preamble
import Mathlib
import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem lemma_3 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (w : Finset V → ℝ) (hw : IsFracPacking G w) (D : Setoid V) :
    ∑ T, w T ≤ (mistakes G D.r : ℝ) := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 94, Lemma 3
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