= Solution
If $m=0$, use a single color. Otherwise choose
$$
r=\max\left\{0,\left\lceil\log_3\frac{4m}{n}\right\rceil\right\}.
$$
The previous bound gives $\mathbb E B\leq n/4$, including the case $r=0$. By <Markov inequality>, $\mathbb P(B>n/2)\leq1/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|\leq B\leq 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|\geq 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\leq2\max\{1,(4m/n)^{\log_3 2}\}$. A simple <graph> has $m\leq n(n-1)/2$, hence <semicoloring by independent hyperplanes> gives
$$
\boxed{k=O(n^\gamma),\qquad\gamma=\log_3 2=\frac{\log2}{\log3}\approx0.63093<1.}
$$
Back to article page
