Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope

We study a new geometric graph parameter $egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of $\rank $ at most $r$. This graph parameter is motivated by its relevance to the bounded rank Grothendieck constant: $egd(G) \le r$ if and only if the rank-$r$ Grothendieck constant of $G$ is equal to 1. The parameter $egd(G)$ is minor monotone. We identify several classes of forbidden minors for $egd(G)\le r$ and give the full characterization for the case $r=2$. We show an upper bound for $egd(G)$ in terms of a new tree-width-like parameter $\sla(G)$, defined as the smallest $r$ for which $G$ is a minor of the strong product of a tree and $K_r$. We show that, for $G\ne K_{3,3}$ 2-connected on at least 6 nodes, $egd(G)\le 2$ if and only if $\sla(G)\le 2$.

• View at Publisher

Free Full Text ( Final Version , 661kb )