MaxCut, orthonormal representations, and extension complexity of polytopes
MaxCut, orthonormal representations, and extension complexity of polytopes
-
Igor Balla, Masaryk University
In this talk, we will present a bipartite generalization of Alon and
Szegedy鈥檚 nearly orthogonal vectors, and discuss how it implies strong bounds
for several extremal problems involving MaxCut, the Lov谩sz theta function,
vector chromatic number, minimum semidefinite rank, nonnegative rank, and
extension complexity of polytopes. Along the way, we will present some
interesting inequalities involving these parameters.
听