Ê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 Graph Search.
Concept
Famille de Sperner
Résumé
In combinatorics, a Sperner family (or Sperner system; named in honor of Emanuel Sperner), or clutter, is a family F of subsets of a finite set E in which none of the sets contains another. Equivalently, a Sperner family is an antichain in the inclusion lattice over the power set of E. A Sperner family is also sometimes called an independent system or irredundant set.
Sperner families are counted by the Dedekind numbers, and their size is bounded by Sperner's theorem and the Lubell–Yamamoto–Meshalkin inequality. They may also be described in the language of hypergraphs rather than set families, where they are called clutters.
Dedekind number
The number of different Sperner families on a set of n elements is counted by the Dedekind numbers, the first few of which are
2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 .
Although accurate asymptotic estimates are known for larger values of n, it is unknown whether there exists an exact formula that can be used to compute these numbers efficiently.
The collection of all Sperner families on a set of n elements can be organized as a free distributive lattice, in which the join of two Sperner families is obtained from the union of the two families by removing sets that are a superset of another set in the union.
Sperner's theorem
The k-element subsets of an n-element set form a Sperner family, the size of which is maximized when k = n/2 (or the nearest integer to it).
Sperner's theorem states that these families are the largest possible Sperner families over an n-element set. Formally, the theorem states that, for every Sperner family S over an n-element set,
Lubell–Yamamoto–Meshalkin inequality
The Lubell–Yamamoto–Meshalkin inequality provides another bound on the size of a Sperner family, and can be used to prove Sperner's theorem.
It states that, if ak denotes the number of sets of size k in a Sperner family over a set of n elements, then
A clutter is a family of subsets of a finite set such that none contains any other; that is, it is a Sperner family.
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.