Lemma 1.1, p. 2 — ¼α_bal = ½√g_bal = h_bal ≤ h ≤ ½√g ≤ ¼α, and the equality cases
ProvedBicliqueSDP.Chain.lemma_1_1bicliquesgraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a bipartite graph, and let , , and their balanced analogues , , be the maxima of , and over all (respectively, all balanced) bipartite biindependent pairs . Then
The chain (3) gives the first inequality of Proposition 1.2, , and (4) characterises when the combinatorial bounds are tight.
Formalization Note The chained equivalences (4) are stated as two biconditionals.
Preamble
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
Formal statement
namespace BicliqueSDP.Chain
/-- Lemma 1.1 (p. 2): relations (3) and (4). -/
theorem lemma_1_1 {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1] [DecidableEq V2]
(E : V1 → V2 → Prop) [∀ i j, Decidable (E i j)] :
((1 / 4) * alphaBal E = (1 / 2) * Real.sqrt (gBal E) ∧
(1 / 2) * Real.sqrt (gBal E) = hBal E ∧ hBal E ≤ h E ∧
h E ≤ (1 / 2) * Real.sqrt (g E) ∧ (1 / 2) * Real.sqrt (g E) ≤ (1 / 4) * alpha E) ∧
((h E = (1 / 4) * alpha E ↔ (1 / 2) * Real.sqrt (g E) = (1 / 4) * alpha E) ∧
((1 / 2) * Real.sqrt (g E) = (1 / 4) * alpha E ↔ alpha E = alphaBal E)) := by sorry
end BicliqueSDP.Chain
Source
Laurent, Polak, Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886v2, p. 2, Lemma 1.1, relations (3) and (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.