Property B

Formally, given a finite set X, a collection C of subsets of X has Property B if we can partition X into two disjoint subsets Y and Z such that every set in C meets both Y and Z.

[1] Property B is equivalent to 2-coloring the hypergraph described by the collection C. A hypergraph with property B is also called 2-colorable.

Property B is often studied for uniform hypergraphs (set systems in which all subsets of the system have the same cardinality) but it has also been considered in the non-uniform case.

[3] The problem of checking whether a collection C has Property B is called the set splitting problem.

The smallest number of sets in a collection of sets of size n such that C does not have Property B is denoted by m(n).

An upper bound of 23 (Seymour, Toft) and a lower bound of 21 (Manning) have been proven.

At the time of this writing (March 2017), there is no OEIS entry for the sequence m(n) yet, due to the lack of terms known.

Erdős (1963) proved that for any collection of fewer than

The proof is simple: Consider a random coloring.

The probability that an arbitrary set is monochromatic is

By a union bound, the probability that there exist a monochromatic set is less than

Erdős (1964) showed the existence of an n-uniform hypergraph with

sets of size n has property B. Erdős and Lovász conjectured that

Beck in 1978 improved the lower bound to

is an arbitrary small positive number.

In 2000, Radhakrishnan and Srinivasan improved the lower bound to