Proposition 7.2 — both join optimum bounds and strictness
OpenConstrainedCorrelationRepulsion.Main.Supplement.proposition_7_2approximationcorrelation-clusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any finite simple graph with vertices, edges and maximum clique size . For every positive integer , join to a new universal clique . Its minimum cluster-deletion cost satisfies
The second displayed inequality is strict. The formal statement retains both the weak inequality and its strict version. This upper bound is used in the exact approximation transfer, and its optimum is the existing constrained objective on the cluster-deletion embedding.
Differences from the source:
- encoding: finite unsigned graphs, deletion optimum and displayed subtraction → Mathlib simple graphs on labelled vertices, published constrained OPT through the deletion embedding, and real arithmetic; reason: the labelling changes no instance, the embedding counts exactly deleted original edges, and real subtraction avoids natural-number truncation
Preamble
import Definitions.Def_ConstrainedCorrelationRepulsion_Main_Supplement_Graphs
Formal statement
namespace ConstrainedCorrelationRepulsion.Main.Supplement
/-- Proposition 7.2, printed p.35 / PDF p.36, including the binomial term and strictness. -/
theorem proposition_7_2 {n : ℕ} (G : Graph n) (t : ℕ) (ht : 0 < t)
(hm : 0 < edgeCount G) :
(deletionOPT (joinClique G t) : ℝ) ≤
(t : ℝ) * ((n : ℝ) - (omega G : ℝ)) + (edgeCount G : ℝ) -
(Nat.choose (omega G) 2 : ℝ) ∧
(t : ℝ) * ((n : ℝ) - (omega G : ℝ)) + (edgeCount G : ℝ) -
(Nat.choose (omega G) 2 : ℝ) ≤
(t : ℝ) * ((n : ℝ) - (omega G : ℝ)) + (edgeCount G : ℝ) ∧
(t : ℝ) * ((n : ℝ) - (omega G : ℝ)) + (edgeCount G : ℝ) -
(Nat.choose (omega G) 2 : ℝ) <
(t : ℝ) * ((n : ℝ) - (omega G : ℝ)) + (edgeCount G : ℝ) := by sorry
end ConstrainedCorrelationRepulsion.Main.Supplement
Source
Yixin Cao, Ying Xu, STOC 2027 submission #869 (October 2026), Proposition 7.2, printed p.35 (PDF p.36)