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

matrix completion, semidefinite programming, correlation matrix, graph minor, Grothendieck constant.
Logistics (theme 3)
Cornell University Library
arXiv.org e-Print archive
Semidefinite programming and combinatorial optimization , Spinoza prijs Lex Schrijver
Networks and Optimization

Eisenberg-Nagy, M, Laurent, M, & Varvitsiotis, A. (2012). On bounded rank positive semidefinite matrix completions of extreme partial correlation matrices.. arXiv.org e-Print archive. Cornell University Library .