Eq. (25), p. 12 — las₁(G) = ϑ(G) for every graph G
ProvedBicliqueSDP.Chain.eq_25graph-theorylovasz-thetap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let be any finite graph. The first Lasserre bound
and Lovász's theta number
coincide:
The paper calls this well known and refers to Grötschel, Lovász and Schrijver; it is used in §3.3 to pass between the two formulations of in the proofs of and .
Preamble
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
Formal statement
namespace BicliqueSDP.Chain
/-- Eq. (25) (p. 12): for every finite graph `G`, `las₁(G) = ϑ(G)`. -/
theorem eq_25 {V : Type} [Fintype V] (G : SimpleGraph V) : las1 G = theta G := by sorry
end BicliqueSDP.Chain
Source
Laurent, Polak, Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886v2, p. 12, Eq. (25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.