Lemma 3.3, p. 13 — h₁(G) = min{λ : λI + Z − C ⪰ 0, Z ∈ S_G}, the minimum attained
ProvedBicliqueSDP.Chain.lemma_3_3Let be a bipartite graph, , and the set of symmetric matrices indexed by that vanish outside the edges of (including the diagonal). Then the semidefinite program (33) defining and the program (32) have the same value, and the minimum in (32) is attained:
This is the strong duality used in §3.3: the dual formulation gives the lower bound and a dual optimal solution, which yields relations (40)–(41).
Formalization Note In the paper the left-hand side is the Lasserre bound of order one (30). The mission defines directly by (33) = (9), so the statement is the equality of the values of (32) and (33), together with the existence of a matrix with (the paper writes "min"). The minimum is a real infimum, sInf.
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
namespace BicliqueSDP.Chain
/-- Lemma 3.3 (p. 13): the value of the dual program (32) equals `h₁(G)` as defined by (33) = (9),
and the minimum in (32) is attained. -/
theorem lemma_3_3 {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1] [DecidableEq V2]
(E : V1 → V2 → Prop) :
h1Dual E = h1 E ∧ ∃ Z, H1DualFeasible E (h1 E) Z := by sorry
end BicliqueSDP.Chain
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.