§3.3, p. 18 — h₁(G) ≤ ¼α(G)
ProvedBicliqueSDP.Chain.h1_le_alphabicliqueslovasz-thetap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
For every bipartite graph with stability number (the maximum of over bipartite biindependent pairs),
Together with it yields 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: `h₁(G) ≤ ¼α(G)`. -/
theorem h1_le_alpha {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1] [DecidableEq V2]
(E : V1 → V2 → Prop) [∀ i j, Decidable (E i j)] :
h1 E ≤ (1 / 4) * alpha 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 h₁(G) ≤ ¼α(G)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.