Due: Thursday, April 15, 2021.
Penalty for late homeworks: 10% for each day or part of a day.

1. Given a complete graph G = (V,E) with edge weights we and n = kp nodes, we wish to partition the vertices into k sets each containing exactly p vertices so as to minimize the sum of the edge weights of the edges with endpoints in the same set. Let e denote the n-vector of ones and let wii = 0 for i = 1,,n. Show that the following semidefinite program gives a lower bound on the optimal value of this problem, where X is an n × n matrix: 2. The coloring number χ of an undirected graph G = (V,E) is the smallest number of colors needed to color the vertices V so that no two adjacent vertices share a color. Let n = |V | and let A denote the n × n adjacency matrix. The Hoffman bound on χ is where λmax(A) and λmin(A) denote the largest and smallest eigenvalues of A respectively. Assume E. Prove 3. Recall the Hoffman bound from Question 2. Show the bound is tight if G is a complete bipartite graph with E. (In a complete bipartite graph, V can be partitioned into two sets V 1 and V 2, every vertex in V 1 is adjacent to every vertex in V 2, no vertex in V 1 is adjacent to any other vertex in V 1, and no vertex in V 2 is adjacent to any other vertex in V 2.)
4. Let Assume X is symmetric. Assume the 2 × 2 submatrices are positive semidefinite. Show that x13 can be chosen so that X is positive semidefinite. (This result can be generalized to allow an approach to solving semidefinite programs that exploits sparsity. The approach involves looking at cliques in chordal graphs.)

5. The package cvx is a modeling framework for convex optimization problems that works within matlab. Install cvx, available from http://cvxr.com/cvx/download/

Use it to solve the Lovász theta relaxation of some randomly generated node packing problems using the routine lovaszthetarand.m

You need to select 2 parameters in matlab: the matrix size msize, and density which controls the number of edges in the graph. The expected number of edges is For a version of the code for solving non-random instances, see lovasztheta.m and an example file edges8.mat

6. Give a progress report on your project. Your report should be at least a couple of paragraphs long. It doesn’t need to repeat anything from your initial report from Homework 3.
 John Mitchell Amos Eaton 325 x6915. mitchj at rpi dot edu Office hours: Monday and Thursday 1pm–2pm. webex: https://rensselaer.webex.com/meet/mitchj