§2.1, p. 5, proof of Theorem 1 — optimality of the bisection Ṽ1, Ṽ2 implies |S| ≤ |R|
ProvedLPCommunity.MinBisect.S_le_R_of_optimalcommunity-detectiongraph-partitioningminimum-bisectionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph on with a planted bisection , and let be an optimal solution of the minimum bisection problem, i.e. a bisection whose cost is at most the cost of every bisection of . With , , , and the edge sets (edges – and –) and (edges – and –), we have
The edges cut by are and those cut by the planted bisection are , with (edges – and –); optimality gives . This is the first of the three inequalities that combine into Theorem 1.
Formalization Note is the Finset W and = Wᶜ; optimality is stated as cutCost G W ≤ cutCost G S for every bisection S. The paper's additional normalizations (, ) are not needed for this step and are not assumed.
Preamble
import Mathlib import Definitions.Def_LPCommunity_MinBisect_Setting
Formal statement
namespace LPCommunity.MinBisect
theorem S_le_R_of_optimal {n : ℕ} (G : SimpleGraph (Fin n)) (V1 W : Finset (Fin n))
(hV1 : IsBisection n V1) (hW : IsBisection n W)
(hopt : ∀ S : Finset (Fin n), IsBisection n S → cutCost G W ≤ cutCost G S) :
Scard G V1 W ≤ Rcard G V1 W := by sorry
end LPCommunity.MinBisect
Source
Del Pia, Khajavirad, Kunisky, Linear Programming and Community Detection, arXiv:2006.03213v2, §2.1, p. 5, proof of Theorem 1 (the optimality of the bisection Ṽ1, Ṽ2 implies |S| ≤ |R|)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.