Ruriko Yoshida
University of Kentucky
Department of Statistics
3:30 PM
154 Hurley
Extremal Positive Semidefinite Matrices for Graphs Without $K_5$ Minors
For a graph $G$ with $p$ vertices the closed convex cone $\mathbb{S}^p_{\succeq0}(G)$ consists of all real positive semidefinite $p\times p$ matrices with zeros in the off-diagonal entries corresponding to nonedges of~$G$. The extremal rays of this cone and their associated ranks have applications to matrix completion problems, maximum likelihood estimation in Gaussian graphical models in statistics, and Gauss elimination for sparse matrices.
In this talk, we will show that the normal vectors to the facets of the $(\pm1)$-cut polytope of $G$ specify the
off-diagonal entries of extremal matrices in $\mathbb{S}^p_{\succeq0}(G)$ for a weakly bipartite graph $G$.
We will also show that the constant term of the linear equation of each facet-supporting hyperplane is the rank of its corresponding extremal matrix in $\mathbb{S}^p_{\succeq0}(G)$. Furthermore, we show that if $G$ is series-parallel then this gives a complete characterization of all possible extremal ranks of $\mathbb{S}^p_{\succeq0}(G)$, consequently solving the sparsity order problem for series-parallel
graphs.
This is joint work with Caroline Uhler at IST/MIT and Liam Solus at University of Kentucky (IST/MIT).
Full List of Applied Math Seminar Speakers
