A new graph parameter related to bounded rank positive semidefinite matrix completions.
Mathematical Programming Series A , Volume 145 - Issue 1-2 p. 291- 325
The Gram dimension gd(G) of a graph G is the smallest inte- ger k ≥ 1 such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of G, can be completed to a positive semidefinite matrix of rank at most k (assuming a positive semidefinite completion exists). For any fixed k the class of graphs satisfying gd(G) ≤ k is minor closed, hence it can characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is Kk+1 for k ≤ 3 and that there are two minimal forbidden minors: K5 and K2,2,2 for k = 4. We also show some close connections to Euclidean realizations of graphs and to the graph parameter ν=(G) of . In particular, our characterization of the graphs with gd(G) ≤ 4 implies the forbidden minor characterization of the 3-realizable graphs of Belk and Connelly [8,9] and of the graphs with ν=(G) ≤ 4 of van der Holst .
|matrix completion, Gram realization, semidefinite programming, graph minor, tree-width, graph realization.|
|Other (theme 6)|
|Mathematical Programming Series A|
|Spinoza prijs Lex Schrijver , Semidefinite programming and combinatorial optimization|
|Organisation||Networks and Optimization|
Laurent, M, & Varvitsiotis, A. (2014). A new graph parameter related to bounded rank positive semidefinite matrix completions. Mathematical Programming Series A, 145(1-2), 291–325. doi:10.1007/s10107-013-0648-x