New semidefinite and eigenvalue bounds for the graph partitioning problems

The k-partition problem is the problem of partitioning the vertex set of a graph 
into k sets of given sizes such that the total weight of edges joining different 
sets is optimized. In the case that there is no restriction on the sizes of the
subsets, the optimization problem is know as the k-cut problem.

In this talk we show how to simplify a matrix-lifting semidefinite programming
(SDP) relaxation for the graph partitioning problems for several classes of graphs,
and also show how to aggregate triangle and independent set constraints for graphs
with symmetry. Further, we present eigenvalue bounds for the graph partitioning
problems, which are the first known closed form bounds applicable to any graph and
partitions, thereby extending several well-known results in spectral graph theory.
Finally, we present vector-lifting SDP bounds for the graph partitioning problems
including the bandwidth problem.