Sperner property of a partially ordered set
Encyclopedia
In the order-theoretic mathematics
, a graded
partially ordered set
is said to have the Sperner property (and hence is called a Sperner poset), if no antichain
within it is larger than the largest rank level (the set 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. The Sperner property and Sperner posets are named after Emanuel Sperner
, who proved Sperner's theorem stating that the family of all subsets of a finite set (partially ordered by set inclusion) has this property.
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.
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, a graded
Graded poset
In mathematics, in the branch of combinatorics, a graded poset, sometimes called a ranked poset , is a partially ordered set P equipped with a rank function ρ from P to N compatible with the ordering such that whenever y covers x, then...
partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
is said to have the Sperner property (and hence is called a Sperner poset), if no antichain
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
within it is larger than the largest rank level (the set 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. The Sperner property and Sperner posets are named after Emanuel Sperner
Emanuel Sperner
Emanuel Sperner was a German mathematician, best known for two theorems. He was born in Waltdorf , and died in Sulzburg-Laufen, Germany. He was a student at Hamburg University where his advisor was Wilhelm Blaschke...
, who proved Sperner's theorem stating that the family of all subsets of a finite set (partially ordered by set inclusion) has this property.
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.