Lemma 8, p. 97 — in a δ-clean cluster every vertex w is 3δ-good w.r.t. N⁺(v) of each member v (δ = 1/44)
ProvedCorrClustBBC.Cautious.lemma_8approximation-algorithmcorrelation-clusteringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let . Let be a complete -labelled graph on a finite vertex set , let be a set of vertices, and let be -clean in the graph induced on . Then for all ,
With and a -clean cluster of , this is the paper's statement: any vertex is -good w.r.t. .
The lemma is the base case of the induction in Theorem 7's proof: when Cautious picks a vertex of a clean cluster, no vertex of that cluster is removed from at the start of the removal step. The proof of Theorem 7 applies it in the remaining graph, hence the set .
Differences from the source:
- generalization: C′ᵢ a δ-clean cluster of OPT′ in G → any set C ⊆ R that is δ-clean in the graph induced on any vertex set R; reason: the proof uses only that C is δ-clean; R = V and C = C′ᵢ is the page's statement.
Preamble
import Mathlib import Definitions.Def_CorrClustBBC_Cautious_Setting
Formal statement
namespace CorrClustBBC.Cautious
theorem lemma_8 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
(R C : Finset V) (hCR : C ⊆ R) (hC : IsClean G R δ44 C) (v w : V) (hv : v ∈ C) (hw : w ∈ C) :
IsGood G R (3 * δ44) (posNbhd G R v) w := by sorry
end CorrClustBBC.Cautious
Source
Bansal, Blum, Chawla, Correlation Clustering, Machine Learning 56 (2004) 89–113, p. 97, Lemma 8 (δ = 1/44 from p. 97)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.