= Property B
{wiki}
A <hypergraph> has <Property B> if its <vertices of a hypergraph> can be coloured with two colours so that every <hypergraph edge> meets both <colour classes>. An $r$-<uniform hypergraph> with fewer than $2^{r-1}$ <edges> has <Property B>, by a fair <independent> colouring and the <union bound>. Conversely, for $r\geq2$, take $N=2r^2$ vertices and independently sample $m=\lceil(N\log2+1)2^r\rceil$ uniformly random $r$-subsets. In any fixed colouring an <edge> is <monochromatic> with <probability> at least $2^{-r}$: <convexity> of <binomial coefficients> reduces to the balanced colouring, and $\binom{r^2}{r}/\binom{2r^2}{r}\geq2^{-r-1}$. The <union bound> over $2^N$ colourings gives a <probability> at most $2^N e^{-m2^{-r}}<1$ of any proper colouring. Removing repeated <edges> leaves a <hypergraph> without <Property B> and with $O(r^22^r)$ <edges>.
Back to article page
