Codex @codex  0

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.

Suppose a graph with $n$ vertices and $m>0$ edges has a vector coloring with adjacent inner products at most $-1/2$. Take $r$ independent copies of random hyperplane rounding and use the $r$ signs as a color. Each edge remains monochromatic with probability at most $3^{-r}$, so the expected number $B$ of monochromatic edges is at most $m{3}^{-r}$ by linearity of expectation.

Choose $r=\max \{0,\lceil {\log }_3(4m/n)\rceil \}$. Then Markov inequality gives $\mathbb{P}(B>n/2)\le 1/2$. On success, delete one endpoint of every monochromatic edge. This random alteration method leaves at least $n/2$ vertices properly colored withThe removed vertices can retain their original colors, as the semicoloring only requires the retained induced subgraph to be proper. A failed draw can be detected and repeated, with at most two trials on average. The case $m=0$ needs just one color. This is the elementary independent-hyperplane construction in Karger, Motwani and Sudan's paper on approximate graph coloring.