Lemma 2, p. 11 — deleting crossing edges preserves LP recovery
ProvedLPCommunity.LPRecovery.lemma_2Characterize 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 a bipartite graph across the same bipartition with
Then (LP-P) also recovers the planted bisection for .
With Lemma 3, this lets recovery for a regular graph be transferred to any graph sandwiched between regular ones, which is how Theorem 4 is obtained.
Formalization Note The second graph has exactly the same edges as inside and inside , and its crossing edges are crossing edges of . The paper writes and its proof removes edges; the case of equality is trivial, so the inclusion is posed as .
import Mathlib import Definitions.Def_LPCommunity_LPRecovery_Setting open Finset open scoped Classical
namespace LPCommunity.LPRecovery
theorem lemma_2 {n : ℕ} (G G' : SimpleGraph (Fin n)) (V1 : Finset (Fin n))
(hV1 : LPCommunity.MinBisect.IsBisection n V1) (hrec : LPRecovers G V1)
(hsame : ∀ i j, LPCommunity.MinBisect.sameSide V1 i j → (G'.Adj i j ↔ G.Adj i j))
(hcross : ∀ i j, ¬ LPCommunity.MinBisect.sameSide V1 i j → G'.Adj i j → G.Adj i j) :
LPRecovers G' V1 := by sorry
end LPCommunity.LPRecovery
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.