§3.3, pp. 16–17 — h₁(G) ≤ ½√g₁(G)
ProvedBicliqueSDP.Chain.h1_le_sqrt_g1bicliquesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
For every bipartite graph , the two semidefinite bounds (8) and (9) satisfy
This is the third inequality of Proposition 1.2, and the technically involved one: the paper compares it with the classical proof of (Remark 3.8). The inequality can be strict, for instance for minus a perfect matching with .
Preamble
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
Formal statement
namespace BicliqueSDP.Chain
/-- §3.3, pp. 16–17: `h₁(G) ≤ ½√g₁(G)`. -/
theorem h1_le_sqrt_g1 {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1] [DecidableEq V2]
(E : V1 → V2 → Prop) :
h1 E ≤ (1 / 2) * Real.sqrt (g1 E) := by sorry
end BicliqueSDP.Chain
Source
Laurent, Polak, Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886v2, §3.3, pp. 16–17, "Proof of h₁(G) ≤ ½√g₁(G)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.