= 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 $m2^{1-r}<1$. Equivalently, the <union bound> says that the <probability> of even one <monochromatic> <hypergraph edge> is less than one. \b[A proper two-colouring therefore exists.]
For the converse, suppose $r\geq2$, put $N=2r^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{\binom ar+\binom{N-a}r}{\binom Nr}.
$$
The numerator is minimized by $a=N/2=r^2$. To see this discretely, use $\binom{a+1}r-\binom ar=\binom a{r-1}$: the successive difference of the numerator is $\binom a{r-1}-\binom{N-a-1}{r-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)\geq2\frac{\binom{r^2}r}{\binom{2r^2}r}
=2^{1-r}\prod_{j=0}^{r-1}\frac{1-j/r^2}{1-j/(2r^2)}
\geq2^{1-r}\prod_{j=0}^{r-1}(1-j/r^2).
$$
The elementary inequality $\prod_j(1-u_j)\geq1-\sum_j u_j$, valid for $0\leq u_j\leq1$, gives
$$
q(a)\geq2^{1-r}\left(1-\frac{r(r-1)}{2r^2}\right)>2^{-r}.
$$
Thus any fixed colouring is proper for all the sampled <hypergraph edges> with <probability> at most $e^{-m2^{-r}}$. There are $2^N$ colourings, so choose
$$
m=\left\lceil(N\log2+1)2^r\right\rceil.
$$
A <union bound> makes the <probability> that any proper colouring exists at most $2^Ne^{-m2^{-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 $m$ distinct <hypergraph edges>. We have proved
$$
\boxed{\text{There is an }r\text{-uniform hypergraph without Property B with }O(r^22^r)\text{ edges}.}
$$
For $r=1$, one singleton <hypergraph edge> is already not two-colourable, so that endpoint causes no exception.
Back to article page
