کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656817 | 1632985 | 2014 | 41 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope](/preview/png/4656817.png)
• We introduce a new graph parameter related to bounded rank positive semidefinite matrix completions.
• We introduce a new tree-width-like graph parameter related to the “largeur d'arborescence” defined by Colin de Verdiere.
• We identify the full list of forbidden minors for both parameters for values at most 2.
• We identify three families of forbidden minors for all values.
• We establish links with the bounded rank Grothendieck constant.
We study a new geometric graph parameter egd(G)egd(G), defined as the smallest integer r⩾1r⩾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)⩽regd(G)⩽r if and only if the rank-r Grothendieck constant of G is equal to 1. We show that the parameter egd(G)egd(G) is minor monotone, we identify several classes of forbidden minors for egd(G)⩽regd(G)⩽r and we give the full characterization for the case r=2r=2. We also show an upper bound for egd(G)egd(G) in terms of a new tree-width-like parameter la⊠(G)la⊠(G), defined as the smallest r for which G is a minor of the strong product of a tree and KrKr. We show that, for any 2-connected graph G≠K3,3G≠K3,3 on at least 6 nodes, egd(G)⩽2egd(G)⩽2 if and only if la⊠(G)⩽2la⊠(G)⩽2.
Journal: Journal of Combinatorial Theory, Series B - Volume 108, September 2014, Pages 40–80