Georgia Institute of Technology College of Sciences

Given a graph G on p vertices we consider the cone of concentration matrices associated to G; that is, the cone of all (p x p) positive semidefinite matrices with zeros in entries corresponding to the nonedges of G. Due to its applications in PSD-completion problems and maximum-likelihood estimation, the geometry of this cone is of general interest. A natural pursuit in this geometric investigation is to characterize the possible ranks of the extremal rays of this cone. We will investigate this problem combinatorially using the cut polytope of G and its semidefinite relaxation, known as the elliptope of G. For the graphs without K_5 minors, we will see that the facet-normals of the cut polytope identify a distinguished set of extremal rays for which we can recover the ranks. In the case that these graphs are also series-parallel we will see that all extremal ranks are given in this fashion. Time permitting, we will investigate the potential for generalizing these results. This talk is based on joint work with Caroline Uhler and Ruriko Yoshida.