PartiallyOrderedSets
Height
returns the height of a poset
Calling Sequence
Parameters
Description
Examples
References
Compatibility
Height(P)
P
-
PartiallyOrderedSet
The command Height(P) returns the height of the partially ordered set P.
Remarks
Height will generate and store the transitive reduction of P.
The command will utilize the rank function of P if it has been generated.
Terminology
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, <=).
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.
An antichain decomposition of the poset (P, <=) is a partition of P into disjoint antichains. Mirsky's theorem states that the cardinality of a chain with maximum cardinality is equal to the cardinality of antichain decomposition of minimum cardinality. This common number is by definition the height of the poset (P, <=).
with⁡PartiallyOrderedSets:
divisibility≔x,y↦irem⁡y,x=0
leq≔`<=`:
Create a poset from a set and a non-strict partial order
S≔1,2,3,4,5:poset1≔PartiallyOrderedSet⁡S,leq
poset1≔< a poset with 5 elements >
Display this poset
DrawGraph⁡poset1
Compute the height of this poset
Height⁡poset1
5
Z≔1,2,3,4,5,6,10,12,15,20,30,60
poset10≔PartiallyOrderedSet⁡Z,divisibility
poset10≔< a poset with 12 elements >
DrawGraph⁡poset10
Height⁡poset10
ZZ≔1,2,3,4,5,6,12,15,60
poset11≔PartiallyOrderedSet⁡ZZ,divisibility
poset11≔< a poset with 9 elements >
DrawGraph⁡poset11
Height⁡poset11
Richard P. Stanley: Enumerative Combinatorics 1. 1997, Cambridge Studies in Advanced Mathematics. Vol. 49. Cambridge University Press.
The PartiallyOrderedSets[Height] command was introduced in Maple 2025.
For more information on Maple 2025 changes, see Updates in Maple 2025.
See Also
PartiallyOrderedSets[IsAntichain]
PartiallyOrderedSets[IsChain]
PartiallyOrderedSets[LessEqual]
PartiallyOrderedSets[MaximalAntichains]
PartiallyOrderedSets[MaximalChains]
PartiallyOrderedSets[PartiallyOrderedSet]
PartiallyOrderedSets[Width]
Download Help Document