Spin-Preserving Knuth Correspondences for Ribbon Tableaux

  • Marc A. A. van Leeuwen


The RSK correspondence generalises the Robinson-Schensted correspondence by replacing permutation matrices by matrices with entries in ${\bf N}$, and standard Young tableaux by semistandard ones. For $r\in{\bf N}_{>0}$, the Robinson-Schensted correspondence can be trivially extended, using the $r$-quotient map, to one between $r$-coloured permutations and pairs of standard $r$-ribbon tableaux built on a fixed $r$-core (the Stanton-White correspondence). Viewing $r$-coloured permutations as matrices with entries in ${\bf N}^r$ (the non-zero entries being unit vectors), this correspondence can also be generalised to arbitrary matrices with entries in ${\bf N}^r$ and pairs of semistandard $r$-ribbon tableaux built on a fixed $r$-core; the generalisation is derived from the RSK correspondence, again using the $r$-quotient map. Shimozono and White recently defined a more interesting generalisation of the Robinson-Schensted correspondence to $r$-coloured permutations and standard $r$-ribbon tableaux; unlike the Stanton-White correspondence, it respects the spin statistic on standard $r$-ribbon tableaux, relating it directly to the colours of the $r$-coloured permutation. We define a construction establishing a bijective correspondence between general matrices with entries in ${\bf N}^r$ and pairs of semistandard $r$-ribbon tableaux built on a fixed $r$-core, which respects the spin statistic on those tableaux in a similar manner, relating it directly to the matrix entries. We also define a similar generalisation of the asymmetric RSK correspondence, in which case the matrix entries are taken from $\{0,1\}^r$.

More surprising than the existence of such a correspondence is the fact that these Knuth correspondences are not derived from Schensted correspondences by means of standardisation. That method does not work for general $r$-ribbon tableaux, since for $r\geq3$, no $r$-ribbon Schensted insertion can preserve standardisations of horizontal strips. Instead, we use the analysis of Knuth correspondences by Fomin to focus on the correspondence at the level of a single matrix entry and one pair of ribbon strips, which we call a shape datum. We define such a shape datum by a non-trivial generalisation of the idea underlying the Shimozono-White correspondence, which takes the form of an algorithm traversing the edge sequences of the shapes involved. As a result of the particular way in which this traversal has to be set up, our construction directly generalises neither the Shimozono-White correspondence nor the RSK correspondence: it specialises to the transpose of the former, and to the variation of the latter called the Burge correspondence.

In terms of generating series, our shape datum proves a commutation relation between operators that add and remove horizontal $r$-ribbon strips; it is equivalent to a commutation relation for certain operators acting on a $q$-deformed Fock space, obtained by Kashiwara, Miwa and Stern. It implies the identity $$\sum_{\lambda\geq_r(0)}G^{(r)}_\lambda(q^{1\over2},X) G^{(r)}_\lambda(q^{1\over2},Y) =\prod_{i,j\in{\bf N}}\prod_{k=0}^{r-1}{1\over1-q^kX_iY_j}; $$ where $G^{(r)}_\lambda(q^{1\over2},X)\in{\bf Z}[q^{1\over2}][[X]]$ is the generating series by $q^{{\rm spin}(P)}X^{{\rm wt}(P)}$ of semistandard $r$-ribbon tableaux $P$ of shape $\lambda$; the identity is a $q$-analogue of an $r$-fold Cauchy identity, since the series factors into a product of $r$ Schur functions at $q^{1\over2}=1$. Our asymmetric correspondence similarly proves $$\sum_{\lambda\geq_r(0)}G^{(r)}_\lambda(q^{1\over2},X) \check G^{(r)}_\lambda(q^{1\over2},Y) =\prod_{i,j\in{\bf N}}\prod_{k=0}^{r-1}(1+q^kX_iY_j). $$ with $\check G^{(r)}_\lambda(q^{1\over2},X)$ the generating series by $q^{{\rm spin}^{\rm t}(P)}X^{{\rm wt}(P)}$ of transpose semistandard $r$-ribbon tableaux $P$, where ${\rm spin}^{\rm t}(P)$ denotes the spin as defined using the standardisation appropriate for such tableaux.

Article Number