jeudi 14 mars 2013

"Jeu de taquin" and growth diagrams

Growth diagrams yield a 2d-view of transformations involved in "jeu de taquin", a creation of Marcel-Paul Schützenberger, see Promotion and Evacuation by Richard P. Stanley, 2009. Here is a 2d-proof that evacuation (as defined by Schützenberger) is an involution:

This picture is constructed using a personal little Sage module, about skew tableaux. The standard module sage.combinat.skew_tableau is, as usual for enumerative combinatorics, useless. Here is an svg version of the picture.

Each row depicts a skew tableau as a sequence of growing diagrams: each diagram depicts a partition, and differs from the preceeding (in the same row) by adding a single cell, depicted by a blue square. Likewise each column is made (downward) by increasing diagrams, where the red square denotes the added cell. Green squares denote cells which are "simultaneously blue and red" (I know, this way of mixing colors is definitely wrong).

Here the bottom row is a given skew tableau t, and successive rows, bottom-up, result from successive evacuations of elements of t, as defined by Schützenberger.

The key observation is the local commutativity rule, which is equivalent to the definition of a taquin slide: starting from a diagram A, we may go right, where is the diagram B, then go down, where is D; or we may first go down, where is C, and then right, where is D. If blue and red squares involved are independent (i.e. they don't form a domino), these "two steps" walks differ by the order in which cells are added. Otherwise these walks are identical, D has an unique green square, that is a "free cell" during a "jeu de taquin" slide.

These rules allow to reconstruct the whole family of diagrams, from the initial tableau t, depicted by the bottom row, and from the diagonal, where all partitions are equal to the inner shape of t. The last column depicts the tableau ε(t) where ε denotes the evacuation operator, and because local commutativity rules are invariant by exchanging rows and columns, the bottom row depicts as well the tableau that results of applying ε to the last column. This is the expected 2d-proof that ε is an involution.

For the record let's look at the two bottom rows of the picture, to analyze their relationship with "jeu de taquin" sliding. The skew tableau t (bottom row) is the following left one, and the evacuation of entry 1 yield the next four tableaux, where a question mark ? denotes the "free cell" during sliding of the entries 1, 2, 5, 9. The last of these tableaux, on the right, results from this sliding:

* * 1 3 10    * * ? 3 10    * * 2 3 10    * * 2 3 10    * * 2 3 10
* * 2 5 11    * * 2 5 11    * * ? 5 11    * * 5 ? 11    * * 5 9 11
* 4 7 9       * 4 7 9       * 4 7 9       * 4 7 9       * 4 7 ?
6 8 12        6 8 12        6 8 12        6 8 12        6 8 12

Compare with the two bottom rows of the main picture, reproduced here for convenience:

In the bottom row, diagrams 1, 2, 5, 9 (with numbering starting at 0) have a green cell, in the same position as the question mark identifying free cell in "jeu de taquin"; other diagrams have a red cell, in the same position as the preceeding green one. It should be clear that on the other hand, this description of green and red cells results precisely from the local commutativity rules, and yields the top row among these two.

Note: jeu de taquin, promotion, evacuation and growth diagrams make sense for any finite poset, see Schützenberger and the cited article by Richard Stanley. This post is about the seminal case, where the underlying poset is N x N, and finite ideals are partitions, which form the Young lattice.

1 commentaire:

  1. Thank you for the picture. It also gives a proof without words of the bijection between self-evacuating and domino tableaux. In the self-evacuating case, the diagram is symmetric, and along the axis of symmetry there can only be green boxes.

    RépondreSupprimer