p. 12, after Eq. (25) — ϑ(G) = α(G) for every bipartite graph G
ProvedBicliqueSDP.Chain.theta_eq_alpha_bipartitebicliquesgraph-theorylovasz-thetap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a bipartite graph and the maximum of over its bipartite biindependent pairs , that is, its stability number. Then the theta number of , viewed as a graph on , equals its stability number:
The proof of Proposition 1.2 uses this to turn the bounds and into bounds in terms of .
Formalization Note The paper states this more generally for perfect graphs, citing Grötschel, Lovász and Schrijver; only the bipartite clause, which the paper uses, is formalized. is evaluated on bipGraph E, and is the paper's maximum over biindependent pairs.
Preamble
import Mathlib import Definitions.Def_BicliqueSDP_Chain_Model
Formal statement
namespace BicliqueSDP.Chain
/-- p. 12, after Eq. (25): `ϑ(G) = α(G)` if `G` is bipartite. -/
theorem theta_eq_alpha_bipartite {V1 V2 : Type} [Fintype V1] [Fintype V2] [DecidableEq V1]
[DecidableEq V2] (E : V1 → V2 → Prop) [∀ i j, Decidable (E i j)] :
theta (bipGraph E) = alpha E := by sorry
end BicliqueSDP.Chain
Source
Laurent, Polak, Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886v2, p. 12, the sentence after Eq. (25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.