Property B

In mathematics, Property B is a certain set theoretic property. Formally, given a finite set ${\displaystyle X}$, a collection ${\displaystyle C}$ of subsets of ${\displaystyle X}$ has Property B if we can partition ${\displaystyle X}$ into two disjoint subsets ${\displaystyle Y}$ and ${\displaystyle Z}$ such that every set in ${\displaystyle C}$ meets both ${\displaystyle Y}$ and ${\displaystyle 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 ${\displaystyle C}$. A hypergraph with property B is also called 2-colorable. Sometimes it is also called bipartite, by analogy to the bipartite graphs (see bipartite hypergraph). 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.

Some formulations use combinatorial designs, where the collection is a design, the sets are blocks, and the elements are points.

The problem of checking whether a collection ${\displaystyle C}$ has Property B is called the set splitting problem.