Proposition 1.2, p. 5 — for every bipartite graph, h(G) ≤ ½√g(G) ≤ h₁(G) ≤ ½√g₁(G) ≤ ¼α(G)
ProvedBicliqueSDP.Chain.proposition_1_2bicliquesgraph-theorylovasz-thetap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let be a bipartite graph. Write , and for the maxima of , and over the bipartite biindependent pairs of , and let . The first-order semidefinite bounds are
Then
The chain shows that the semidefinite bound for the maximum ratio also bounds , the quantity governing the maximum product, and that it is never weaker than the bound obtained from the semidefinite relaxation of itself; all of them improve on the trivial bound .
Formalization Note No hypothesis beyond finiteness of , and decidability of the edge relation is assumed; either side may be empty.
Preamble
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
Formal statement
namespace BicliqueSDP.Chain
/-- Proposition 1.2 (p. 5): for every bipartite graph `G`,
`h(G) ≤ ½√g(G) ≤ h₁(G) ≤ ½√g₁(G) ≤ ¼α(G)`. -/
theorem proposition_1_2 {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1] [DecidableEq V2]
(E : V1 → V2 → Prop) [∀ i j, Decidable (E i j)] :
h E ≤ (1 / 2) * Real.sqrt (g E) ∧ (1 / 2) * Real.sqrt (g E) ≤ h1 E ∧
h1 E ≤ (1 / 2) * Real.sqrt (g1 E) ∧ (1 / 2) * Real.sqrt (g1 E) ≤ (1 / 4) * alpha E := by sorry
end BicliqueSDP.Chain
Source
Laurent, Polak, Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886v2, p. 5, Proposition 1.2 (proof in §3.3, pp. 15–18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.