I have a question I hope you might be able to answer.

Let's say we have an integer program for the **stable set** problem (or clique, not principal).

\begin{equation} \begin{aligned} & \text{maximize} & \sum_i x_i \\ & \text{subject to} & \\ %& & \sum_{i \in C} x_i \leq 1 \text{ for all cliques } C\\ & & x_i+x_j \leq 1 \text { for } i,j \in E \\ & & x_i \in \{0,1\} \end{aligned} \end{equation}

One can use relaxation to obtain upper bounds like linear programming (LP) relaxation (relaxing integer variables to be in $[0,1]$) or using SDP relaxation (Lovasz)

\begin{equation} \begin{aligned} & \text{maximize} & \sum_i \sum_j X_{ij} \\ & \text{subject to} & \\ & & \mbox{tr} (X) = 1 \\ & & X_{ij} = 0 \text{ if } \{i,j\} \in E(G) \\ & &X \succ 0 \end{aligned} \end{equation}

Is there a nice *direct* proof that the value of the SDP relaxation above is always at most the value of the LP relaxation of the integer program?

Any help and thoughts will be greatly appreciated.

Edit: formal description

So let's say the stable set number is $\alpha(G)$, the value of linear relaxation is $z^*_{LP}$, and the value of SDP is $z^*_{SDP}$. The formal statement about "better" would be that $\alpha(G) \leq z^*_{SDP} \leq z^*_{LP}$ for every graph $G$.

3more comments