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’s 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.