Theorem 1, p. 4 — if d_in − d_out > n/4 − 1, the minimum bisection problem recovers the planted bisection
ProvedLPCommunity.MinBisect.theorem_1Let be a graph on with a planted bisection (). Let be the minimum degree of the nodes of and the maximum degree of the nodes of the bipartite graph of edges between and . If
then the minimum bisection problem recovers the planted bisection: is the unique bisection of of minimum cost.
The condition involves only the worst-case degree inside and across the communities, with no randomness. It is tight: by Theorem 2 of the paper, for every divisible by eight and every admissible pair with there are graphs on which recovery fails. Section 3 of the paper compares it with the condition under which the metric LP relaxation recovers the planted bisection.
Formalization Note The vertex set is Fin n. and are the defined dIn, dOut, and the hypothesis is compared in (real division , no truncated subtraction). "Recovers" means: every bisection S with cutCost G S ≤ cutCost G V1 equals V1 or V1ᶜ. At the statement holds trivially (the only bisection is ).
import Mathlib import Definitions.Def_LPCommunity_MinBisect_Setting
namespace LPCommunity.MinBisect
theorem theorem_1 {n : ℕ} (G : SimpleGraph (Fin n)) (V1 : Finset (Fin n)) (hV1 : IsBisection n V1)
(h : (dIn G V1 : ℝ) - (dOut G V1 : ℝ) > (n : ℝ) / 4 - 1) :
MinBisectRecovers G V1 := by sorry
end LPCommunity.MinBisect
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.