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

For a proper three-graph colouring $c$, associate the colors with the three roots of unity $d(i)=\exp (2\pi i(c(i)-1)/3)$, viewed as unit vectors in ${\mathbb{R}}^2$. Define $U_{ij}=2⟨d(i),d(j)⟩$ using the real inner product.

This is twice a Gram matrix, so it is a positive semidefinite matrix. Its diagonal is $2$. On every edge, the endpoint colors differ, so their vectors make angle $2\pi /3$ or $4\pi /3$ and $U_{ij}=2\cos (2\pi /3)=-1$. Thus $t=3$ and this $U$ are feasible in the second semidefinite program, provingThis is the regular simplex construction of a strict vector coloring.