§2.1, p. 5, proof of Theorem 1 — |S| ≥ 2t(d_in − t + 1)
ProvedLPCommunity.MinBisect.two_t_dIn_le_SLet be a graph on with a planted bisection and let be any bisection of . Put , , , , , and let where is the set of edges with one endnode in and one in and the set of edges with one endnode in and one in . Then
where is the minimum number of neighbours a vertex has on its own side of the planted bisection.
Each of the nodes of has at least neighbours in , of which at most lie in ; symmetrically for , which also has nodes. This is the lower bound on in the proof of Theorem 1. The right-hand side may be negative, in which case the bound is trivial.
Formalization Note The inequality is stated in , so that is not truncated at . is the bisection W; is (V1 ∩ W).card. No optimality of W is assumed.
import Mathlib import Definitions.Def_LPCommunity_MinBisect_Setting
namespace LPCommunity.MinBisect
theorem two_t_dIn_le_S {n : ℕ} (G : SimpleGraph (Fin n)) (V1 W : Finset (Fin n))
(hV1 : IsBisection n V1) (hW : IsBisection n W) :
2 * ((V1 ∩ W).card : ℤ) * ((dIn G V1 : ℤ) - (V1 ∩ W).card + 1) ≤ (Scard G V1 W : ℤ) := by sorry
end LPCommunity.MinBisect
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.