Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Propriété B
Résumé
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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.