Wikipedia / Property B
Wikipedia / Property B
In mathematics, Property B is a certain set theoretic property. Formally, given a finite set of subsets.
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. 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.
has Property B is called the set splitting problem.
Smallest collections without property B
.
Small values of m(n)
:
m(n) = 1, 3, 7, 23 A392185: does not have Property B.
: .
: (the Steiner triple system). One may check all other collections of 6 3-sets to see that all have Property B.
: Östergård (2014). Before, Seymour (1974), and Manning in 1995 in 1997.
: 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.
Asymptotics of m(n)
Erdős (1963). By a union bound. Therefore, there exists a good coloring.
Erdős (1964) 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) sets of size n. Beck in 1978 is an arbitrary small positive number. In 2000, 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.
See also
Notes
References
.
.
.
.
.
.
.
.