Color-to-spin ribbon Schensted algorithms (Q1348154)

A colored permutation is a permutation \(\pi\) with values colored with colors from \(\{0,1,\dots,k-1\}\). The total color of \(\pi\) is the sum of the colors in its colored values. A \(k\)-ribbon is a connected skew shape with \(k\) cells with at most one cell on each (northwest to southeast) diagonal. The spin of the ribbon is equal to the difference between the row indices of the head and the tail of the ribbon. Standard ribbon tableaux are built from ribbons in the same way as domino tableaux are built from dominos. The spin of the tableau is the sum of the spins of the ribbons. In the paper under review the authors construct a new Schensted bijection from the colored permutations to pairs of standard \(k\)-ribbon tableaux of the same shape such that twice the total color of the permutation is equal to the sum of the spins of the tableaux. This new bijection has the involution property: Taking a suitable inverse of the permutation has the effect of exchanging the two tableaux. The color-to-spin ribbon Schensted algorithm is introduced both in traditional manner and in a poset-theoretic framework. The authors present also an extension of this bijection to a bijection between colored indexed words and pairs of ribbon tableaux of the same shape, one semistandard and the other standard.