Voici à quoi ressemble un fpl (fully packed loop) typique (tiré au sort avec équiprobabilité, via un algorithme coupling from the past). Les points rouges (resp. bleus) marquent les +1 (resp. -1) de la matrice à signes alternants correspondante.

En voici un autre, inscrit cette fois dans un carré de côté 128; les circuits ne sont pas dessinés, seuls apparaissent les chemins, qui relient deux points sur les bords du carré. Les cinq chemins les plus longs sont coloriés en rouge (chemin le plus long, de taille 1669), vert (deux chemins de tailles 1116 et 544) ou bleu.

Voici enfin une matrice à signes alternants de même taille (toujours tirée au sort avec équiprobabilité), dont chaque élément est colorié selon le modèle à six sommets. Les points rouges et bleus sont, comme précédemment, les +1 et les -1, tandis que les autres sont coloriés comme leurs frères des quatre coins.

Les calculs ont été effectués avec un module Julia.

Promotion and growth diagrams

Here is the picture associated with dual evacuation (with an svg version):

This time the skew tableau t is depicted by the top row, and next rows, downward, result from successive dual evacuations of elements of t, selected in decreasing order.

The local commutativity rules enable us to build the whole family of diagrams, from the top row and from the diagonal, where all partitions are equal to the outer shape of t. The first column depicts the tableau ε^*(t), and symmetry between rows and columns yields a 2d-proof that dual evacuation ε^* is an involution.

This dual version of the preceding post would be of little interest, if it was not a preamble to a much nicer formula involving promotion. This operator ∂ is defined like evacuation of the minimal element, except that we put in the cell freed by this evacuation, a new entry larger than any other. The following picture shows p successive applications of ∂ to a tableau t (bottom row), where p is the size of t, i.e., the number of entries:

(here is an svg version).

Because the local rules that allow us to build the picture from the bottom row and from one of the diagonals are always the same, we discover that the left half of the picture, bordered by the central column, is exactly the same as the picture associated to evacuation, published in the preceding post; and on the right half of the picture we recognize a dual evacuation, applied to the central column (beware that diagrams in this part of the picture are different from those located at the start of this post, because top row is different). Hence we get a very nice 2d-proof of the following formula, again due to Schützenberger:

∂ ^p = ε ε^*

where the operators are composed in the "right" order, i.e. first ε then ε^*. The tableau ε(t) appears as the central column on this picture.

"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.