§2.1, p. 5, proof of Theorem 1 — by definition of d_out, |R| ≤ 2t d_out
ProvedLPCommunity.MinBisect.R_le_two_t_dOutcommunity-detectiongraph-partitioningminimum-bisectionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let 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 maximum number of neighbours a vertex has on the other side of the planted bisection.
Every edge of crosses the planted bisection and has an endnode in or in , and for any two bisections. This is the upper bound on in the proof of Theorem 1.
Formalization Note is the bisection W; is (V1 ∩ W).card. No optimality of W is assumed.
Preamble
import Mathlib import Definitions.Def_LPCommunity_MinBisect_Setting
Formal statement
namespace LPCommunity.MinBisect
theorem R_le_two_t_dOut {n : ℕ} (G : SimpleGraph (Fin n)) (V1 W : Finset (Fin n))
(hV1 : IsBisection n V1) (hW : IsBisection n W) :
Rcard G V1 W ≤ 2 * (V1 ∩ W).card * dOut G V1 := 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 (by definition of d_out, |R1| ≤ t d_out and |R2| ≤ t d_out, thus |R| ≤ 2t d_out)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.