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 object of class Poset
Optional inputs:
- Strategy => a string, default value antichains, either "chains" or "antichains"
Outputs:
- l, an object of class 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.139965 seconds

o4 = Partition{9, 2}

o4 : Partition

i5 : time greeneKleitmanPartition(D, Strategy => "chains")
     -- used 0.000010755 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

Ways to use `greeneKleitmanPartition` :

greeneKleitmanPartition(Poset)

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

Synopsis

Description

See also

Ways to use greeneKleitmanPartition :

Ways to use `greeneKleitmanPartition` :