Properties of SDP solution Lovasz Theta function

121 Views Asked by At

I have the following SDP program for a graph $G=(V,E)$, $|V| = n$, $k \in \mathbb{N}$ and $k<n$, $J$ the matrix of all ones. \begin{equation} \begin{aligned} & {\underset{A,B \in \mathbb{S}^n}{ \text{ Maximize}}} & & \quad \langle J, k A + (k^2 - k) B \rangle \\ & \text{subject to} & & \langle I, A \rangle = \frac{1}{k} \\ &&& A_{ij} =0\quad \forall (i,j) \in E \\ &&& B_{ii} = 0 \quad \forall i \in V \\ &&& A - B \succeq 0, \, A + (k-1)B \succeq 0 \end{aligned} \end{equation}

Denote by $A^*$ and $B^*$ optimal solutions to this program. Now it appears that the eigenvalues of $A^*$ and $B^*$ follow some regularities that I cannot prove. If we write $\lambda_1(M)$ to be the largest eigenvalue of a matrix $M$ it seems as if: $$\lambda_1(A^*+(k-1)B^*) \leq \frac{1}{k} \\ \lambda_1(B^*) \leq \frac{1}{k^2} \\ \lambda_1(A^*) < \frac{2}{k^2} $$

For context, this program computes the Lovász theta function for $\vartheta(K_k \square G)$ (I have reformulated it). Here '$\square$' denotes the Cartesian product of graphs and $K_k$ is the complete graph on $k$ vertices. I want to prove some results on $\vartheta(K_k \square G)$ but I don't understand the ins and outs of this SDP program well enough. Can anyone provide some insights or provide me with references in the right direction?