In
order-theoretic mathematics, a
graded partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
is said to have the Sperner property (and hence is called a Sperner poset), if no
antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.
The size of the largest antichain in a partially ordered set is known as its wid ...
within it is larger than the largest rank level (one of the sets of elements of the same rank) in the poset.
[.] Since every rank level is itself an antichain, the Sperner property is equivalently the property that some rank level is a maximum antichain.
[Handbook of discrete and combinatorial mathematics, by Kenneth H. Rosen, John G. Michaels]
/ref> The Sperner property and Sperner posets are named after Emanuel Sperner
Emanuel Sperner (9 December 1905 – 31 January 1980) was a German mathematician, best known for two theorems. He was born in Waltdorf (near Neiße, Upper Silesia, now Nysa, Poland), and died in Sulzburg-Laufen, West Germany. He was a student at ...
, who proved Sperner's theorem
Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who ...
stating that the family of all subsets of a finite set (partially ordered by set inclusion) has this property. The lattice of partitions of a finite set typically lacks the Sperner property.
Variations
A ''k''-Sperner poset is a graded poset in which no union of ''k'' antichains is larger than the union of the ''k'' largest rank levels,[ or, equivalently, the poset has a maximum k-family consisting of ''k'' rank levels.][
A strict Sperner poset is a graded poset in which all maximum antichains are rank levels.][
A strongly Sperner poset is a graded poset which is ''k-Sperner'' for all values of ''k'' up to the largest rank value.][
]
References
Order theory
{{combin-stub