Lemma 3, p. 11 — adding edges inside the communities preserves LP recovery
ProvedLPCommunity.LPRecovery.lemma_3community-detectionexact-recoverylinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Characterize a graph with planted bisection by the triple of its crossing graph and its two induced subgraphs. Suppose the metric relaxation (LP-P) recovers the planted bisection for . Let , be graphs on , with
Then (LP-P) also recovers the planted bisection for .
Adding edges inside the communities can only help the LP single out the planted bisection; with Lemma 2 this extends Proposition 2 from regular to sandwiched graphs.
Formalization Note The second graph has exactly the same crossing edges as , and every edge of inside or inside is an edge of .
Preamble
import Mathlib import Definitions.Def_LPCommunity_LPRecovery_Setting open Finset open scoped Classical
Formal statement
namespace LPCommunity.LPRecovery
theorem lemma_3 {n : ℕ} (G G' : SimpleGraph (Fin n)) (V1 : Finset (Fin n))
(hV1 : LPCommunity.MinBisect.IsBisection n V1) (hrec : LPRecovers G V1)
(hcross : ∀ i j, ¬ LPCommunity.MinBisect.sameSide V1 i j → (G'.Adj i j ↔ G.Adj i j))
(hsame : ∀ i j, LPCommunity.MinBisect.sameSide V1 i j → G.Adj i j → G'.Adj i j) :
LPRecovers G' V1 := by sorry
end LPCommunity.LPRecovery
Source
Del Pia, Khajavirad, Kunisky, Linear Programming and Community Detection, arXiv:2006.03213v2, p. 11, Lemma 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.