Lemma 9, p. 98 — vertices of two distinct δ-clean clusters are never both 3δ-good w.r.t. one set X (δ = 1/44)
ProvedCorrClustBBC.Cautious.lemma_9approximation-algorithmcorrelation-clusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let . Let be a complete -labelled graph on a finite vertex set , let , and let be disjoint sets, both -clean in the graph induced on . For every , every and every ,
With and , () two clusters of , this is the paper's statement.
The lemma yields Corollary 10: the removal step never leaves vertices of two different clean clusters together.
Differences from the source:
- generalization: C′ᵢ, C′ⱼ (i ≠ j) clusters of OPT′ in G and an arbitrary set X → any two disjoint sets C, C′ ⊆ R that are δ-clean in the graph induced on any vertex set R, and any X ⊆ R; reason: the proof uses only cleanliness and disjointness; R = V (so every X qualifies) and C = C′ᵢ, C′ = C′ⱼ is the page's statement.
Preamble
import Mathlib import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem lemma_9 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(R X C C' : Finset V) (hX : X ⊆ R) (hCR : C ⊆ R) (hC'R : C' ⊆ R) (hdisj : Disjoint C C')
(hC : IsClean G R δ44 C) (hC' : IsClean G R δ44 C') (v₁ v₂ : V) (hv₁ : v₁ ∈ C) (hv₂ : v₂ ∈ C') :
¬ (IsGood G R (3 * δ44) X v₁ ∧ IsGood G R (3 * δ44) X v₂) := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 98, Lemma 9 (δ = 1/44 from p. 97)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.