Online Help

Rank will generate and store the transitive reduction of P.

The rank function will be generated and stored if P is graded.

A partially ordered set, or poset for short, is a pair (P, <=) where P is a set and <= is a partial order on P.

From now on, we fix a poset (P, <=). Two elements a and b of P are said comparable if either a <= b or b <= a holds, otherwise a and b are said incomparable.

A subset C of P is called a chain if any two elements of C are comparable. A chain C of P is said maximal if P does not admit another chain D of which C would be a proper subset.

A subset C of P is called an antichain if any two distinct elements of C are incomparable. An antichain C of P is said maximal if P does not admit another antichain D of which C would be a proper subset. We note that any singleton of P is both a chain and an antichain.

The element a of P is strictly less than the element b of P if a <= b and a 342円211円240円 b both hold.

The element b of Pcovers the element a of P if a is strictly less than b and for no element c of P, distinct from both a and b, both a <= c and c <= b hold.

Let S be a subset of P and a be an element of S. We say that a is a greatest element (resp. least element) of S if for every element b of S we have b <= a (resp. a <= b). Observe that if S has a greatest element (resp. least element) then it is unique.

We say that a is an upper bound (resp. lower bound) of S if if for every element b of S we have b <= a (resp. a <= b). Observe that a need not be in S in order to be an upper bound (resp. lower bound) of S.

We say that a is the infimum of S, or the greatest lower bound of S, if a is the greatest element among all lower bounds of S.

We say that a is the supremum of S, or the lest upper bound of S, if a is the least element among all upper bounds of S.

From now on, we assume that P is finite.

We call rank function on the poset (P, <=) any function r defined on P, taking integer values and so that for any two elements a and b of P, if b covers a then r(b) = r(a) + 1 holds.

The poset (P, <=) is said graded if it admits a rank function.

The poset (P, <=) is said ranked if all its maximal chains have the same cardinality.

We note that the terms graded poset and ranked poset have slightly different definitions in some textbooks, like the ones of Richard Stanley. We refer to the wikipedia pages of ranked poset and graded poset for a discussion on these terminology issues.