2012-03-01

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

## Publication

### Publication

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

Additional Metadata | |
---|---|

, , , , | |

Cornell University Library | |

arXiv.org e-Print archive | |

Semidefinite programming and combinatorial optimization , Spinoza prijs Lex Schrijver | |

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