**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Property B

Summary

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 (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.
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).
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 entry for the sequence m(n) yet, due to the lack of terms known.
m(1)
For n = 1, set X = {1}, and C = {{1}}. Then C does not have Property B.
m(2)
For n = 2, 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) = 7).

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related MOOCs

Loading

Related people

Related concepts

Related lectures

Related MOOCs

No results

Related publications

Related units

Related courses

No results

No results

No results

No results

No results

No results