coRSK algorithm

[darijgr]

Implement the dual RSK and coRSK algorithms from {0, 1}-matrices.

Depends on #27852

CC: @sagetrac-troby @tscrim

Component: combinatorics

Keywords: gsocRSK, IMA coding sprint, tableaux, permutations, fpsac2019

Author: Darij Grinberg, Tom Roby, Chaman Agrawal

Branch/Commit: 739aa17

Reviewer: Darij Grinberg, Travis Scrimshaw

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

[sagetrac-git]

Commit: 224b9f1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

53c10cc	add dual RSK
224b9f1	implement dual RSK (just needs examples)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

49ea704

implement dual RSK (just needs examples)

[sagetrac-git]

Changed commit from 224b9f1 to 49ea704

[sagetrac-git]

Changed commit from 49ea704 to 07a5577

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

07a5577

Filled in a couple of missing examples.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

caf09d3

fill in all doctests

[sagetrac-git]

Changed commit from 07a5577 to caf09d3

[tscrim]

Changed branch from public/combinat/dualRSK to public/combinat/dualRSK_alt-25070

[tscrim]

comment:5

My attempt at a version which blends dual RSK together with RSK. Note the changes are relatively minimal.

---

New commits:

b8e89f3

Blend the dual RSK with RSK.

[tscrim]

Changed commit from caf09d3 to b8e89f3

[mantepse]

comment:6

Note to myself that (additionally!) adding dual RSK to growth.py is very easy. It amounts to coding F^2 and B^2 on page 18 http://www.mat.univie.ac.at/~kratt/artikel/growth.html. This should essentially be a copy-paste job, because F^1 (as RuleRSK.forward_rule) and F^4 (as RuleBurge.forward_rule) are already implemented.

Although this should be done, the proper solution would be #24659, which unfortunately turns out to be tricky.

[ChamanAgrawal]

comment:7

Hi,
I am working on dualRSK and coRSK as part of my GSoC project(Ticket #28058). I have already migrated dualRSK but I am not able to find any reference for coRSK. Any help?

[darijgr]

comment:8

Don't worry, it's my own notation and everyone calls it differently. See the second solution to Exercise 2.7.12(a) in http://www.cip.ifi.lmu.de/~grinberg/algebra/HopfComb-sols.pdf or construction (1d) in Appendix A.4 of Fulton's Young tableaux book. You don't have to reimplement it as I haven't implemented it in the first place (this ticket only does dual RSK).

[ChamanAgrawal]

Changed keywords from IMA coding sprint, tableaux, permutations to gsocRSK, IMA coding sprint, tableaux, permutations

[ChamanAgrawal]

Changed branch from public/combinat/dualRSK_alt-25070 to u/gh-ChamanAgrawal/25070_coRSK

[ChamanAgrawal]

Changed commit from b8e89f3 to 3d073b5

[ChamanAgrawal]

Last 10 new commits:

4ee1e35	Remove insertion_complete for insertion()
02db216	Merge branch 'u/gh-ChamanAgrawal/27852_refactorRSK' into u/gh-ChamanAgrawal/28058_dualRSK
89a749c	Minor change in docs and insertion()
15934c5	implemented forward part of coRSK
f946493	Add forgotten docs change
e4554ee	Docs corrected
e03a2c9	Merge branch 'u/gh-ChamanAgrawal/27852_refactorRSK' into u/gh-ChamanAgrawal/28058_dualRSK
1bc9fb9	Resolved merge conflicts
54985f0	Merge branch 'u/gh-ChamanAgrawal/28058_dualRSK' into startcoRSK
3d073b5	Complete implementation of coRSK algorithm

[ChamanAgrawal]

Changed author from Darij Grinberg, Tom Roby to Darij Grinberg, Tom Roby, Chaman Agrawal

[sagetrac-git]

Changed commit from 3d073b5 to ec00502

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ec00502

Add docs and test for coRSK

[tscrim]

Changed keywords from gsocRSK, IMA coding sprint, tableaux, permutations to gsocRSK, IMA coding sprint, tableaux, permutations, fpsac2019

[sagetrac-git]

Changed commit from eaddf7d to e2986a9

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e2986a9

Remove default parameter from *_format_output

[sagetrac-git]

Changed commit from e2986a9 to 161db3d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

161db3d

Minor doc change

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

98bd5a8

Minor doc changes

[sagetrac-git]

Changed commit from 161db3d to 98bd5a8

[tscrim]

comment:19

There is a docbuild failure reported on the patchbot, likely from these things:

    For more information, see Chapter 7, Section 14 in [Sta-EC2]_
    (where dual RSK is called RSK*) or the Third solution to
    Exercise 2.7.12(a) in [GR2018v5sol]_.

      a `\{0, 1\}`-matrix (i.e., a matrix whose entries are `0`s
      and `1`s).

and

        (namely, the lists `(j_0, j_1, \ldots, j_{\ell-1})` and
        `(k_0, k_1, \ldots, k_{\ell-1})` represent the generalized
        permutation
        ((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell-1}, k_{\ell-1}))`)

In the first case, I would make it

    (where dual `\mathrm{RSK}` is called `\mathrm{RSK}^*`) or the third solution to

(also note that Third should not be capitalized) and the second, you need to have `0`'s and `1`'s as you cannot have the latex marker followed by a letter (Sphinx does not correctly interpret it as such). The third one is missing a backtick ` in the last line.

Also, typo reversel -> reversal, backwards CoRSK -> backwards coRSK,

-    Checking that tableaux should be of same shape::
+    Checking that the tableaux should be of same shape::

and

construction (1d)) or the Second solution to Exercise 2.7.12(a) in

Second should also not be capitalized.

[tscrim]

Changed reviewer from Darij Grinberg, Travis Scrimshaw, to Darij Grinberg, Travis Scrimshaw

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4c18e17

doc typos pointed out by Travis (mostly)

[sagetrac-git]

Changed commit from 98bd5a8 to 4c18e17

[darijgr]

comment:21

Done, thanks!

[tscrim]

comment:22

Now let's just wait for the patchbot. If that comes back (essentially) green, then this is a positive review.

[sagetrac-git]

Changed commit from 4c18e17 to c05a591

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

bfb6b5d	Merge branch 'public/ticket/25070' of git://trac.sagemath.org/sage into public/ticket/25070
c05a591	Fixing another `0`s and `1`s.

[sagetrac-git]

Changed commit from c05a591 to 739aa17

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

739aa17

Fixing pyflakes warnings.

[tscrim]

comment:26

Green patchbot. I just trivially fixed the pyflakes warnings, and I am allowing myself to set a positive review. Thank you all.

[vbraun]

Changed branch from public/ticket/25070 to 739aa17