Tableau switching: Algorithms and applications (Q1924234)

The (skew) shape \(\lambda/\mu\) extends the shape \(\mu/\nu\) when \(\lambda\supseteq \mu\subseteq \nu\) are partitions (identified with their Young diagrams): a tableau is obtained by filling such a shape by integers which increase weakly along rows and strictly down columns. A `switching' algorithm is given which transforms a pair \((S,T)\) of tableaux, such that the shape of \(T\) extends the shape of \(S\), into a new pair \((^ST, S_T)\), such that the shape of \(S_T\) extends the shape of \(^ST\). The algorithm consists of a sequence of exchanges of numbers from \(S\) with adjacent numbers to the right or below from \(T\), subject only to the condition that the exchange preserves the row and column conditions for the numbers from \(S\) and for the numbers from \(T\). Thus the content of \(^ST\) is the same as that of \(T\), the content of \(S_T\) is the same as that of \(S\), and the shape of \(^ST\cup S_T\) is the same as that of \(S\cup T\). Remarkably, the tableaux \(^ST\) and \(S_T\) are independent of the sequence of exchanges carried out. Further, the switching map can be defined axiomatically as the unique such map of pairs of tableaux which is compatible with decompositions, in a natural sense, of \(S\) or \(T\) as a disjoint union of two subtableaux. The tableaux \(^ST\) and \(S_T\) are Knuth equivalent to \(T\) and to \(S\) respectively, and the switching map is an involution: if we start with \((^ST, S_T)\), then we recover \((S,T)\). This switching procedure generalises similar algorithms constructed by several authors and used to prove identities concerning inter alia Schur functions, branching rules and Littlewood-Richardson coefficients, and so it provides a uniform approach to these proofs. A variant of the procedure, in which the tableaux \(T\) and \(^ST\) are row strict rather than column strict, permits an application to work of Remmel on super-Schur functions. Further applications of the switching procedure are given which relate to Haiman's notion of `dual equivalence' for tableaux and to Schützenberger's `evacuation procedure'. This leads to the concept of the reverse \(U^e\) of an arbitrary skew tableau \(U\): \(U^e\) is the unique tableau which is dual equivalent to \(U\) (and so has the same shape as \(U\)) and is Knuth equivalent to the tableau \(U^*\) obtained by rotating \(U\) \(180^\circ\) and changing the sign of each entry. In the case where the shape of \(U\) is the Young diagram of a partition, \(U^e\) coincides with the evacuation \(U^E\) of \(U\). The involution \(U\mapsto U^{e*}\) provides an explicit bijection between tableaux of rotated shape having the same content, and this is used to give an elegant proof that the skew Schur functions corresponding to rotated shapes are equal. Symmetries of Littlewood-Richardson coefficients due to Berenstein and Zelevinsky are similarly obtained.