Solution

Colour every vertex independently red or blue, each with probability

1/2

. A fixed

r

-element hypergraph edge is monochromatic with probability

2^{1 - r}

. If there are

m < 2^{r - 1}

hypergraph edges, the expected number of monochromatic hypergraph edges is

m 2^{1 - r} < 1

. Equivalently, the union bound says that the probability of even one monochromatic hypergraph edge is less than one. A proper two-colouring therefore exists.

For the converse, suppose

r \geq 2

, put

N = 2 r^{2}

, and sample

m

independent uniformly random

r

-subsets of an

N

-vertex set. Initially this is a multihypergraph. For a fixed two-colouring with

a

red vertices, a sampled hypergraph edge is monochromatic with probability

q (a) = \frac{( r a ) + ( r N - a )}{( r N )} .

(1)

The numerator is minimized by

a = N /2 = r^{2}

. To see this discretely, use

(r a + 1) - (r a) = (r - 1 a)

: the successive difference of the numerator is

(r - 1 a) - (r - 1 N - a - 1)

, negative up to the middle and positive afterwards. Binomial coefficients with an upper index below

r

are understood as zero.

For this balanced colouring,

q (a) \geq 2 \frac{( r r ^{2} )}{( r 2 r ^{2} )} = 2^{1 - r} \prod_{j = 0}^{r - 1} \frac{1 - j / r ^{2}}{1 - j / ( 2 r ^{2} )} \geq 2^{1 - r} \prod_{j = 0}^{r - 1} (1 - j / r^{2}) .

(2)

The elementary inequality

\prod_{j} (1 - u_{j}) \geq 1 - \sum_{j} u_{j}

, valid for

0 \leq u_{j} \leq 1

, gives

q (a) \geq 2^{1 - r} (1 - \frac{r ( r - 1 )}{2 r ^{2}}) > 2^{- r} .

(3)

Thus any fixed colouring is proper for all the sampled hypergraph edges with probability at most

e^{- m 2^{- r}}

. There are

2^{N}

colourings, so choose

m = ⌈ (N lo g 2 + 1) 2^{r} ⌉ .

(4)

A union bound makes the probability that any proper colouring exists at most

2^{N} e^{- m 2^{- r}} \leq e^{- 1} < 1

. Some sampled multihypergraph is consequently not two-colourable. Remove repeated copies of its hypergraph edges: this changes neither which colourings are proper nor non-two-colourability, and leaves at most