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

Table of contents
- Solution ii

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

P {c (i) = c (j)} \leq 3^{- r} .

Let

B = \sum_{ij \in E} 1_{{c (i) = c (j)}}

count monochromatic edges. Applying linearity of expectation to these indicator random variables gives

E B \leq m 3^{- 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.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version