§3.3, p. 18 — g₁(G) ≤ α(G)·h₁(G)
ProvedBicliqueSDP.Chain.g1_le_alpha_mul_h1bicliqueslovasz-thetap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
For every bipartite graph ,
where and are the semidefinite bounds (8) and (9) and is the stability number.
Combined with this gives , i.e. the last inequality of Proposition 1.2.
Preamble
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
Formal statement
namespace BicliqueSDP.Chain
/-- §3.3, p. 18: `g₁(G) ≤ α(G) h₁(G)`. -/
theorem g1_le_alpha_mul_h1 {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1]
[DecidableEq V2] (E : V1 → V2 → Prop) [∀ i j, Decidable (E i j)] :
g1 E ≤ alpha 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. 18, "Proof of g₁(G) ≤ α(G)h₁(G)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.