Geometry of semidefinite Max-Cut relaxations via matrix ranks

Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and has been shown to be excellent both in theory and in practice. Recently the present authors have derived a new relaxation using a second lifting. This new relaxation, denoted SDP2, is strictly tighter than the relaxation obtained by adding all the triangle inequalities to the well-known relaxation. In this paper we present new results that further describe the remarkable tightness of this new relaxation. Let F-n denote the feasible set of SDP2 for the complete graph with n nodes, let F denote the appropriately defined projection of F-n into S-n, the space of real symmetric n x n matrices, and let C denote the cut polytope in S-n. Further let Y\in F-n be the matrix variable of the SDP2 relaxation and X is an element of F be its projection. Then for the complete graph on 3 nodes, F = C holds. We prove that the rank of the matrix variable Y\in F-3 of SDP2 completely characterizes the dimension of the face of the cut polytope in which the corresponding matrix X lies. This shows explicitly the connection between the rank of the variable Y of the second lifting and the possible locations of the projected matrix X within C. The results we prove for n = 3 cast further light on how SDP2 captures all the structure of C, and furthermore they are stepping stones for studying the general case n greater than or equal to 4. For this case, we show that the characterization of the vertices of the cut polytope via rank Y = 1 extends to all n greater than or equal to 4. More interestingly, we show that the characterization of the one-dimensional faces via rank Y = 2 also holds for n greater than or equal to 4. Furthermore, we prove that if rank Y = 2 for n greater than or equal to 3, then a simple algorithm exhibits the two rank-one matrices (corresponding to cuts) which are the vertices of the one-dimensional face of the cut polytope where X lies.