Greene-Kleitman partition of a poset

[darijgr]

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-greene_shape-review-ts.patch

CC: @nthiery @fchapoton

Component: combinatorics

Keywords: RSK, permutations, days45

Author: Darij Grinberg

Reviewer: Travis Scrimshaw

Merged: sage-5.10.beta5

Issue created by migration from https://trac.sagemath.org/ticket/14131

[darijgr]

greene_shape is the most important method here. The stuff after it is what I needed for checks; maybe it has its use too, but I wouldn't expect too much.

[darijgr]

comment:2

Attachment: greene.py.gz

Reuploaded fixed version, with docstrings and doctests.

I assume it should eventually be merged into Posets, with the functions becoming methods (umm, the ones that aren't useless to begin with). The ford_fulkerson_chronicle method should get an underscore in front of it (right now this would break the doctests).

[darijgr]

Attachment: posets.py.gz

posets.py. Should be diffed against devel/sage-main/sage/combinat/posets/posets.py as of 5.9.rc1

[darijgr]

comment:3

I have tried to make this into an actual patch but I need some help now. I somehow fucked up with hg mq, and the patch ended up empty. I don't have the old version of the file anymore, but I'm just using sage-main 5.9.rc1 (no other patches installed right now), so can anyone just diff the sage/combinat/posets/posets.py of that release against the posets.py I've uploaded and make the changes into a .patch?

Note that this will likely need manual merging with #14136 since both patches insert stuff at the same position; but there's no actual conflict.

As far as content is concerned, this contains the most important parts of greene.py with a couple bugfixes. The Greene-Kleitman partition of a poset is computed (in polynomial time). The doctests succeed, but I haven't tried compiling the doc (how does that work again?), so there might be formatting issues.

[darijgr]

comment:5

Attachment: trac_14131_greene_shape_v1.patch.gz

I've made this stuff into a patch [trac_14131_greene_shape_v1.patch] . Can anyone check if it applies correctly? (I am working from sage-main 5.9 rc1.) It might have a few stupid newline issues.

[tscrim]

comment:6

Hey I've uploaded a review patch which fixes up some of the documenation. The doc of _ford_fulkerson_chronicle will still need to be standardized following the conventions page.

As for the potential conflect with #14136, I was able to apply this after but has some fuzz. All that means is it will need a qrefresh to be run.

Also the first patch is missing a commit message. Let me know when these are done and I can give it another code review. I'd prefer if someone else (Frederic) can give this a math review.

Best,

Travis

[darijgr]

Attachment: trac_14131-greene_shape_v2.patch.gz

Updated file, replaces both mine and Travis's files so far

[darijgr]

comment:7

Thanks a lot for the comments, Travis!

I've uploaded a new patch [trac_14131-greene_shape_v2.patch], which contains both of our changes and a few more. I've standardized the docstring of the Ford-Fulkerson chronicle, though it wouldn't harm to check whether standardized really means standardized. I've also added a (very simple) method to permutations.py to compute the permutation poset of a permutation, and while being there fixed a couple typos in the RSK docs (the changeset isn't very informative, but what I've done is replacing some "right" by "left" in the doc).

I'm not sure what "fuzz" exactly means; is it something like "the line numbers have shifted, but it's kinda clear where the changes belong"?

I don't know how to add a commit message...

[fchapoton]

comment:8

to add a commit message, you can use

hg qrefresh - m "trac #14131 patch for doing really serious things"

or just

hg qrefresh -e

which will open a text editor

[tscrim]

comment:9

Then you'll also run

hg export trac_14131-greene_shape_v2.patch > /path/to/patch/trac_14131-greene_shape_v2.patch

Note that the export does not have to override the patch file, but you only would have to do it once if changes are subsequently made to the patch.

If you try to apply the one patch after the other, you should get something like "patch applied with fuzz 2 (offset 1 line)" or something like that. The fuzz is telling you somethings have moved, but it still applied.

Anyways, the doc looks much better but the inputs should be formatted in code with 2 backticks (see frank_network() for example).

I would prefer for this not to change the RSK docs since this will create a conflict with #8392 and is outside of the scope of this patch (same could be said of my changes to evacuation() and is_slender() [I believe that is what that function is called], but here the doc was more misformed). Also you'll need your real name in the Author section of the ticket, and we should make #14136 depend on this ticket because we need to sort out the doctest issue. Thanks.

[tscrim]

Reviewer: Travis Scrimshaw

[fchapoton]

comment:11

for the bot : apply trac_14131-greene_shape_v2.patch

[darijgr]

comment:12

Thank you @tscrim and Frédéric for the help with hg! Now I guess I've got the whole mq picture. A shame it's soon to be obsoleted...

There is one thing I don't understand: [Travis] "Note that the export does not have to override the patch file, but you only would have to do it once if changes are subsequently made to the patch." Do what once?

I deliberately used 1 backtick for the variables since their font should match the font in which they appear in later LaTeX formulae. Is this against some convention?

[darijgr]

Attachment: trac_14131-greene_shape_v2_conservative.patch.gz

Alternative version of v2, which should no longer conflict with Travis' RSK changes; UPDATE: BUG FIXED

[darijgr]

Attachment: trac_14131-greene_shape_v2_conservative.2.patch.gz

Alternative version of v2, which should no longer conflict with Travis' RSK changes; SECOND BUGFIX UPDATE!

[darijgr]

comment:13

New version uploaded: attachment: trac_14131-greene_shape_v2_conservative.2.patch. This differs from the one from 2 days ago in that RSK methods are no longer being edited, and I have even changed the insertion point so it shouldn't even be close to RSK. I have tested on 5.10beta2 that this doesn't conflict with #8392 in either order of patching. Oh and I also fixed a documentation bug (the :meth: declaration used a wrong method name), put inputs in double backticks the first time they appear, and added a commit message.

[tscrim]

Changed author from darij to Darij Grinberg

[tscrim]

comment:16

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,

Travis

[darijgr]

comment:17

Thank you for the review! There were some stupid doc blunders oops.

I agree with all of your changes except maybe two:

• You replaced range by xrange -- wasn't xrange supposed to be deprecated? (Do let me know what you think, as my other patches have the same situation at times.)

• I'd replace ``s`` -- the source vertex of `G` by ``s`` -- a vertex of `G`, to be used as the source vertex and similarly for t. This is to avoid the false impression that s needs to be a source in the sense of having no arrows going to s (that's not required).

[tscrim]

comment:18

I didn't know xrange was deprecated in python 3 (it might even be removed outright); I've changed it back. I've also tweaked those inputs around.

[darijgr]

comment:19

TBH I'm not sure if this is a good reason; I was just saying this is the reason why I chose range. Looking at the changes in Python 3.0 ( http://docs.python.org/3.1/whatsnew/3.0.html ), I suspect that most of our code is going to break if we ever switch to 3.0 (I am using None < 0 several times in my Bender-Knuth code, for example), so I am not sure whether to expect such a switch in the nearest time...

[nthiery]

comment:20

Replying to @darijgr:

TBH I'm not sure if this is a good reason; I was just saying this is the reason why I chose range. Looking at the changes in Python 3.0 ( http://docs.python.org/3.1/whatsnew/3.0.html ), I suspect that most of our code is going to break if we ever switch to 3.0 (I am using None < 0 several times in my Bender-Knuth code, for example), so I am not sure whether to expect such a switch in the nearest time...

I don't expect a switch in the short run. Yet I try to avoid using 2.0-only "features" without a compelling reason (but I certainly am unknowingly using some).

Cheers,
Nicolas

[tscrim]

comment:21

Hey Darij,

If you're happy with the latest review patch I've uploaded, you can set this to positive review.

Best,

Travis

[darijgr]

comment:23

Oops, of course! Yes, I'm happy with the review patch. But why are you suddenly making francophone typos? ("attachement")

[tscrim]

comment:24

...because I'm doing this on a keyboard I'm not used to? :P

[darijgr]

comment:26

Touché. :D

[jdemeyer]

comment:27

There is a problem with the documentation:

[combinat ] /mazur/release/merger/sage-5.10.beta5/local/lib/python2.7/site-packages/sage/combinat/posets/posets.py:docstring of sage.combinat.posets.posets:20: WARNING: Inline literal start-string without end-string.

[tscrim]

Attachment: trac_14131-greene_shape-review-ts.patch.gz

[tscrim]

comment:28

Fixed, small typo. Sorry about that.

[jdemeyer]

Merged: sage-5.10.beta5