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

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