Combinatorial conditions for low rank solutions in semidefinite programming

In this thesis we investigate combinatorial conditions that guarantee the existence of low-rank optimal solutions to semidefinite programs. Results of this type are important for approximation algorithms and for the study of geometric representations of graphs. The structure of the thesis is as follows:

In Chapter 1 we motivate the study of this problem and sketch the main contributions of the thesis.

In Chapters 2, 3 and 4 we give preliminaries on graph theory, semidefinite programming and relaxations of cut polyhedra.

In Chapter 5 we study the low-rank positive semidefinite matrix completion problem. Our main tool is a new minor monotone graph parameter, called the Gram dimension of a graph, for which we determine the forbidden minors for values up to 4. Based on this we find that any semidefinite program achieving its optimum, has an optimal solution of rank at most the Gram dimension of its aggregate sparsity pattern.

In Chapter 6 we investigate the relation of the Gram dimension with Euclidean graph realizations and a well-known spectral graph parameter.

In Chapter 7 we investigate complexity aspects of the Gram dimension.

In Chapter 8 we survey the topic of Grothendieck inequalities and in Chapter 9 we derive a closed-form formula for the Grothendieck constant of graphs with noK_5-minor.

In Chapter 10 we consider semidefinite programs with the unique constraint that every feasible matrix has diagonal entries equal to one. For such semidefinite programs, to prove the existence of low-rank optimal solutions, we introduce a graph parameter called the extreme Gram dimension of a graph. This parameter is upper bounded by the Gram dimension and is closely related to the rank-constrained Grothendieck constant. We show that the extreme Gram dimension is minor monotone and we identify the forbidden minors for graphs with extreme Gram dimension at most 2. Moreover, we show that the extreme Gram dimension is upper bounded by a new treewidth-like parameter, called the strong largeur d’arborescence.

In Chapter 11 we determine a sufficient condition for constructing partial positive semidefinite matrices with a unique positive semidefinite completion. Such partial matrices are useful to get lower bounds for the Gram dimension and the extreme Gram dimension. Lastly, we determine interesting connections with the theory of universally rigid graphs.