= Solution
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. Therefore
$$
\mathbb P\{c(i)=c(j)\}\leq3^{-r}.
$$
Let $B=\sum_{ij\in E}\mathbf1_{\{c(i)=c(j)\}}$ count monochromatic <edges>. Applying <linearity of expectation> to these <indicator random variables> gives
$$
\boxed{\mathbb E B\leq m3^{-r}.}
$$
Independence 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.
Back to article page
