#14131: Greene-Kleitman partition of a poset
---------------------------------------------+------------------------------
Reporter: darij | Owner: sage-combinat
Type: enhancement | Status: needs_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 {'newvalue': u'Darij Grinberg', 'oldvalue': u'darij'}):
* author: darij => Darij Grinberg
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. I'm not doing
> this as a patch, because I believe the Posets file is currently being
> worked on and this is likely to require manual merging (also, I am not
> currently using sage-combinat).
>
> Apply:
> * [attachment:trac_14131-greene_shape_v2_conservative.2.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]
* [attachement:trac_14131-green_shape-review-ts.patch]
--
Comment:
I've uploaded a new (version) review patch which makes some changes to the
doc. If you agree with my changes, you can set this to positive review.
Also thanks for separating off the RSK changes.
Best,[[BR]]
Travis
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14131#comment:16>
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.
