On bounded rank positive semidefinite matrix completions of extreme partial correlation matrices.

We study a new geometric graph parameter egd(G), defined as the smallest integer r ≥ 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) ≤ 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) ≤ 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 la