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

Usage:

l = greeneKleitmanPartition P

l = greeneKleitmanPartition(P, Strategy => "auto")

l = greeneKleitmanPartition(P, Strategy => "chains")

l = greeneKleitmanPartition(P, Strategy => "antichains")

l = greeneKleitmanPartition(P, Strategy => "Britz-Fomin")
Inputs:
- P, an instance of the type Poset,
Optional inputs:
- Strategy => a string, default value "auto", one of "auto", "chains", "antichains", or "Britz-Fomin"
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.542966s (cpu); 0.333941s (thread); 0s (gc)

o4 = Partition{9, 2}

o4 : Partition

i5 : time greeneKleitmanPartition(D, Strategy => "chains")
 -- used 2.0168e-05s (cpu); 1.9256e-05s (thread); 0s (gc)

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

When the Strategy is "auto", for small posets, the strategies "chains" and "antichains" are used as a brute force search is performed. For larger posets, a max-flow computation is performed according to [BF01].

References

[BF01] Thomas Britz and Sergey Fomin, Finite Posets and Ferrer Shapes, Adv. Math., 158.1 (2001), pp. 86-127.

Ways to use greeneKleitmanPartition:

greeneKleitmanPartition(Poset)

For the programmer

The object greeneKleitmanPartition is a method function with options.

The source of this document is in /build/reproducible-path/macaulay2-1.26.05+ds/M2/Macaulay2/packages/Posets.m2:5246:0.

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

Description

References

See also

Ways to use greeneKleitmanPartition:

For the programmer