Complementary algorithms for tableaux

Abstract: We study four operations defined on pairs of tableaux. Algorithms for the first three involve the familiar procedures of jeu de taquin, row insertion, and column insertion. The fourth operation, hopscotch, is new, although specialised versions have appeared previously. Like the other three operations, this new operation may be computed with a set of local rules in a growth diagram, and it preserves Knuth equivalence class. Each of these four operations gives rise to an a priori distinct theory of dual equivalence. We show that these four theories coincide. The four operations are linked via the involutive tableau operations of complementation and conjugation.

Review text

In 1987, in his theory of rational tableaux, Stembridge found a striking duality between the insertion procedure of Schensted and the theory of jeu de taquin of Schützenberger. In the paper under review the authors introduce the involutive tableau operation of complementation to formalize this duality and show that the internal row insertion and the jeu de taquin give complementary operations on pairs of tableaux. By conjugation, one may consider the operation of internal column insertion. The complementary operation hopscotch, studied by the authors, is new, although it extends known algorithms. Like the other three operations, this new operation may be computed with a set of local rules in a grow diagram. The four operations of jeu de taquin, internal row insertion, internal column insertion and hopscotch preserve the Knuth equivalence. Hence hopscotch gives rise to new algorithms to rectify tableaux. The authors also establish that these four operations have the same dual-equivalence theory.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Complementary algorithms for tableaux

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5952336)