### Abstract

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 problem of finding low-rank solutions to semidefinite programs over the elliptope, and also by its relevance to the bounded rank Grothendieck constant. Indeed, egd(G)⩽r if and only if the rank-r Grothendieck constant of G is equal to 1. We show that the parameter egd(G) is minor monotone, we identify several classes of forbidden minors for egd(G)⩽r and we give the full characterization for the case r=2. We also show an upper bound for egd(G) in terms of a new tree-width-like parameter la⊠(G), defined as the smallest r for which G is a minor of the strong product of a tree and Kr. We show that, for any 2-connected graph G≠K3,3 on at least 6 nodes, egd(G)⩽2 if and only if la⊠(G)⩽2.

Original language | English |
---|---|

Pages (from-to) | 40-80 |

Journal | Journal of Combinatorial Theory, Series B, Graph theory |

Volume | 108 |

Issue number | September 2014 |

Early online date | 19 Mar 2014 |

DOIs | |

Publication status | Published - Sep 2014 |

## Fingerprint Dive into the research topics of 'Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope'. Together they form a unique fingerprint.

## Cite this

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, Graph theory*,*108*(September 2014), 40-80. https://doi.org/10.1016/j.jctb.2014.02.011