THE REAL POSITIVE-DEFINITE COMPLETION PROBLEM - CYCLE COMPLETABILITY

Simple necessary and sufficient conditions have recently been given fo r a real partial positive semidefinite matrix, whose diagonal entries are specified and the graph of whose specified entries is a full cycle , to have a positive semidefinite completion. For an arbitrary graph G , these ''cycle conditions'' on all the cycles of G are then necessary for a partial positive semidefinite matrix, the graph of whose specif ied entries is G, to have a positive semidefinite completion. For whic h graphs G are they also sufficient? We give the following answer, whi ch also relates three topological graph theoretic concepts. The follow ing are equivalent: (0) every partial positive semidefinite matrix, th e graph of whose specified entries is G, that meets the cycle conditio ns for G has a positive semidefinite completion; (1) no induced subgra ph of G is a k-wheel, k greater than or equal to 5, or can be built fr om a k-wheel, k greater than or equal to 4, by subdividing edges and/o r partitioning vertices; (2) every induced subgraph of G that contains a homeomorphic image of K-4 contains an actual copy of K-4; and (3) G has a chordal supergraph that contains no 4-clique not present in G.