# greeneKleitmanPartition -- computes the Greene-Kleitman partition of a poset

## Synopsis

• Usage:
l = greeneKleitmanPartition P
l = greeneKleitmanPartition(P, Strategy => "chains")
l = greeneKleitmanPartition(P, Strategy => "antichains")
• Inputs:
• P, an instance of the type Poset,
• Optional inputs:
• Strategy => , default value antichains, either "chains" or "antichains"
• Outputs:
• l, an instance of the type Partition, the Greene-Kleitman partition of $P$

## Description

The Greene-Kleitman partition $l$ of $P$ is the partition such that the sum of the first $k$ parts of $l$ is the maximum number of elements in a union of $k$ chains in $P$.

 i1 : P = poset {{1,2},{2,3},{3,4},{2,5},{6,3}}; i2 : greeneKleitmanPartition P o2 = Partition{4, 2} o2 : Partition

The conjugate of $l$ has the same property, but with chains replaced by antichains. Because of this, it is often better to count via antichains instead of chains. This can be done by passing "antichains" as the Strategy.

 i3 : D = dominanceLattice 6; i4 : time greeneKleitmanPartition(D, Strategy => "antichains") -- used 0.231914 seconds o4 = Partition{9, 2} o4 : Partition i5 : time greeneKleitmanPartition(D, Strategy => "chains") -- used 0.00001295 seconds o5 = Partition{9, 2} o5 : Partition

The Greene-Kleitman partition of the $n$ chain is the partition of $n$ with $1$ part.

 i6 : greeneKleitmanPartition chain 10 o6 = Partition{10} o6 : Partition

## See also

• chains -- computes all chains of a poset
• antichains -- computes all antichains of a poset

## Ways to use greeneKleitmanPartition :

• "greeneKleitmanPartition(Poset)"

## For the programmer

The object greeneKleitmanPartition is .