In
mathematics, Property B is a certain
set theoretic property. Formally, given a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
''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
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) w ...
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 (set systems in which all subsets of the system have the same cardinality) but it has also been considered in the non-uniform case.
The problem of checking whether a collection ''C'' has Property B is called the
set splitting problem.
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''(''n'').
Known values of m(n)
It is known that ''m''(1) = 1, ''m''(2) = 3, and ''m''(3) = 7 (as can by seen by the following examples); the value of ''m''(4) = 23 (Östergård), although finding this result was the result of an exhaustive search. 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
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
entry for the sequence ''m''(''n'') yet, due to the lack of terms known.
; ''m''(1)
: For ''n'' = 1, set ''X'' = , and ''C'' =
. Then C does not have Property B.
; ''m''(2)
: For ''n'' = 2, set ''X'' = and ''C'' =
(a triangle). Then C does not have Property B, so ''m''(2) <= 3. However, ''C''
' = does (set ''Y'' = and ''Z'' = ), so ''m''(2) >= 3.
; ''m''(3)
: For ''n'' = 3, set ''X'' = , and ''C'' = (the
Steiner triple system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...
''S''
7); ''C'' does not have Property B (so ''m''(3) <= 7), but if any element of ''C'' is omitted, then that element can be taken as ''Y'', and the set of remaining elements ''C''
' will have Property B (so for this particular case, ''m''(3) >= 7). One may check all other collections of 6 3-sets to see that all have Property B.
; ''m''(4)
: Östergård (2014) through an exhaustive search found ''m''(4) = 23. Seymour (1974) constructed a hypergraph on 11 vertices with 23 edges without Property B, which shows that ''m''(4) <= 23. Manning (1995) narrowed the floor such that ''m''(4) >= 21.
Asymptotics of ''m''(''n'')
Erdős (1963) 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 (1964) showed the existence of an ''n''-uniform hypergraph with
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 (1963) 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.
See also
*
*
Set splitting problem
References
Further reading
*
*
*
*.
*.
*.
*.
*.
*.
*.
*
*{{cite journal, ref=none, last1=Östergård, first1=Patric R. J., title=On the minimum size of 4-uniform hypergraphs without property B, journal=Discrete Applied Mathematics, date=30 January 2014, volume=163, Part 2, pages=199–204, doi=10.1016/j.dam.2011.11.035, doi-access=free
Families of sets
Hypergraphs