PartiallyOrderedSets/Height - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : PartiallyOrderedSets/Height

PartiallyOrderedSets

  

Height

  

returns the height of a poset

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

Calling Sequence

Height(P)

Parameters

P

-

PartiallyOrderedSet

Description

• 

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

Examples

withPartiallyOrderedSets&colon;

divisibilityx&comma;yiremy&comma;x=0

divisibilityx&comma;yiremy&comma;x=0

(1)

leq`<=`&colon;

Create a poset from a set and a non-strict partial order

S1&comma;2&comma;3&comma;4&comma;5&colon;poset1PartiallyOrderedSetS&comma;leq

poset1< a poset with 5 elements >

(2)

Display this poset

DrawGraphposet1

Compute the height of this poset

Heightposet1

5

(3)

 

Create a poset from a set and a non-strict partial order

Z1&comma;2&comma;3&comma;4&comma;5&comma;6&comma;10&comma;12&comma;15&comma;20&comma;30&comma;60

Z1&comma;2&comma;3&comma;4&comma;5&comma;6&comma;10&comma;12&comma;15&comma;20&comma;30&comma;60

(4)

poset10PartiallyOrderedSetZ&comma;divisibility

poset10< a poset with 12 elements >

(5)

Display this poset

DrawGraphposet10

Compute the height of this poset

Heightposet10

5

(6)

Create a poset from a set and a non-strict partial order

ZZ1&comma;2&comma;3&comma;4&comma;5&comma;6&comma;12&comma;15&comma;60

ZZ1&comma;2&comma;3&comma;4&comma;5&comma;6&comma;12&comma;15&comma;60

(7)

poset11PartiallyOrderedSetZZ&comma;divisibility

poset11< a poset with 9 elements >

(8)

Display this poset

DrawGraphposet11

Compute the height of this poset

Heightposet11

5

(9)

References

  

Richard P. Stanley: Enumerative Combinatorics 1. 1997, Cambridge Studies in Advanced Mathematics. Vol. 49. Cambridge University Press.

Compatibility

• 

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]