Graded poset
In
- The rank function is compatible with the ordering, meaning that for all x and y in the order, if x < y then ρ(x) < ρ(y), and
- The rank is consistent with the covering relation of the ordering, meaning that for all x and y, if y covers x then ρ(y) = ρ(x) + 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.[1][2]
Graded posets play an important role in combinatorics and can be visualized by means of a Hasse diagram.
Examples
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 latticeof finite subsets of a set ordered by inclusion (number of elements of the subset)
- Any lower setsof another poset (number of elements)
- In particular any finite distributive lattice
- Poset of all unlabeled posets on (number of elements)[3]
- 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 partitionsof a set into finitely many parts, ordered by reverse refinement (number of parts)
- Lattice of partitionsof 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
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
In some common posets such as the
A graded poset (with positive integer ranks) cannot have any elements x for which arbitrarily long
Note that graded posets need not satisfy the ascending chain condition (ACC): 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 (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
If P also has a
- 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
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:
For the power set of every finite set the maximum
maximumWhitney number.
This means:
Every finite power set has the Sperner property
See also
- Graded (mathematics)
- Prewellordering – a prewellordering with a norm is analogous to a graded poset, replacing a map to the integers with a map to the ordinals
- Star product, a method for combining two graded posets
Notes
- S2CID 14857863.
- ISBN 9780821826003.
- S2CID 120473635
- greatest element.
- ^ I.e., one does not have a situation like and both being maximal chains.
- ^ Not containing arbitrarily long descending chains starting at a fixed element of course excludes any infinite descending chains. The former condition is strictly stronger though; the set has arbitrarily long chains descending from , but has no infinite descending chains.
- ^ 'Lattice Theory', Am. Math. Soc., Colloquium Publications, Vol.25, 1967, p.5
- ^ See reference [2], p.722.
References
- ISBN 0-521-66351-2.
- Anderson, Ian (1987). Combinatorics of Finite Sets. Oxford, UK: ISBN 0-19-853367-5.
- Engel, Konrad (1997). Sperner Theory. Cambridge, UK (et al.): Cambridge University Press. ISBN 0-521-45206-6.
- Kung, Joseph P. S.; ISBN 978-0-521-73794-4.