The Algebraic Boundary of Graph Elliptopes

This paper studies the algebraic boundary of the elliptope E(G) of a graph G. In particular, we completely characterize the algebraic boundary of E(G) when G is cycle completable. In this case, the boundary is a union of determinantal hypersurfaces and Lissajous varieties, i.e., images of rational linear subspaces under the coordinatewise cosine map. As an application,
we show that the algebraic boundary of E(G) is disjoint from its interior precisely when E(G) is a spectrahedron or, equivalently, when G is a chordal graph. A central ingredient for the defining equation of the boundary hypersurface is the cycle polynomial, which captures the algebraic boundary of the elliptope E(Cn) of the n-th cycle graph Cn. We show that the cycle polynomial of Cn is the resultant of two smaller cycle polynomials. Via this result, Sylvester’s determinantal formula offers an inductive method for computing the cycle polynomial which
mirrors a geometric property of metric polytopes. We also determine the degree of the homogeneous cycle polynomial, settling an open question of Sturmfels and Uhler (2010).