Tableau algorithms defined naturally for pictures
We consider pictures as defined by Zelevinsky. We elaborate on the generalisation of the Robinson-Schensted correspondence to pictures defined by him, and on the result of Fomin and Greene that shows that this correspondence is natural, i.e., independent of the precise ``reading'' order of the squares of skew diagrams that is used in its definition. We give a simplified proof of this result by showing that the generalised Schensted insertion procedure can be defined without using this order at all. Our main results involve the operation of glissement defined by Schützenberger. We show that glissement can be generalised to pictures, and is natural. In fact, we obtain two dual forms of glissement; consequently both tableaux corresponding to a permutation in the Robinson-Schensted correspondence can be obtained by glissement from one picture. We show that the two forms of glissement commute with each other. From this fact the main properties of glissement follow in a much simpler way than their original derivation by Schützenberger.
|Department of Analysis, Algebra and Geometry [AM]|
van Leeuwen, M.A.A. (1995). Tableau algorithms defined naturally for pictures. Department of Analysis, Algebra and Geometry [AM]. CWI.