Jeu de taquin

The French name of a puzzle game introduced in France by H.E. Lucas. It consists of fifteen wooden squares, numbered from one to fifteen, which can be moved in a $(4\times4)$-box. A single space is free, and must be used to restore the consecutive numbering of the smaller squares. This game is still on sale with some variations.

┌───┬───┬───┬───┐
│ a │ b │ c │ d │
├───┼───┼───┼───┤
│ e │ f │ g │ h │
├───┼───┼───┼───┤
│ i │ j │ k │ l │
├───┼───┼───┼───┤
│ m │ n │ o │   │
└───┴───┴───┴───┘

By analogy, this same name has been given by M.-P. Schützenberger (cf. [a4], [a5]) to a graphical representation of the plactic, or Knuth, congruences.

The Robinson–Schensted construction (cf. Robinson–Schensted correspondence) establishes a bijection between a permutation and a pair of standard Young tableaux (cf. Young tableau and [a2]). It is a fundamental tool in the combinatorics of representations of symmetric groups (cf. [a3]). This construction has been extended to words (i.e. allowing repetitions) by D. Knuth. In the latter case, the first tableau is no longer standard, but semi-standard (the entries are increasing along the columns and non-decreasing along the rows). Knuth has also shown that two words correspond to the same semi-standard tableau if and only if it is possible to obtain one from the other by a succession of certain commutations of letters.

Further, A. Lascoux and Schützenberger have established that the equivalence relation generated by this set of relations is compatible with concatenation. The quotient monoid (which is in bijection with the set of semi-standard tableaux) is known as the plactic monoid. They have also given the fundamental properties of this monoid, in [a1].

The plactic (or Knuth) congruences are the following: Let the alphabet $X$ be totally ordered and suppose that $a<b<c$. Then

$$bca\equiv bac,acb\equiv cab,$$

$$aba\equiv baa,bba\equiv bab.$$

This equivalence can be transferred to (semi-standard) skew Young tableaux (cf. Skew Young tableau) in the following way. Two skew Young tableaux are equivalent if and only if one can be obtained from the other by a succession of local transformations corresponding, respectively, to the four plactic congruences:

Figure: j110030a

Under this equivalence relation each class of skew Young tableaux contains exactly one Young tableau. This statement is in fact equivalent to Knuth's theorem. This game of transformation of tableaux is what is called jeu de taquin.

It can be used to provide an alternative to the original Schensted insertion algorithm as generalized by Knuth. Let $w$ be a word. Consider any skew Young tableau such that, reading its entries from left to right and from bottom to top, one obtains precisely $w$. Then apply jeu de taquin transformations to that tableau a Young tableau is obtained. This last tableau depends only on $w$, but not on the choices of starting tableau and of transformations. It is exactly the first tableau of the pair associated to $w$.

For example, start with $w=abcba$. One can produce the following sequence of transformations. Note that the starting tableau has the "reading property" mentioned above.

Figure: j110030b

References

[a1]	A. Lascoux, M.-P. Schützenberger, "Le monoïde plaxique" , Non Commutative Structures in Algebra and Geometric Combinatorics, Arco Felice (1978) , Quaderni Ricerca Sci. , 109 , Consiglio Naz. Ricerche (1981) pp. 129–156
[a2]	D. Knuth, "The art of computer programming" , 3 , Addison-Wesley (1973)
[a3]	I.G. Macdonald, "Symmetric functions and Hall polynomials" , Clarendon Press (1995) (Edition: Second)
[a4]	M.-P. Schützenberger, "Sur une construction de Gilbert de B. Robinson" , Algèbre (1971/2) , Sém. P. Dubreuil 25e année , 1: 8 , Secrétariat Math. Univ. Paris (1973)
[a5]	M.-P. Schützenberger, "La correspondance de Robinson" , Combinatoire et Représentations du Groupe Symétrique, Strasbourg (1976) , Lecture Notes in Mathematics , 579 , Springer (1977) pp. 59–135 Zbl 0398.05011