Graded poset

Graded poset

In mathematics, a graded poset, sometimes called a ranked poset (but see the article for an alternative meaning), is a partially ordered set (poset) "P" equipped with a rank function ρ from "P" to N compatible with the ordering (so ρ("x")<ρ("y") whenever "x" < "y") such that whenever "y" covers "x", then ho(y)= ho(x)+1. Graded posets play an important role in combinatorics.

Alternative characterizations

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

:In some common posets such as the face lattice of a convex polytope there is a natural grading by dimension, which if used as rank function would give the minimal element, the empty face, rank –1. In such cases it might be convenient to bend the definition stated above by adjoining the value –1 to the set of values allowed for the rank function.

A poset containing elements "x" for which arbitrarily long chains with greatest element "x" exist (for instance the interval [0,1] of the real numbers) has no chance of being a graded poset. 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.

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

Examples

Some examples of graded posets (with in parentheses the rank function) are:
* the natural numbers N, with their usual order (rank: the number itself), or some interval [0,"N"] of this poset,
* N"n", with the product order (sum of the coefficients), or a subposet of it that is a product of intervals,
* the 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 (number of elements of the subset),
* the lattice of partitions of a set into finitely many parts, ordered by reverse refinement (number of parts),
* the lattice of partitions of a finite set "X", ordered by refinement (number of elements of "X" minus number of parts),
* permutations of a totally ordered "n"-element set, with either the weak or strong Bruhat order (number of inversions),
* geometric lattices, such as the lattice of subspaces of a vector space (dimension of the subspace),
* the distributive lattice of finite lower sets of another poset (number of elements),
* Young's lattice, a particular instance of the previous example (number of boxes in the Young diagram),
* face lattices of convex polytopes (dimension of the face, plus one),
* face lattices of abstract polytopes (dimension of the face, plus one),
* abstract simplicial complexes (number of elements of the simplex).

References

*Richard Stanley, "Enumerative Combinatorics," vol.1, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, 1997, ISBN 0-521-66351-2


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Ranked poset — In mathematics, a ranked partially ordered set (or poset) may be either:* a graded poset, or * a poset that has the property that for every element x , all maximal chains among those with x as greatest element have the same finite length, or * a… …   Wikipedia

  • Partially ordered set — The Hasse diagram of the set of all subsets of a three element set {x, y, z}, ordered by inclusion. In mathematics, especially order theory, a partially ordered set (or poset) formalizes and generalizes the intuitive concept of an ordering,… …   Wikipedia

  • Nilpotent orbit — Nilpotent orbits are generalizations of nilpotent matrices that play an important role in representation theory of real and complex semisimple Lie groups and semisimple Lie algebras. Contents 1 Definition 2 Examples 3 Properties …   Wikipedia

  • Abstract polytope — In mathematics, an abstract polytope is a combinatorial structure with properties similar to those shared by a more classical polytope. Abstract polytopes correspond to the structures of polygons, polyhedra, tessellations of the plane and higher… …   Wikipedia

  • Star product — In mathematics, the star product of two graded posets (P,le P) and (Q,le Q), where P has a unique maximal element widehat{1} and Q has a unique minimal element widehat{0}, is a poset P*Q on the set (Psetminuswidehat{1})cup(Qsetminuswidehat{0}).… …   Wikipedia

  • Characteristic polynomial — This article is about the characteristic polynomial of a matrix. For the characteristic polynomial of a matroid, see Matroid. For that of a graded poset, see Graded poset. In linear algebra, one associates a polynomial to every square matrix: its …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Coxeter group — In mathematics, a Coxeter group, named after H.S.M. Coxeter, is an abstract group that admits a formal description in terms of mirror symmetries. Indeed, the finite Coxeter groups are precisely the finite Euclidean reflection groups; the symmetry …   Wikipedia

  • Lattice (order) — See also: Lattice (group) The name lattice is suggested by the form of the Hasse diagram depicting it. Shown here is the lattice of partitions of a four element set {1,2,3,4}, ordered by the relation is a refinement of . In mathematics, a… …   Wikipedia

  • Outline of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”