Lemma 7.4 — direct quadratic-time clique extraction
OpenConstrainedCorrelationRepulsion.Main.Supplement.lemma_7_4approximationcorrelation-clusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is an absolute positive constant such that for every finite simple graph with vertices, every integer and every cluster-deletion set of , the direct universal-row scan returns a clique of with
The input deletion set is arbitrary: it need not be optimal, approximately optimal, or preserve the universal clique. The bound uses real division, including when its right-hand side is negative. The scan's maintained population count equals its output bitmap cardinality. Its complexity constant is quantified before every graph, size and deletion set. This is the constructive extraction used by Theorem 1.3.
Differences from the source:
- encoding: one can produce a clique in quadratic time → the specified costed universal-row scan returns that clique and its population counter agrees with the output cardinality; reason: a row of a surviving universal vertex is exactly its cluster on valid inputs; explicit scan costs express the source word-operation bound
Preamble
import Definitions.Def_ConstrainedCorrelationRepulsion_Main_Supplement_Scan
Formal statement
namespace ConstrainedCorrelationRepulsion.Main.Supplement
/-- Lemma 7.4, printed p.36 / PDF p.37. A universal constant bounds the actual scan,
before quantification over all inputs. The size bound uses real, untruncated division. -/
theorem lemma_7_4 : ∃ C : ℕ, 0 < C ∧
∀ n t : ℕ, 0 < t → ∀ G : Graph n,
∀ D : Finset (Sym2 (Fin (n+t))), IsDeletionSet (joinClique G t) D →
G.IsClique (extractedClique n t D) ∧
(n : ℝ) - (D.card : ℝ) / (t : ℝ) ≤ ((extractedClique n t D).card : ℝ) ∧
(gatherScan n t D).size = (extractedClique n t D).card ∧
(gatherScan n t D).work ≤ C * (n+t)^2 := by sorry
end ConstrainedCorrelationRepulsion.Main.Supplement
Source
Yixin Cao, Ying Xu, STOC 2027 submission #869 (October 2026), Lemma 7.4 and proof, printed p.36 (PDF p.37)