TITLE:  Connecting Two Problems with a Spectrahedron

ABSTRACT:  Spectrahedra are natural generalizations of polyhedra that arise as parameterizations of slices of the cone of positive semidefinite matrices.  To a graph G we can associate a spectrahedron known as an elliptope.  We will use the elliptope to connect two well-studied problems via their underlying geometry.  The first problem is the well-known max-cut problem from linear programming, the feasible region of which is the cut polytope of G.  The second problem is the positive semidefinite matrix completion problem whose solution is characterized by extremal rays of the cone of concentration matrices for G.  We will begin with a brief introduction to the geometry of positive semidefinite matrices and spectrahedra.  Then we will define these two problems and their associated convex bodies.  Finally, we will see that for some graphs the facets of the cut polytope correspond to extremal rays of the cone of concentration matrices, and that this correspondence is given by the elliptope and its dual.  Moreover, we will see that the shape of the facet decides the rank of the corresponding extremal ray.