Graded poset

Some examples of graded posets (with the rank function in parentheses) are: • Natural numbers N with their usual order (rank: the number itself), or some interval [0, N] of this poset • Nn with the product order (sum of the components), or a subposet of it that is a product of intervals • Positive integers ordered by divisibility (number of prime factors, counted with multiplicity), or a subposet of it formed by the divisors of a fixed N • The Boolean lattice of finite subsets of a set ordered by inclusion (number of elements of the subset) • Any distributive lattice of finite lower sets of another poset (number of elements) • In particular any finite distributive lattice • Poset of all unlabeled posets on \{1,...,n\} (number of elements) • Young's lattice (number of boxes in the Young diagram) • Any geometric lattice, such as the lattice of subspaces of a vector space (dimension of the subspace) • Lattice of partitions of a set into finitely many parts, ordered by reverse refinement (number of parts) • Lattice of partitions of a finite set X, ordered by refinement (number of elements of X minus number of parts) • Face lattice of convex polytopes (dimension of the face, plus one) • Abstract polytope ("distance" from the least face, minus one) • Abstract simplicial complex (number of elements of the simplex) • A group with a generating set, or equivalently its Cayley graph, ordered by the weak or strong Bruhat order, and ranked by word length (length of shortest reduced word) • In particular a Coxeter group, for example permutations of a totally ordered n-element set, with either the weak or strong Bruhat order (number of adjacent inversions) == Alternative characterizations ==

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 0 . 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 (so the rank function can always be chosen so that the elements of minimal rank in their connected component have rank 0). 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 [Ô, x] 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 (the length of a finite chain is its number of "steps", so one less than its number of elements), and whenever x covers y, adjoining x to a maximal chain in [Ô, y] gives a maximal chain in [Ô, x]. If P also has a greatest element Î (so that it is a bounded poset), then the previous condition can be simplified to the requirement that all maximal chains in P have the same (finite) length. This suffices, since any pair of maximal chains in [Ô, x] can be extended by a maximal chain in [x, Î] to give a pair of maximal chains in P. :Note Stanley defines a poset to be graded of length n if all its maximal chains have length n (Stanley 1997, p.99). This definition is given in a context where interest is mostly in finite posets, and although the book subsequently often drops the part "of length n", it does not seem appropriate to use this as definition of "graded" for general posets, because (1) it says nothing about posets whose maximal chains are infinite, in particular (2) it excludes important posets like Young's lattice. Also it is not clear why in a graded poset all minimal elements, as well as all maximal elements, should be required to have the same length, even if Stanley gives examples making clear that he does mean to require that (ibid, pp.216 and 219). == 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 W_0,W_1,W_2,... . These numbers are defined by 'W_i = 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: == See also ==