Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.