graded poset
A graded poset is a poset P that is equipped with a rank function ρ, which is a function from P to ℤ, satisfying the following three conditions:
-
1.
ρ is constant on all minimal elements of P, usually with value -1 or 0
-
2.
ρ is isotone, that is, if a≤b, then ρ(a)≤ρ(b), and
-
3.
ρ preserves covering relations: if a≺b, then ρ(a)+1=ρ(b).
Equivalently, a poset P is graded if it admits a partition into maximal antichains {An∣n∈ℕ} such that for each x∈An, all of the elements covering x are in An+1 and all the elements covered by x are in An-1.
A poset P can be graded if one can define a rank function ρ on P so (P,ρ) is a graded poset. Below is a poset that can not be graded:
\entrymodifiers=[o]\xymatrix@!=1pt&&∘\ar@-[ld]\ar@-[rd]&&\ar@-[ld]&&∘\ar@-[d]∘\ar@-[rd]&&&\ar@-[d]&\ar@-[rd]&&∘\ar@-[ld]&&∘& |
Generalized rank functions
Since certain common posets such as the face lattice of a polytope are most naturally graded by dimension (http://planetmath.org/Dimension2), the rank of a minimal element is sometimes required to be -1.
More generally, given a chain C, one can define C-graded posets. A poset P is C-graded provided that there is a poset map ρ:P→C that preserves covers and is constant on minimal elements of P. Such a rank function is unique up to choice of the rank of minimal elements. In practice, however, the term graded is only used to indicate ℕ-grading, ℕ∪{-1}-grading, or ℤ-grading.
Maximal chains in graded posets
Let P be a graded poset with rank function ρ. A chain C in P is said to be a saturated chain provided that ρ(C)=ρ(P). If C is saturated in P, then each cover relation in C is also a cover relation in P; thus a saturated chain is also a maximal chain.
It is a property of graded posets that all saturated chains have the same cardinality. As a partial converse, if P is a finite bounded poset (http://planetmath.org/BoundedLattice) and each maximal chain has the same cardinality, then P is graded.
Title | graded poset |
Canonical name | GradedPoset |
Date of creation | 2013-03-22 14:09:12 |
Last modified on | 2013-03-22 14:09:12 |
Owner | mps (409) |
Last modified by | mps (409) |
Numerical id | 9 |
Author | mps (409) |
Entry type | Definition |
Classification | msc 06A06 |
Classification | msc 05B35 |
Related topic | EulerianPoset |
Related topic | StarProduct |
Related topic | HeightOfAnElementInAPoset |
Defines | rank function |
Defines | saturated chain |