Property B

A 2-coloring of a hypergraph, equivalent to a collection C with 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.Template:Sfnp

Property B is equivalent to 2-coloring the hypergraph described by the collection $C$. A hypergraph with property B is also called 2-colorable.Template:Sfnp 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.Template:Sfnp

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

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

Smallest collections without property B

The Steiner triple system $S_7$, the smallest 3-uniform collection that doesn't have 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(n)$.

Small values of m(n)

For $n=1,2,3,4$:

$m(n)=1,3,7,23$  Template:OEIS

$m(1)=1$:
For $n=1$, set $X=\{1\}$, and $C=\{\{1\}\}$. Then $C$ does not have Property B.

$m(2)=3$:
For $n=1$, set $X=\{1,2,3\}$ and $C=\{\{1,2\},\{1,3\},\{2,3\}\}$ (a triangle). Then $C$ does not have Property B, so $m(2)\le 3$. However, for $C^{\prime }=\{\{1,2\},\{1,3\}\}$, $X$ has a partition into sets $Y=\{1\}$ and $Z=\{2,3\}$, so $m(2)\ge 3$.

$m(3)=7$:
For $n=3$, set $X=\{1,2,3,4,5,6,7\}$, and $C=\{\{1,2,4\},\{2,3,5\},\{3,4,6\},\{4,5,7\},\{5,6,1\},\{6,7,2\},\{7,1,3\}\}$ (the Steiner triple system $S_7$), $C$ does not have Property B (so $m(3)\le 7$), but if any element of $C$ is omitted, then that element can be taken as $Y$, and the set of remaining elements $C^{\prime }$ will have Property B (so for this particular case, $m(3)\ge 7$). One may check all other collections of 6 3-sets to see that all have Property B.

$m(4)=23$:
Östergård (2014)Template:Sfnp through an exhaustive search found $m(4)=23$. Before, Seymour (1974)Template:Sfnp constructed a hypergraph on 11 vertices with 23 edges without Property B, showing that $m(4)\le 23$, and Manning in 1995Template:Sfnp had narrowed the floor such that $m(4)\ge 20$, then to $m(4)\ge 21$ in 1997.Template:Sfnp

$29\le m(5)\le 51$:
The bounds for even the next unknown value are quite far apart. On the lower end, only collections with certain numbers of unique elements could potentially not have Property B, but this range grows larger further from the lower bound. The lower bound was improved from 28 to 29 in 2020.Template:Sfnp

Asymptotics of m(n)

Erdős (1963)Template:Sfnp proved that for any collection of fewer than $2^{n-1}$ sets of size $n$, there exists a 2-coloring in which all sets are bichromatic. The proof is simple: Consider a random coloring. The probability that an arbitrary set is monochromatic is $2^{-n+1}$. By a union bound, the probability that there exist a monochromatic set is less than $2^{n-1}{2}^{-n+1}=1$. Therefore, there exists a good coloring.

Erdős (1964)Template:Sfnp showed the existence of an $n$-uniform hypergraph with $O(2^n\cdot n^2)$ hyperedges which does not have property B (i.e., does not have a 2-coloring in which all hyperedges are bichromatic), establishing an upper bound.

Schmidt (1964)Template:Sfnp proved that every collection of at most $n/(n+4)\cdot 2^n$ sets of size n has property B. Erdős and Lovász conjectured that $m(n)=\theta (2^n\cdot n)$. Beck in 1978Template:Sfnp improved the lower bound to $m(n)=\mathrm{\Omega }(n^{1/3-ϵ}{2}^n)$, where $ϵ$ is an arbitrary small positive number. In 2000,Template:Sfnp Radhakrishnan and Srinivasan improved the lower bound to $m(n)=\mathrm{\Omega }(2^n\cdot \sqrt{n/\log n})$ using a probabilistic algorithm.

Other partial results

For a design without Property B, merging any pair of points not occurring in any block of the design creates another design without Property B. The search may thus be restricted to designs that cover all pairs of points, known as covering designs.Template:Sfnp

See also

• Template:Slink
• Set splitting problem

References

• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Cite journal
• Template:Cite journal
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Cite journal
• Template:Cite journal