Relations (40)–(41), p. 16 — at an optimal X of (33), Σ_{j∈V₂} X_ij = 2h₁(G)X_ii (i ∈ V₁) and symmetrically
ProvedBicliqueSDP.Chain.relations_40_41bicliquescomplementary-slacknessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let be a bipartite graph and let be an optimal solution of the program (33) defining : , , for , and . Write . Then
In the paper's Gram notation , , , these read for (40) and for (41). They are the first step of the proof of .
Formalization Note The relations are stated for the matrix rather than for a Gram factorisation: and . Optimality of is the paper's hypothesis ("Let X be an optimal solution for the formulation (33)").
Preamble
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
Formal statement
namespace BicliqueSDP.Chain
/-- Relations (40)–(41) (p. 16), in matrix form: an optimal solution `X` of (33) satisfies
`∑_{j ∈ V₂} X_ij = 2 h₁(G) X_ii` for `i ∈ V₁` and `∑_{i ∈ V₁} X_ji = 2 h₁(G) X_jj` for `j ∈ V₂`. -/
theorem relations_40_41 {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1] [DecidableEq V2]
(E : V1 → V2 → Prop) (X : Matrix (V1 ⊕ V2) (V1 ⊕ V2) ℝ) (hX : H1Feasible E X)
(hopt : frob Cmat X = h1 E) :
(∀ i : V1, ∑ j : V2, X (Sum.inl i) (Sum.inr j) = 2 * h1 E * X (Sum.inl i) (Sum.inl i)) ∧
(∀ j : V2, ∑ i : V1, X (Sum.inr j) (Sum.inl i) = 2 * h1 E * X (Sum.inr j) (Sum.inr j)) := by sorry
end BicliqueSDP.Chain
Source
Laurent, Polak, Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886v2, p. 16, relations (40) and (41) in the proof of h₁(G) ≤ ½√g₁(G)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.