Opened 4 years ago

Last modified 4 years ago

#24659 new enhancement

Make semistandard extension of growth diagrams generic.

Reported by: mantepse Owned by:
Priority: major Milestone: sage-8.2
Component: combinatorics Keywords:
Cc: aschilling Merged in:
Authors: Martin Rubey Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by mantepse)

Growth diagrams as introduced by Fomin work for partial fillings of skew Ferrers shapes: in every row and every column at most one cross (possibly coloured, depending on the type of growth diagram) is allowed.

However, for Robinson-Schensted insertion, one can accommodate several entries in rows and columns, and arbitrary nonnegative integer entries instead of crosses as follows:

  • for each row with sum of entries equal to e, subdivide the row into e rows,
  • same for the columns
  • arrange crosses in the new grid according to one of the rules below, whenever they correspond to entries in the same row or column of the original growth diagram.
  • Rule RSK ("Knuth"): arrange crosses increasing in rows and columns
  • Rule RSK' ("Burge"): arrange crosses decreasing in rows and columns

and for 0-1 fillings:

  • Rule RSK*: increasing in columns, decreasing in rows
  • Rule RSK'*: increasing in rows, decreasing in columns

This ticket aims at adding supporting code.

For shifted insertion, there is a different standardisation procedure. This is described in Section 8 of Sagan's "Shifted Tableaux, Schur Q-Functions, and a Conjecture of R. Stanley". A naive implementation to standardise words is attached.

Attachments (1)

shifted.sage (1.8 KB) - added by mantepse 4 years ago.

Download all attachments as: .zip

Change History (8)

Changed 4 years ago by mantepse

comment:1 Changed 4 years ago by mantepse

  • Description modified (diff)

comment:2 follow-up: Changed 4 years ago by mantepse

Anne, which version of shifted semistandard insertion do you need precisely? Bruce Sagan's is a bijection between matrices with nonnegative integer entries, possibly primed, and pairs (T,U) of generalized shifted tableaux of the same shape, such that U has no primed entries on the diagonal.

A generalized shifted tableau is a filling that is weakly increasing in rows and columns and primed entries are not repeated in rows and unprimed entries are not repeated in columns.

Thus, T is not a ShiftedPrimedTableau, because it can have primed entries on the diagonal.

I'm not sure how this is dealt with best. Subclassing?

comment:3 Changed 4 years ago by mantepse

  • Description modified (diff)

comment:4 in reply to: ↑ 2 Changed 4 years ago by aschilling

Replying to mantepse:

Anne, which version of shifted semistandard insertion do you need precisely? Bruce Sagan's is a bijection between matrices with nonnegative integer entries, possibly primed, and pairs (T,U) of generalized shifted tableaux of the same shape, such that U has no primed entries on the diagonal.

I am interested in the Haiman mixed insertion, see for example Section 3.2 in https://arxiv.org/pdf/1704.00889.pdf.

comment:5 Changed 4 years ago by mantepse

OK, that's (I believe) the same as Sagan's extension for unprimed words.

With the attached file, you can in principle do this, except that I haven't implemented "destandardisation". In fact, I need some help there or do some thinking myself - the question is what is the precise analogue of the labels between the letters in to_chain.

I now know how I want to add this to the growth diagram framework, I hope to do it over the weekend.

comment:6 Changed 4 years ago by gh-MareoRaft

Take note that the addition of the superRSK algorithm (https://trac.sagemath.org/ticket/24894) is similar in many ways to Haiman mixed insertion, but not the same.

It seems that the tableau in Haiman mixed insertion in the paper linked above don't follow the standard tableau shape. Also, Haiman mixed insertion behaves differently on diagonals. superRSK does not treat diagonals in any special way.

Still, I'm confident that these algorithms can share code. For example, you can probably reuse my _bump_row and _bump_col functions.

Version 0, edited 4 years ago by gh-MareoRaft (next)

comment:7 Changed 4 years ago by gh-MareoRaft

In fact, in Rob Muth's paper (https://arxiv.org/pdf/1711.00420.pdf), Remark 3.2, he says "If X = N, where < is the usual order on integers and every element is of even parity, then 0-insertion is Schensted insertion [S]. For general X and standard tableaux, 0-insertion is mixed insertion as defined by Haiman (where odd letters are referred to as circled) [H]."

He might be mistaken though, since again when I read your reference, it says something about diagonals.

Note: See TracTickets for help on using tickets.