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

Let $J=11^T$ be the all-ones matrix. Every feasible block matrix in the first formulation has $t\ge 1$, because its principal $2\times 2$ submatrix on indices $0,i$ is $\left(\begin{array}{cc}t& 1\\ 1& 1\end{array}\right)$ and is a positive semidefinite matrix. In particular, $t>0$.

By the Schur complement,Set $U=tZ-J$. Then $U⪰0$, $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\ge 1$, and $Z=(U+J)/t$ has $Z_{ii}=1$, $Z_{ij}=0$ on edges, and $Z-J/t=U/t⪰0$.

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.

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.

For an edge $ij$, put $\rho =⟨v_i,v_j⟩$ and $\theta =\arccos \rho$. Since $\rho \le -1/2$, we have $\theta \ge 2\pi /3$.

The random normal $a$ has the isotropic Gaussian distribution $N(0,I_p)$. Its distribution is invariant under orthogonal transformations; if $v_i,v_j$ are linearly independent, its projection onto their plane has a uniformly distributed direction. The signs of its inner products with $v_i,v_j$ differ in two sectors of total angle $2\theta$, out of $2\pi$. Thus random hyperplane rounding givesIf $v_j=-v_i$, the signs differ with probability one and the same formula holds with $\theta =\pi$. Zero inner products have probability zero, since each $v_i$ is a unit vector.

If the graph has an edge, its corresponding principal $2\times 2$ block of $U$ forces $t\ge 2$, so the division by $t-1$ used to obtain the Gram matrix is valid. An edgeless graph can instead be colored with one color directly.

A fixed edge is monochromatic exactly when none of the $r$ hyperplanes separates its endpoints. Each hyperplane fails to cut it with probability at most $1/3$, and the hyperplanes are independent. ThereforeLet $B={\sum }_{ij\in E}{1}_{\{c(i)=c(j)\}}$ count monochromatic edges. Applying linearity of expectation to these indicator random variables givesIndependence between different edges is unnecessary; only the independently sampled hyperplanes are used. The $r$ signs provide at most $2^r$ colors, whether or not every sign region is nonempty.

If $m=0$, use a single color. Otherwise chooseThe previous bound gives $\mathbb{E}B\le n/4$, including the case $r=0$. By Markov inequality, $\mathbb{P}(B>n/2)\le 1/2$. Sample the hyperplanes, count the monochromatic edges, and repeat if $B>n/2$. The success probability is at least $1/2$, so at most two draws are needed on average.

For a successful draw, select one endpoint of each monochromatic edge and let $D$ be the union of the selected vertices. Then $|D|\le B\le n/2$. Every monochromatic edge meets $D$, so the original colors give a proper graph colouring on the induced subgraph with vertex set $W=V\setminus D$. Since $|W|\ge n/2$, the coloring of all vertices is a semicoloring. This is a random alteration method; no additional colors for $D$ are required.

The number of available colors satisfies $2^r\le 2\max \{1,(4m/n{)}^{{\log }_{3}2}\}$. A simple graph has $m\le n(n-1)/2$, hence semicoloring by independent hyperplanes gives