21 november 2024
14:00 t/m
15:00
[DMO] Igor Balla: MaxCut, orthonormal representations, and extension complexity of polytopes
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.