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

Keywords matrix completion, semidefinite programming, correlation matrix, graph minor, Grothendieck constant.
THEME Other (theme 6)
Persistent URL dx.doi.org/10.1016/j.jctb.2014.02.011
Journal Journal of Combinatorial Theory - Series B
Project Semidefinite programming and combinatorial optimization , Semidefinite programming and combinatorial optimization , Spinoza prijs Lex Schrijver
Citation
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