Loading…

A new graph parameter related to bounded rank positive semidefinite matrix completions

The Gram dimension of a graph is the smallest integer such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of , can be completed to a positive semidefinite matrix of rank at most (assuming a positive semidef...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2014-06, Vol.145 (1-2), p.291-325
Main Authors: Laurent, Monique, Varvitsiotis, Antonios
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Gram dimension of a graph is the smallest integer such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of , can be completed to a positive semidefinite matrix of rank at most (assuming a positive semidefinite completion exists). For any fixed the class of graphs satisfying is minor closed, hence it can be characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is for and that there are two minimal forbidden minors: and for . We also show some close connections to Euclidean realizations of graphs and to the graph parameter of van der Holst (Combinatorica 23(4):633–651, 2003 ). In particular, our characterization of the graphs with implies the forbidden minor characterization of the 3-realizable graphs of Belk (Discret Comput Geom 37:139–162, 2007 ) and Belk and Connelly (Discret Comput Geom 37:125–137, 2007 ) and of the graphs with of van der Holst (Combinatorica 23(4):633–651, 2003 ).
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-013-0648-x