Property B


In mathematics, Property B is a certain set theoretic property. 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.
The property gets its name from mathematician Felix Bernstein, who first introduced the property in 1908.
Property B is equivalent to 2-coloring the hypergraph described by the collection C. A hypergraph with property B is also called 2-colorable. Sometimes it is also called bipartite, by analogy to the bipartite graphs.
Property B is often studied for uniform hypergraphs but it has also been considered in the non-uniform case.

Smallest set-families without property B

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.

Known values of m(n)

It is known that m = 1, m = 3, and m = 7 ; the value of m = 23, although finding this result was the result of an exhaustive search. An upper bound of 23 and a lower bound of 21 have been proven. At the time of this writing, there is no OEIS entry for the sequence m yet, due to the lack of terms known.
; m
; m
; m
; m

Asymptotics of ''m''(''n'')

Erdős proved that for any collection of fewer than sets of size n, there exists a 2-coloring in which all set are bichromatic. 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. Therefore, there exists a good coloring.
Erdős showed the existence of an n-uniform hypergraph with hyperedges which does not have property B, establishing an upper bound.
Schmidt proved that every collection of at most sets of size n has property B. Erdős and Lovász conjectured that. Beck in 1978 improved the lower bound to, where is an arbitrary small positive number. In 2000, Radhakrishnan and Srinivasan improved the lower bound to. They used a clever probabilistic algorithm.