§3.3, p. 16 — ½√g(G) ≤ h₁(G)
ProvedBicliqueSDP.Chain.sqrt_g_le_h1bicliquesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
For every bipartite graph ,
where is the maximum of over bipartite biindependent pairs and is the semidefinite bound (9).
This is the second inequality of Proposition 1.2: the SDP bound dominates not only but also .
Preamble
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
Formal statement
namespace BicliqueSDP.Chain
/-- §3.3, p. 16: `½√g(G) ≤ h₁(G)`. -/
theorem sqrt_g_le_h1 {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1] [DecidableEq V2]
(E : V1 → V2 → Prop) [∀ i j, Decidable (E i j)] :
(1 / 2) * Real.sqrt (g E) ≤ h1 E := by sorry
end BicliqueSDP.Chain
Source
Laurent, Polak, Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886v2, §3.3, p. 16, "Proof of ½√g(G) ≤ h₁(G)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.