Graded poset

In mathematics, in the branch of combinatorics, a graded poset is a partially ordered set (poset) P equipped with a rank function ρ from P to N satisfying the following two properties:

The value of the rank function for an element of the poset is called its rank. Sometimes a graded poset is called a ranked poset but that phrase has other meanings; see ranked poset. A rank or rank level of a graded poset is the subset of all the elements of the poset that have a given rank value.

Graded posets play an important role in combinatorics and can be visualized by means of a Hasse diagram.

Some examples of graded posets (with the rank function in parentheses) are:

A bounded poset admits a grading if and only if all maximal chains in P have the same length: setting the rank of the least element to 0 then determines the rank function completely. This covers many finite cases of interest; see picture for a negative example. However, unbounded posets can be more complicated.

A candidate rank function, compatible with the ordering, makes a poset into graded poset if and only if, whenever one has x < z with z of rank n+1, an element y of rank n can be found with x ≤ y < z. This condition is sufficient because if z is taken to be a cover of x, the only possible choice is y = x showing that the ranks of x and z differ by 1, and it is necessary because in a graded poset one can take for y any element of maximal rank with x ≤ y < z, which always exists and is covered by z.

Often a poset comes with a natural candidate for a rank function; for instance if its elements are finite subsets of some base set B, one can take the number of elements of those subsets. Then the criterion just given can be more practical than the definition because it avoids mention of covers. For instance if B is itself a poset, and P consists of its finite lower sets (subsets for which with every one of its elements, all smaller elements are also in the subset), then the criterion is automatically satisfied, since for lower sets x ⊂ z there is always a maximal element of z that is absent from x, and it can be removed from z to form y.

...
Wikipedia