= Solution
For an <edge> $ij$, put $\rho=\langle v_i,v_j\rangle$ and $\theta=\arccos\rho$. Since $\rho\leq-1/2$, we have $\theta\geq2\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> gives
$$
\boxed{\mathbb P(H\text{ cuts }ij)=\frac{\theta}{\pi}\geq\frac23.}
$$
If $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\times2$ block of $U$ forces $t\geq2$, 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.
Back to article page
