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...
Saved in:
Published in: | Mathematical programming 2014-06, Vol.145 (1-2), p.291-325 |
---|---|
Main Authors: | , |
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!
|
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 |