Implement Hecke insertion

[tscrim]

Hecke insertion is a variant of RSK which has interesting applications in

• K-theoretic Schubert calculus,
• representation theory of the 0-Hecke monoid, and
• probability theory of the Plancherel-Hecke measure.

For a reference, see http://arxiv.org/abs/0801.1319.

CC: @sagetrac-sage-combinat @darijgr @nthiery

Component: combinatorics

Keywords: hecke insertion, RSK

Author: Travis Scrimshaw

Branch/Commit: 264484f

Reviewer: Darij Grinberg

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

[tscrim]

Description changed:

--- 
+++ 
@@ -3,3 +3,5 @@
 - K-theoretic Schubert calculus,
 - representation theory of the 0-Hecke monoid, and
 - probability theory of the Plancherel-Hecke measure.
+
+For a reference, see http://arxiv.org/abs/0801.1319.

[tscrim]

New commits:

c64ff5a

Implementation of Hecke insertion.

[tscrim]

Commit: c64ff5a

[tscrim]

Branch: public/combinat/hecke_insertion-19541

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1a53e81	Merge branch 'public/combinat/hecke_insertion-19541' of git://trac.sagemath.org/sage into hecke
f8b1034	review up to reverse insertion

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c64ff5a to f8b1034

[tscrim]

comment:3

The comment

# We must have len(p[j-1]) > len(r), otherwise we would
#   have added x to the previous row

comes from if len(p[j-1]) == len(r) (recall r = p[j]) and we wanted to add the entry x to the end of r, then by the strictly increasing condition, we should have added x to the end of p[j-1]. It means that we can skip the check that len(p[j-1]) > len(r).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f8b1034 to af8855b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

af8855b

More documentation fixes

[darijgr]

comment:5

Ah, I got it! I think my way of saying it is clearer, though.

In other news, am I seeing it right that reversed(d.items()) and reversed(row_dict.values()) are fragile? I'll replace them by safer things.

[tscrim]

comment:6

Replying to @darijgr:

Ah, I got it! I think my way of saying it is clearer, though.

I won't argue.

In other news, am I seeing it right that reversed(d.items()) and reversed(row_dict.values()) are fragile? I'll replace them by safer things.

Ah, yes, those are bad. Should be sorted(d.items(), key=lambda x: -x[0]) (the minus should do the reversal, otherwise just also add the reverse=True) and sorted(row_dict.values(), reverse=True) resp. I don't know what I was thinking...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from af8855b to 264484f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

264484f

rsk.py reviewed

[darijgr]

comment:8

Thanks for the prompt fix suggestion. The code now LGTM. I have added some weasel language (in one of my previous commits) to avoid creating the impression that the Hecke RSK algorithm is understood in the "semistandard" case (i.e., upper row is not (1, 2, ..., n)). If you have a source for this, please put it in a reference.

[tscrim]

Reviewer: Darij Grinberg

[tscrim]

comment:9

I think my reference allows for it, but I'm okay with the language being there. Thanks for doing the review.

[vbraun]

Changed branch from public/combinat/hecke_insertion-19541 to 264484f