The rank function is compatible with the ordering, meaning that for every x and y in the order with x < y, it must be the case that ρ < ρ, and
The rank is consistent with the covering relation of the ordering, meaning that for every x and y for which y covers x, it must be the case that ρ = ρ + 1.
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.
Examples
Some examples of graded posets are:
the natural numbers N, with their usual order, or some interval of this poset,
Nn, with the product order, or a subposet of it that is a product of intervals,
the positive integers, ordered by divisibility, or a subposet of it formed by the divisors of a fixed N,
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, 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. A graded poset cannot have any elements x for which arbitrarily longchains with greatest elementx exist, as otherwise it would have to have elements of arbitrarily small rank. For instance, the integers cannot be a graded poset, nor can any interval of rational or real numbers. Henceforth we shall therefore only consider posets in which this does not happen. This implies that whenever x < y we can get from x to y by repeatedly choosing a cover, finitely many times. It also means that compatibility of ρ with the ordering follows from the requirement about covers. As a variant of the definition of a graded poset, Birkhoff allows rank functions to have arbitrary integer values. In this variant, the integers can be graded in his setting, and the compatibility of ranks with the ordering is not redundant. As a third variant, Brightwell and West define a rank function to be integer-valued, but don't require its compatibility with the ordering; hence this variant can grade even e.g. the real numbers by any function, as the requirement about covers is vacuous for this example. Note that graded posets need not satisfy the ascending chain condition : for instance, the natural numbers contain the infinite ascending chain. A poset is graded if and only if every connected component of its comparability graph is graded, so further characterizations will suppose this comparability graph to be connected. On each connected component the rank function is only unique up to a uniform shift. If P has a least element Ô then being graded is equivalent to the condition that for any element x all maximal chains in the interval have the same length. This condition is necessary since every step in a maximal chain is a covering relation, which should change the rank by 1. The condition is also sufficient, since when it holds, one can use the mentioned length to define the rank of x, and whenever x covers y, adjoining x to a maximal chain in gives a maximal chain in . If P also has a greatest element Î, then the previous condition can be simplified to the requirement that all maximal chains in P have the same length. This suffices, since any pair of maximal chains in can be extended by a maximal chain in to give a pair of maximal chains in P.
The usual case
Many authors in combinatorics define graded posets in such a way that all minimal elements of P must have rank 0, and moreover that there is a maximal rank r that is the rank of any maximal element. Then being graded means that all maximal chains have length r, as is indicated above. In this case one says that P has rank r. Furthermore, in this case, to the rank levels are associated the rank numbers or Whitney numbers . These numbers are defined by = number of elements of P having rank i. The Whitney numbers are connected with a lot of important combinatorial theorems. The classic example is Sperner's theorem, which can be formulated as follows: This means:
