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 |
Description
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.