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. 1.

    ρ is constant on all minimal elements of P, usually with value -1 or 0

  2. 2.

    ρ is isotone, that is, if ab, then ρ(a)ρ(b), and

  3. 3.

    ρ preserves covering relations: if ab, then ρ(a)+1=ρ(b).

Equivalently, a poset P is graded if it admits a partitionMathworldPlanetmathPlanetmath into maximal antichains {Ann} such that for each xAn, 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 latticeMathworldPlanetmath of a polytope are most naturally graded by dimensionPlanetmathPlanetmath (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 ρ:PC 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 saturatedPlanetmathPlanetmath 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 converseMathworldPlanetmath, 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