View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100301.png" />-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 typical example is the  "puzzle"  program distributed with the Macintosh operating system).

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

The Robinson–Schensted construction (cf. [[Robinson–Schensted correspondence|Robinson–Schensted correspondence]]) establishes a bijection between a permutation and a pair of standard Young tableaux (cf. [[Young tableau|Young tableau]] and [[#References|[a2]]]). It is a fundamental tool in the combinatorics of representations of symmetric groups (cf. [[#References|[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|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 [[#References|[a1]]].

The plactic (or Knuth) congruences are the following: Let the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100302.png" /> be totally ordered and suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100303.png" />. Then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100304.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100305.png" /></td> </tr></table>

This equivalence can be transferred to (semi-standard) skew Young tableaux (cf. [[Skew Young tableau|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:

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/j110030a.gif" />

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100306.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100307.png" />. Then apply jeu de taquin transformations to that tableau a Young tableau is obtained. This last tableau depends only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100308.png" />, but not on the choices of starting tableau and of transformations. It is exactly the first tableau of the pair associated to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100309.png" />.

For example, start with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j11003010.png" />. One can produce the following sequence of transformations. Note that the starting tableau has the  "reading property"  mentioned above.

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/j110030b.gif" />

Figure: j110030b

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Knuth,   "The art of computer programming" , '''3''' , Addison-Wesley  (1973)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  I.G. Macdonald,   "Symmetric functions and Hall polynomials" , Clarendon Press  (1995)  (Edition: Second)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR></table>