***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Igor Balla (Masaryk University)

Thursday 7th November, 3:00 in Fine Hall 224.

Title: 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.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)