Lemma 3, p. 94 — the weight of any fractional packing of erroneous triangles is at most the number of mistakes of any clustering
ProvedCorrClustBBC.Cautious.lemma_3Let be a complete graph on a finite vertex set whose edges are labelled or . Let 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 . Then for every clustering of , with mistakes,
In particular the weight of every packing is a lower bound on , 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.
import Mathlib import Definitions.Def_CorrClustBBC_Cautious_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.