Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

From the stable set problem to convex algebraic geometry

Algebra & Discrete Mathematics

Speaker: Joao Gouveia, University of Washington
Location: 2112 MSB
Start time: Fri, Oct 31 2008, 2:10PM

The theta body of a graph is a well-known semidefinite relaxation of its stable set polytope, introduced by Lovász. He later observed an alternate definition of the theta body via sums of squares polynomials modulo the vanishing ideal of the vertices of the stable set polytope. These ideas allow us to define generalized theta bodies for polynomial ideals, which approximate the convex hulls of their varieties. We derive properties of these theta bodies and criteria for when the kth body coincides with the convex hull of the variety. Our methods give rise to a new set of semidefinite relaxations for cut polytopes of graphs, which in turn provides approximations of the max cut problem.