= Complement theta number
{title2=$\bar\vartheta(G)=\vartheta(\bar G)$}
For a finite simple <graph> with at least one vertex, the complement theta number has the equivalent <semidefinite program> formulations
$$
\bar\vartheta(G)=\min\left\{t:
\begin{pmatrix}t&\mathbf1^T\\\mathbf1&Z\end{pmatrix}\succeq0,
\ Z_{ii}=1,\ Z_{ij}=0\text{ for }ij\in E(G)\right\}
$$
and
$$
\bar\vartheta(G)=\min\{t:U\succeq0,\ U_{ii}=t-1,\ U_{ij}=-1\text{ for }ij\in E(G)\}.
$$
The <Schur complement> and $U=tZ-J$ prove the equivalence; any feasible $t$ is at least one, so division by $t$ is valid. For a <graph> with an edge, $U/(t-1)$ is the <Gram matrix> of a <strict vector coloring>. Consequently $\bar\vartheta(G)$ is the strict vector chromatic number, and an ordinary $k$-<graph colouring> gives $\bar\vartheta(G)\leq k$ by assigning the colors the vertices of a <regular simplex>.
Back to article page
