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$.

, , , ,
Academic Press
doi.org/10.1016/j.jctb.2014.02.011
Journal of Combinatorial Theory - Series B
Semidefinite programming and combinatorial optimization , Semidefinite programming and combinatorial optimization , Spinoza prijs Lex Schrijver
Networks and Optimization

Eisenberg-Nagy, M., Laurent, M., & Varvitsiotis, A. (2014). Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope. Journal of Combinatorial Theory - Series B, 108, 40–80. doi:10.1016/j.jctb.2014.02.011