Clarification on HW6

Ok, yeah, part (b) was super-vague, sorry about that. Here is a more precise question, I think.

Consider the matrix $M_2\left(y\right)$; if this is psd, then we know, e.g., that $y_{abcd}$ can be written as the dot product of vectors $z_{ab}$ and $z_{cd}$, and also as the dot products of vectors $z_{bc}$ and $z_{ad}$ etc. Similarly $y_{ab}$ can be written as $z_a$ dot $z_b$, and also as $z_{ab}$ dot $z_{\varnothing }$. Hence we now have these vectors $z$'s, each subscripted by at most two vertices, with some constraints relating them.

The goal of the problem is to show that the SDP $Q_1\left(K_{VC}\right)$ is at least as strong as a natural vertex cover SDP, which assigns a vector $v_i$ to each node $i$ to minimize $\sum _i{v}_i\cdot v_i$ subject to

• $(v_{\varnothing }-v_a)(v_{\varnothing }-v_b)=0$ for all edges $ab$.
• $v_{\varnothing }\cdot v_{\varnothing }=1$ (say).

Can you show that the SDP you've created implies these constraints?

Does your SDP also imply the triangle inequalities:

• $\mid \mid v_a-v_b\mid {\mid }^2+\mid \mid v_b-v_c\mid {\mid }^2\ge \mid \mid v_a-v_c\mid {\mid }^2$?

If things are still vague (or if you see some mistakes above), please email/post yr questions.