#14131: Greene-Kleitman partition of a poset
---------------------------------------------+------------------------------
Reporter: darij | Owner: sage-combinat
Type: enhancement | Status: positive_review
Priority: minor | Milestone: sage-5.10
Component: combinatorics | Resolution:
Keywords: RSK, permutations, days45 | Work issues:
Report Upstream: N/A | Reviewers: Travis Scrimshaw
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
---------------------------------------------+------------------------------
Changes (by darij):
* status: needs_review => positive_review
Old description:
> The theory behind it is explained in Britz-Fomin, arXiv:9912126 (and
> briefly discussed in EC1, exercise 77 in chapter 3). It is a map
> associating to any poset P a partition \lambda(P) of |P|. For P being a
> permutation poset, this partition is the shape of the RSK tableaux of the
> permutation; the tableaux themselves can also be reconstructed by taking
> the sequences of \lambda(P_i) where P_i are the initial resp. final
> intervals of P.
>
> This functionality appears in Macaulay (
> http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.5/share/doc/Macaulay2/Posets/html/_greene__Kleitman__Partition.html
> ) but is apparently not exposed in Sage. I also don't like the Macaulay
> implementation, since (as far as I understand the sourcecode at
> http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.5/share/Macaulay2/Posets.m2
> ) it goes by brute force despite the existence of a polynomial-time
> algorithm.
>
> So I've implemented the algorithm given in Britz-Fomin.
>
> Apply:
> * [attachment:trac_14131-greene_shape_v2_conservative.2.patch]
> * [attachement:trac_14131-green_shape-review-ts.patch]
New description:
The theory behind it is explained in Britz-Fomin, arXiv:9912126 (and
briefly discussed in EC1, exercise 77 in chapter 3). It is a map
associating to any poset P a partition \lambda(P) of |P|. For P being a
permutation poset, this partition is the shape of the RSK tableaux of the
permutation; the tableaux themselves can also be reconstructed by taking
the sequences of \lambda(P_i) where P_i are the initial resp. final
intervals of P.
This functionality appears in Macaulay (
http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.5/share/doc/Macaulay2/Posets/html/_greene__Kleitman__Partition.html
) but is apparently not exposed in Sage. I also don't like the Macaulay
implementation, since (as far as I understand the sourcecode at
http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.5/share/Macaulay2/Posets.m2
) it goes by brute force despite the existence of a polynomial-time
algorithm.
So I've implemented the algorithm given in Britz-Fomin.
Apply:
* [attachment:trac_14131-greene_shape_v2_conservative.2.patch]
* [attachment:trac_14131-green_shape-review-ts.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14131#comment:22>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
