Jeu de taquin

In the mathematical field of combinatorics, jeu de taquin is a construction due to Schützenberger [Schützenberger 1977] which defines an equivalence relation on the set of skew standard Young tableaux. A jeu de taquin slide is a transformation where the numbers in a tableau are moved around in a way similar to how the pieces in the fifteen puzzle move. ["Jeu de taquin" (literally "teasing game") is in fact just the French name for the fifteen puzzle.] Two tableaux are jeu de taquin equivalent if one can be transformed into the other via a sequence of such slides.

Definition of a jeu de taquin slide

Given a skew standard Young tableau "T" of skew shape $lambdasetminusmu$, pick an adjacent empty cell "c" that can be added to $lambdasetminusmu$; what this means is that "c" must share at least one edge with some cell in "T", and $\{c\}\; cup\; lambdasetminusmu$ must also be a skew shape. There are two kinds of slide, depending on whether "c" lies to the upper left of "T" or to the lower right. Suppose to begin with that "c" lies to the upper left. Slide the number from its neighbouring cell into "c"; if "c" has neighbours both to its right and below, then pick the smallest of these two numbers. (This rule is designed so that the tableau property of having increasing rows and columns will be preserved.) If the cell that just has been emptied has no neighbour to its right or below, then the slide is completed. Otherwise, slide a number into that cell according to the same rule as before, and continue in this way until the slide is completed. After this transformation, the resulting tableau is still a skew (or possibly straight) standard Young tableux.

The other kind of slide, when "c" lies to the lower right of "T", just goes in the opposite direction. In this case, one slides numbers into an empty cell from the neighbour to its left or above, picking the larger number whenever there is a choice. The two types of slides are mutual inverses – a slide of one kind can be undone using a slide of the other kind.

Applications

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

Notes

References

*Citation
last = Schützenberger
first = Marcel-Paul
author-link = Marcel-Paul Schützenberger
year = 1977
contribution = La correspondance de Robinson
contribution-url =
editor-last = Foata
editor-first = Dominique
editor-link =
editor2-last =
editor2-first =
editor2-link =
title = Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976)
edition =
series = Lecture Notes in Math. 579
place = Berlin
publisher = Springer
volume =
pages = 59–113
id =
isbn =
doi =
oclc =
url =

*Citation
last = Stanley
first = Richard P.
author-link = Richard P. Stanley
year = 1999
title = Enumerative Combinatorics
edition =
volume = 2
series = Cambridge Studies in Advanced Mathematics 62
publication-place =
place =
publisher = Cambridge University Press
pages =
page =
id =
isbn = 0-521-56069-1
doi =
oclc =
url = http://www-math.mit.edu/~rstan/ec/
accessdate =

*Citation
last = Sagan
first = Bruce E.
author-link =
year = 2001
title = The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions
edition = 2nd
volume =
series = Graduate Texts in Mathematics 203
place = New York
publisher = Springer
pages =
page =
id =
isbn = 0-387-95067-2
doi =
oclc =
url =
accessdate =