Jeu de taquin

In the mathematical field of combinatorics, jeu de taquin is a construction due to Marcel-Paul Schützenberger (1977) which defines an equivalence relation on the set of skew standard Young tableaux.

Two tableaux are jeu de taquin equivalent if one can be transformed into the other via a sequence of such slides.

"Jeu de taquin" (literally "teasing game") is the French name for the fifteen puzzle.

, pick an adjacent empty cell c that can be added to the skew diagram

There are two kinds of slide, depending on whether c lies to the upper left of T or to the lower right.

(This rule is designed so that the tableau property of having increasing rows and columns will be preserved.)

The other kind of slide, when c lies to the lower right of T, just goes in the opposite direction.

Jeu-de-taquin slides change not only the relative order of the entries of a tableau, but also its shape.

is a Young diagram), and the resulting skew shape is set to be

The only change that has to be made to the definition of an inward slide, in order for it to generalize, is a rule on how to proceed when the (temporarily) empty cell has neighbours below and to its right, and these neighbours are filled with equal numbers.

A similar change is needed in the definition of an outward slide (where one has to choose the neighbor above).

These changes may seem arbitrary, but they actually make the "only reasonable choices"—meaning the only choices that keep the columns of the tableau (disregarding the empty cell) strictly increasing (as opposed to just weakly increasing).

This can generally be done in many different ways (one can freely choose into which cell to slide first), but the resulting straight-shape tableau is known to be the same for all possible choices.

This tableau is called the rectification of T. Two skew semistandard tableaux T and S are said to be jeu-de-taquin equivalent if one can transform one of them into the other using a sequence (possibly empty) of slides (both inward and outward slides being allowed).

There are various ways to associate a word (in the sense of combinatorics, i. e., a finite sequence of elements of an alphabet—here the set of positive integers) to every Young tableau.

(Each row of T is seen as a word simply by reading its entries from left to right, and we draw Young tableaux in English notation so that the longest row of a straight-shape tableau appears at the top.)

Jeu de taquin can be used to define an operation on standard Young tableaux of any given shape, which turns out to be an involution, although this is not obvious from the definition.

Now apply a jeu de taquin slide to turn that skew tableau into a straight one, which will free one square on the outside border.

Then fill this square with the negative of the value that was originally removed at the top-left corner; this negated value is considered part of a new tableau rather than of the original tableau, and its position will not change in the sequel.

Now as long as the original tableau has some entries left, repeat the operation of removing the entry x of the top-left corner, performing a jeu de taquin slide on what is left of the original tableau, and placing the value −x into the square so freed.

When all entries of the original tableau have been handled, their negated values are arranged in such a way that rows and columns are increasing.

Jeu de taquin is closely connected to such topics as the Robinson–Schensted–Knuth correspondence, the Littlewood–Richardson rule, and Knuth equivalence.