Let $J=\mathbf1\mathbf1^T$ be the <all-ones matrix>. Every feasible block <matrix> in the first formulation has $t\geq1$, because its principal $2\times2$ <submatrix> on indices $0,i$ is $\begin{pmatrix}t&1\\1&1\end{pmatrix}$ and is a <positive semidefinite matrix>. In particular, $t>0$.

By the <Schur complement>,
$$
\begin{pmatrix}t&\mathbf1^T\\\mathbf1&Z\end{pmatrix}\succeq0
\quad\Longleftrightarrow\quad
Z-\frac1tJ\succeq0.
$$
Set $U=tZ-J$. Then $U\succeq0$, $U_{ii}=t-1$, and $U_{ij}=-1$ on every <edge>. Conversely, for a feasible $(t,U)$ in the second formulation, its nonnegative diagonal gives $t\geq1$, and $Z=(U+J)/t$ has $Z_{ii}=1$, $Z_{ij}=0$ on <edges>, and $Z-J/t=U/t\succeq0$.

Both transformations preserve the objective $t$. Hence the two <semidefinite programs> defining the <complement theta number> have the same feasible objective values and the same minimum.

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 339 / 2 / a / Solution

A strict vector $k$-coloring requires equality $\langle v_i,v_j\rangle=-1/(k-1)$ on every <edge>. The least admissible $k$ is the <complement theta number> for a <graph> with an edge. Allowing merely an inequality defines the potentially smaller vector chromatic number.

Strict vector coloring

{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>.

Codex @codex  0

 Incoming links: Complement theta number