Edge Sequences, Ribbon Tableaux, and an Action of Affine Permutations

Marc A. A. van Leeuwen

Université de Poitiers, Département de Mathématiques, SP2MI, Téléport 2, BP 179, 86960 Futuroscope Cedex, France

                              maavl@math.univ-poitiers.fr
                     URL: http://www-math.univ-poitiers.fr/~maavl/

ABSTRACT

An overview is provided of some of the basic facts concerning rim hook lattices and ribbon tableaux, using a representation of partitions by their edge sequences. An action is defined of the affine Coxeter group of type Ã_{r−1} on the r-rim hook lattice, and thereby on the sets of standard and semistandard r-ribbon tableaux, and this action is related to the concept of chains in r-ribbon tableaux.

1991 Mathematics Subject Classification: 05E10.

Keywords and Phrases: ribbon tableau, rim hook lattice, affine permutation group.

§1. Introduction. Rim hook lattices are defined by endowing the set P of all partitions of natural numbers with a partial ordering ‘≤_{r}’ for some r > 0; this partial ordering is generated by the removal of so-called rim hooks of length r (also called r-ribbons) from Young diagrams. Saturated chains in such a lattice correspond to combinatorial objects known as ribbon tableaux. In this note we study the basic properties of ribbon tableaux, using a particular way to represent partitions, namely by their edge sequences; this leads in a very easy way to a structure theorem for rim hook lattices (§2), and thereby to decomposition theorems for ribbon tableaux (§3). Neither these theorems nor the concept of edge sequences are new, but it appears that the systematic use of edge sequences to study rim hook lattices and ribbon tableaux is. From our description we obtain in a natural way an action of the group S̃_{r}, which is an affine Coxeter group of type Ã_{r−1}, by automorphisms on the r-rim hook lattice, and thereby on r-ribbon tableaux (§4). A detailed study of this action leads to the concept of chains of ribbons in r-ribbon tableaux, which has been considered previously only for domino tableaux (r = 2); we derive some basic combinatorial properties of chains and of the operation of moving them in the ribbon tableau.

The purpose of this note is twofold. In the first place we wish to provide a self-contained introduction to the theory of ribbon tableaux, giving simple proofs of all the basic facts. In the second place this note is a preliminary to a forthcoming paper [11] on domino tableaux: we collect here all definitions and results needed there for domino tableaux that are valid in the more general setting of r-ribbon tableaux.

Elements of N×N will be called squares, and correspondingly displayed, using the matrix convention that the first index increases downwards, and the second index to the right. The term inward will be used throughout to mean “to the left and/or upwards”, and similarly outward means “to the right and/or downwards”; a typical use is to discriminate between inward and outward slides for jeu de taquin.

We shall denote the set of all partitions of natural numbers by P. Depending on the context, a partition λ ∈ P will be either considered to be a weakly decreasing sequence (λ_{0}, λ_{1}, …) of natural numbers, or will be identified with the corresponding Young diagram { (i, j) ∈ N × N | j < λ_{i} } (a set of squares); the latter always applies when set theoretic notation such as (i, j) ∈ λ is used. The empty partition (0, 0, …) will be denoted by ∅, the cardinality ∑_{i} λ_{i} of the Young diagram λ by |λ|, and its transpose by λ^{t}. For λ, μ ∈ P the use of the notation λ/μ will imply that μ ⊆ λ, but otherwise it is just a formal symbol; it is related to the skew diagram λ \ μ (set theoretic difference of Young diagrams), but that set alone might fail to determine λ and μ.

§2. Edge sequences. We associate to λ ∈ P a doubly infinite word δ(λ) over the alphabet {0, 1}, called its edge sequence. It describes the shape of the boundary of the (connected) region occupied by the set of squares N × N \ λ, as a sequence of vertical and horizontal line segments (of length 1) going from bottom-left to top-right, where 1 represents a vertical segment and each 0 a horizontal segment. For instance, for λ = (3, 3, 1) the part of the boundary near the origin looks like this:

We therefore have δ(λ) = (… 1 1 1 0 1 0|0 1 1 0 0 0 …), where the ‘|’ is a reference mark indicating the point where the boundary crosses the main diagonal. The individual terms of an edge sequence will be referred to as its bits. Formally, δ(λ) is a map Z → {0, 1} defined by

δ(λ)(d) = \{ \begin{matrix}1 & if d ∈ \{ λ_{i} − i − 1 | i ∈ N \} \\ 0 & if d ∈ \{ j − λ_{j}^{t} | j ∈ N \} \end{matrix}  (1)

(the two conditions are easily seen to be complementary); the ‘|’-mark separates the indices d < 0 from the indices d ≥ 0. We shall denote the edge seqence δ(∅) = (… 1 1 1|0 0 0 …) of the empty partition by δ_{0}, so that

δ_{0}(d) = \{ \begin{matrix}1 & if d ∈ Z \ N \\ 0 & if d ∈ N \end{matrix} .  (2)

We define

FD = { f: Z → {0, 1} | f(d) = δ_{0}(d) for all but finitely many d }  (3)

(the sequences at finite Hamming distance from δ_{0}); then δ is an injection P → FD. Moreover, for any λ ∈ P, the differences between δ(λ) and δ_{0} are evenly distributed between both sides of the ‘|’-mark: there are |{ i ∈ N | (i, i) ∈ λ }| differences on either side. In fact, if we define for f ∈ FD its “displacement” as

d(f) = ∑_{i∈Z} f(i) − δ_{0}(i) = |{ d ≥ 0 | f(d) = 1 }| − |{ d < 0 | f(d) = 0 }|;

then the image δ(P) of P in FD is precisely { f ∈ FD | d(f) = 0 }. There is an action of Z on FD by translations, given by t_{n}(f)(i) = f(i − n); informally speaking, t_{n}(f) is the same sequence as f, but with the reference mark ‘|’ shifted n places to the left. One has d(t_{n}(f)) = d(f) + n, so δ(P) is a set of representatives of the orbits of this action, which means that if a sequence without reference mark is given, there is a unique way to insert it to obtain a sequence δ(λ) for some λ ∈ P. Abusing the notation somewhat, we shall write δ^{−1}(f) = λ for any f ∈ FD in the orbit of δ(λ), i.e., in applying δ^{−1} we allow relocation of the reference mark if necessary. Remark. Clearly δ(λ) records information about the Young diagram λ “by diagonals” rather than by rows or columns. Individual edges however do not lie on diagonals of λ, but in between two successive ones. As the diagonal of a square (i, j) is naturally labelled by the integer j −i, the most natural indexing set for the bits of δ(λ) would seem to be Z + \frac{1}{2} rather than Z. On the other hand it is convenient to have the structure of Z available, such as the maps Z → Z/n. The natural order reversing involution of Z in this context is i ↦ −1 − i, which interchanges N and Z \ N, rather than i ↦ −i.

2.1. Other concepts related to edge sequences. One finds in the literature various concepts that are more or less equivalent to edge sequences, in the sense that they are in bijection by means of a straightforward translation with FD, or with some subset or its set of translation orbits. For the convenience of those acquainted with these concepts, we shall mention some of them, and detail the pertinent bijections. We shall start with various concepts mentioned in [14], some of which also occur in [8, 2.7], see also [15]. Firstly one associates to a partition λ of length l (i.e., l = λ_{0}^{t}) the set of its “first column hook lengths” X_{λ} = { λ_{i} + l − i − 1 | i = 0, …, l − 1 }, which equals (δ(λ)^{−1}(1) + l) ∩ N (note that the shift l is such that 0 is the smallest integer absent from δ(λ)^{−1}(1) + l). For r ≥ 0 the set X_{λ}^{+r} = { x + r | x ∈ X_{λ} }∪{0, …, r−1} is defined, which is simply (δ(λ)^{−1}(1)+l+r)∩N.

Each of these sets is a so-called β-set (a finite subset of N), and from any β-set X one recovers λ as δ^{−1}(f), where f ∈ FD is te characteristic function of the set X ∪ (Z \ N). The concept of “partition sequences” (which are doubly infinite words over {0, 1}) is almost equivalent to our edge sequences, with two differences: the rôles of 0 and 1 are interchanged, and, as no formal definition of (equality of) doubly infinite words is given in [14], partition sequences seem to correspond to translation orbits in FD. Olsson also defines partition sequences with a “cut”, which similar to our reference mark ‘|’, but it is used for a rather different purpose (namely to define Frobenius symbols).

The “Maya diagrams” of [3, §4] are introduced as sequences, indexed by Z, of black and white squares, such that all squares at sufficiently negative indices are black, and those at sufficiently positive indices are white; this is exactly equivalent to our definition of FD. The objects formally representing Maya diagrams are not maps Z → {0, 1} however, but permutations m of Z that have no descent except possibly between −1 and 0: one has m(i) > m(i − 1) for all i ≠ 0. Any f ∈ FD uniquely determines such a permutation, whose respective restrictions are the order preserving bijections Z \ N → f^{−1}(1) and N → f^{−1}(0); conversely one recovers f from m by f = δ_{0} ∘ m^{−1}. The “charge” of m is defined as lim_{i→±∞} m(i)−i, which is equal to d(f). Each Maya diagram determines an “infinite Young diagram” (a subset of Z × N), which encodes a finite Young diagram together with the charge of the Maya diagram; this corresponds to the fact that f ∈ FD is determined by δ^{−1}(f) and d(f).

2.2. Removal of hooks. The basic attributes of the Young diagram λ can be read off from f = δ(λ); the main concept used to do this is that of the hook. There is a hook h associated to each square (i, j) ∈ λ, namely the set h = { (i, j′) ∈ λ | j′ ≥ j } ∪ { (i′, j) ∈ λ | i′ ≥ i }; the number |h| is called its length. The segments of the boundary of λ that cross the ends of column j and of row i respectively correspond to the bits of δ(λ) at indices k = j − λ_{j}^{t} and l = λ_{i} − i − 1; we have k < l (in fact l − k = |h|), δ(λ)(k) = 0, and δ(λ)(l) = 1. Moreover, any such pair (k, l) comes from a unique hook h of λ. Therefore we define a hook of f ∈ FD to be a pair (k, l) with k < l, f(k) = 0, and f(l) = 1, and call l − k the length of this hook. We also define |f| to be the number of hooks of f, so that |δ(λ)| = |λ|.

Given a hook (k, l) of f ∈ FD, we define another sequence f′ ∈ FD by interchanging the bits at indices k and l: f′(k) = 1, f′(l) = 0, and f′(i) = f(i) for i ∉ {k, l}; f′ is said to be obtained by removing the hook (k, l) from f. One has d(f′) = d(f) and |f′| = |f| − (l − k) (for k < i < l, either (k, i) or (i, l) is a hook of f, but not of f′). If f = δ(λ) and h is the hook of λ corresponding to (k, l), then λ′ ∈ P with δ(λ′) = f′ can be obtained by removing h from λ, and then shifting the subset { (i′, j′) ∈ λ | i′ > i ∧ j′ > j } of the remainder one square up and to the left. The difference set λ \ λ′ is a connected sequence of squares along the outer rim of λ, with the same number of elements and the same end points as h; it is called the rim hook of λ corresponding to h, and λ′ is said to be obtained from λ by removing this rim hook. If |h| = 1, then the square of h is called a corner of λ, and a cocorner of λ′.

hook  (.11001\underline{0}0|10010\underline{1}0100.) (.11001\underline{1}0|10010\underline{0}0100.) rim hook

For r > 0 we define a partial ordering ‘≤_{r}’ on FD, which is generated by relations f′ ≤_{r} f whenever f′ is obtained from f by removing a hook of length r. Clearly f′ ≤_{r} f implies d(f′) = d(f), and each translation t_{n} is an isomorphism of the poset (FD, ≤_{r}). The corresponding partial ordering on P is also denoted by ‘≤_{r}’, and is generated by λ′ ≤_{r} λ whenever λ′ is obtained from λ by removing a rim hook of length r; the poset (P, ≤_{r}) is called the r-rim hook lattice. The ordering ‘≤_{1}’ on P coincides with the ordering ‘⊆’ defined by inclusion of Young diagrams, so the 1-rim hook lattice is just the Young lattice (P, ⊆). Whereas (P, ⊆) has a unique minimal element ∅, any translate t_{d}(δ_{0}) of δ(∅) is minimal in (FD, ≤_{1}), and for any f ∈ FD one has t_{d}(δ_{0}) ≤_{1} f with d = d(f). Hence the connected components of (FD, ≤_{1}) are the fibres of the surjection d: FD → Z, each of which is isomorphic to the Young lattice (P, ⊆).

Returning to the case of arbitrary r > 0, define S_{r}: FD → FD^{r} by splitting up the bits of a sequence f ∈ FD into r subsequences, according to the congruence class modulo r of their indices:

S_{r}(f) = (c_{0,r}(f), c_{1,r}(f), …, c_{r−1,r}(f)), where c_{i,r}(f)(n) = f(nr + i).

If f′ is obtained from f by removing a hook of length r, then S_{r}(f′) differs from S_{r}(f) only in one component c_{i,r}(f′), and there the difference is the interchange of two adjacent bits, i.e., removal of a hook of length 1. It follows that S_{r} is an isomorphism of posets (FD, ≤_{r}) → (FD, ≤_{1})^{r}. Therefore, the connected components of (FD, ≤_{r}) are the fibres of the surjection d^{r}: FD → Z^{r} defined by

d^{r}(f) = (d(c_{0,r}(f)), …, d(c_{r−1,r}(f))),

each of which is isomorphic to (P, ⊆)^{r}. In the fibre above (d_{0}, …, d_{r−1}) ∈ Z^{r}, the minimal element is S_{r}^{−1}(t_{d_{0}}(δ_{0}), …, t_{d_{r−1}}(δ_{0})). It follows easily from the definition of d that the sum of the r components of d^{r}(f) equals d(f) for any f ∈ FD; therefore δ is a poset isomorphism from (P, ≤_{r}) to the subposet of (FD, ≤_{r}) formed by the fibres of d^{r} above points (d_{0}, …, d_{r−1}) with ∑_{i=0}^{r−1} d_{i} = 0. Denoting the set of minimal elements of (P, ≤_{r}) by C_{r}, whose elements are called r-cores, we have

(P, ≤_{r}) ≅ ∐_{γ∈C_{r}}(P, ⊆)^{r}.  (4)

The r-core γ in the connected component of some λ ∈ (P, ≤_{r}) can be found as as follows: first compute (d_{0}, …, d_{r−1}) = d^{r}(δ(λ)), then γ = δ^{−1}(S_{r}^{−1}(t_{d_{0}}(δ_{0}), …, t_{d_{r−1}}(δ_{0}))). In terms of the edge sequence f = δ(λ) this amounts to sorting the bits in each subsequence c_{i,r}(f) seperately, removing all its hooks, so as to arrive at δ(γ) in which no hooks are left within any such subsequence. In the component labelled by γ at the right hand side of (4), λ corresponds to an r-tuple (λ^{(0)}, …, λ^{(r−1)}) ∈ P^{r} called its r-quotient. Its components are given by λ^{(i)} = δ^{−1}(c_{i,r}(δ(λ))) for i = 0, …, r − 1, where the convention mentioned above comes into play, that δ^{−1} will first translate its argument into δ(P). It can be seen that these methods of computing the r-core and r-quotient of λ are simplified forms of the abacus construction in [8, 7.2]; different (though equivalent) methods given in [4] (for the case γ = ∅ only) and in [2].

There is an alternative way to compute the map d^{r} ∘ δ: P → Z^{r}. For λ ∈ P define the Laurent polynomial diag(λ) = ∑_{(i,j)∈λ} x^{j−i}, which counts the squares of λ by diagonals (the sequence of its coefficients is called a “fairy sequence” f_{λ} in [4]). Then d^{r}(δ(λ)) will be the sequence of coefficients of the image of (1 − x^{−1}) diag(λ) in Z[x]/(1 − x^{r}) (this follows either by an easy induction on |λ|, or directly by considering the contribution of two successive diagonals numbered i, i + 1 to the coefficient of x^{i mod r}). In particular, the r-core of λ is determined by the image of diag(λ) in Z[x]/(1 − x^{r}) (i.e., by counting the squares of |λ| by diagonals modulo r), cf. [8, 2.7.41].

An example may illuminate our constructions. Consider the case r = 3 and λ = (8, 6, 6, 6, 5, 4, 1). We draw the Young diagram of λ, determine the edge sequence f = δ(λ), the three sequences c_{0,3}(f), c_{1,3}(f), c_{2,3}(f) constituting S_{3}(f), and the values of d applied to them:

λ: \begin{matrix}δ(λ): & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & d \\ c_{0,3}(δ(λ)): & & 1 & & & 1 & & & 0 & & & 1 & & & 1 & & & 0 & & & 0 & & +1 \\ c_{1,3}(δ(λ)): & & & 1 & & & 0 & & & 1 & & & 0 & & & 1 & & & 1 & & & 0 & +1 \\ c_{2,3}(δ(λ)): & 1 & & & 0 & & & 0 & & & 0 & & & 1 & & & 0 & & & 0 & & & −2 \end{matrix}

From this we see that d^{3}(δ(λ)) = (1, 1, −2), and it follows that the 3-core γ corresponding to λ is δ^{−1}(… 1 1 0 1 1 0|1 1 0 0 …) = (2, 2, 1, 1). The components of the 3-quotient (λ^{(0)}, λ^{(1)}, λ^{(2)}) of λ are computed from the subsequences c_{i,3}(δ(λ)) in the table: λ^{(0)} = δ^{−1}(… 1 1 0 1 1 0 0 …) = (1, 1), λ^{(1)} = δ^{−1}(… 1 0 1 0 1 1 0 …) = (2, 2, 1), and λ^{(2)} = δ^{−1}(… 1 0 0 0 1 0 0 …) = (3). Graphically we have

γ:  λ \ γ:  λ^{(0)}:  λ^{(1)}:  λ^{(2)}:

If one tries to repeatedly remove rim hooks of length 3 from λ in any order, then one will indeed find that it is eventually reduced to γ, which has no further rim hooks of length 3; the rim hooks that were removed form a tiling of λ \ γ. Using the alternative method of finding d^{3}(δ(λ)) one would first compute diag(λ) = x^{−6} + x^{−5} + 2x^{−4} + 3x^{−3} + 4x^{−2} + 4x^{−1} + 5 + 4x + 4x^{2} + 3x^{3} + 2x^{4} + x^{5} + x^{6} + x^{7}, multiply by 1−x^{−1} to obtain −x^{−7}−x^{−5}−x^{−4}−x^{−3}−x^{−1}+1+x^{2}+x^{3}+x^{4}+x^{7} (the relation of this polynomial to δ(λ) = (… 1 1 1 0 1 0 0 0 1 0|1 0 1 1 1 0 0 1 0 0 0 …) is easy to perceive), and determine its image 1 + x − 2x^{2} in Z[x]/(1 − x^{3}) is, which indeed gives d^{3}(δ(λ)) = (1, 1, −2).

2.3. Distribution of r-core sizes. In the isomorphism (4), adding a hook of length r to λ (the left hand side) corresponds to adding just a single corner from one of the partitions λ^{(i)} of its r-quotient (the right hand side); therefore |λ| = |γ| + r ∑_{i} |λ^{(i)}|. We have indicated above how the r-core γ can be found, but |γ| can be expressed directly in terms of the parameters (d_{0}, …, d_{r−1}) = d^{r}(δ(λ)). We have seen that δ(γ) is formed by splicing together r copies of δ_{0}, with copy i translated over d_{i}; therefore |γ| = |δ(γ)| can be computed by counting hooks in this sequence. We get

|γ| = ∑_{0≤i<j<r} \binom{d_{i} − d_{j}}{2};  (5)

the summand counts the hooks (k, l) of δ(γ) with either k ≡ j and l ≡ i (in case d_{i} > d_{j}) or with k ≡ i and l ≡ j modulo r (in case d_{i} ≤ d_{j}; note that \binom{d_{i}−d_{j}}{2} = \binom{1−d_{i}+d_{j}}{2}). Since δ(γ) has no hooks of length divisible by r, all hooks are counted. Using the fact that ∑_{i} d_{i} = 0, the formula simplifies to

|γ| = \frac{r}{2} (∑_{i=0}^{r−1} d_{i}^{2}) + ∑_{i=0}^{r−1} id_{i}  (6)

(cf. [7, Bijection 2]). For r = 2 there is only one parameter, so we may write d_{0} = −d_{1} = d, and get |γ| = \binom{2d}{2} = 2d^{2} − d. Since \binom{−2d}{2} = \binom{2d+1}{2}, we see that all triangular numbers occur exactly once as size of a 2-core; indeed the 2-cores are precisely the “staircase” partitions of the form (k, k − 1, …, 1) for k ≥ 0.

§3. Standard and semistandard ribbon tableaux.

3.1. Standard ribbon tableaux. As is well known, saturated chains in (P, ⊆) correspond to standard tableaux (see for instance [10]). The corresponding concept for (P, ≤_{r}) is that of r-ribbon tableaux.

3.1.1. Definition. Let r ≥ 1 and λ, μ ∈ P; a standard r-ribbon tableau S of shape λ/μ is a saturated chain μ = λ^{0} <_{r} λ^{1} <_{r} ⋯ <_{r} λ^{k} = λ in (P, ≤_{r}), together with a k-element totally ordered set A. The set of skew diagrams { λ^{i+1} \ λ^{i} | 0 ≤ i < k } is denoted by Rib(S), and its elements are called ribbons of S. The symbol S is also used to denote the unique bijection Rib(S) → A with S(λ^{i+1} \ λ^{i}) < S(λ^{j+1} \ λ^{j}) whenever i < j, and S(ξ) is called the entry of ξ in S, for ξ ∈ Rib(S).

Ribbon tableaux are sometimes called rim hook tableaux, but note that ξ ∈ Rib(S) need not be a rim hook of λ, only of some λ^{i}. By itself a ribbon of any standard r-ribbon tableau is called an r-ribbon, or in case r = 2 alternatively a domino; 2-ribbon tableaux are also called domino tableaux.

Note. Although the same symbol is used, we do not identify S with the bijection Rib(S) → A, which determines λ \ μ but not necessarily λ and μ themselves. The distinction is necessary because we shall perform constructions that require explicit knowledge of λ and μ. A price we pay is that our tableaux cannot be translated in the plane, or involve squares outside N × N.

We shall display a ribbon tableau by drawing each ribbon with its entry placed in it. Unless the shape λ/μ is explicitly given, this leaves some ambiguity (even about the location of the origin), but in such cases we shall assume that μ has the smallest possible value. Here for instance is a standard 3-ribbon tableau of the shape λ/γ in the example given earlier, and with set of entries A = {0, 1, …, 9}.

S:  0 1 2 3 4 5  6  7 8 9

We now introduce some terminology related to individual ribbons. Let ξ = ν \ ν′ be an r-ribbon, then δ(ν′) is obtained from δ(ν) by removing some hook (k, l) of length l − k = r; we write l = pos(ξ), and call it the position of ξ. We have

pos(ξ) = max { j − i | (i, j) ∈ ξ },

the number of the rightmost diagonal meeting ξ; in particular for r = 1, the position of a square is just the number of the diagonal it lies on. We also define the form of ξ to consist of the bits of δ(ν) (or equivalently of δ(ν′)) at the indices between k and l:

form(ξ) = (δ(ν)(k + 1), …, δ(ν)(l − 1)) ∈ {0, 1}^{r−1}.

The bits of form(ξ) describe for each pair of successive squares of ξ whether they are horizontally or vertically adjacent. For r = 2 we call the two possible forms of dominoes simply horizontal (form(ξ) = (0)) and vertical (form(ξ) = (1)). Finally, we define the height of ξ, written ‘ht(ξ)’, as the sum of the bits of form(ξ), in other words the number of vertical adjacencies among the squares in ξ, or one less than the number of rows that meet ξ.

3.1.2. Proposition. Let r > 0, λ, μ ∈ P with μ ≤_{r} λ, and A a totally ordered set with |λ \ μ| = r|A|; let (λ^{(0)}, …, λ^{(r−1)}) and (μ^{(0)}, …, μ^{(r−1)}) be the r-quotients of λ and μ, and let d^{r}(δ(λ)) = d^{r}(δ(μ)) = (d_{0}, …, d_{r−1}). There is a bijection between the set of standard r-ribbon tableaux S of shape λ/μ with entries in A, and the set of r-tuples (S_{0}, …, S_{r−1}) of ordinary standard tableaux, where S_{i} has shape λ^{(i)}/μ^{(i)}, and the sets of entries of the S_{i} are mutually disjoint, and unite to A. If x is a square of λ^{(i)} \ μ^{(i)}, then S_{i}(x) = S(ξ) for a ξ ∈ Rib(S) with pos(ξ) = r(pos(x) + d_{i}) + i.

Proof. The existence of the bijection is immediate from (4): each (S_{0}, …, S_{r−1}) corresponds to a saturated chain in (P, ⊆)^{r} from (μ^{(0)}, …, μ^{(r−1)}) to (λ^{(0)}, …, λ^{(r−1)}). Since c_{i,r}(δ(λ)) = t_{d_{i}}(δ(λ^{(i)})) by the explicit description of the isomorphism (4), a bit δ(λ^{(i)})(l) is equal to c_{i,r}(δ(λ))(l + d_{i}), which in turn equals δ(λ)(r(l + d_{i}) + i); from this the relation between pos(x) and pos(ξ) follows.

For the case of an empty r-core (i.e., d_{i} = 0 for all i) our bijection coincides with the map Π of [16, Corollary 23]. As an example, consider the tableau S depicted above; we have λ/μ = (8, 6, 6, 6, 5, 4, 1)/(2, 2, 1, 1) so that λ^{(0)} = (1, 1), λ^{(1)} = (2, 2, 1), and λ^{(2)} = (3), all μ^{(i)} are ∅ (since μ is a 3-core), and d^{3}(δ(λ)) = (1, 1, −2). The successive ribbons have positions 3, 4, 1, −2, 0, −4, −1, 7, 2, 4, so that entries 0 and 4 will end up in S_{0} with positions 0 and −1, entries 1 ,2, 3, 7, and 9 in S_{1} with positions 0 ,−1, −2, 1, and 0, and entries 5, 6, and 8 in S_{2} with positions 0, 1, and 2; we find

S_{0}: 0 4  S_{1}: 1 7 2 9 3  S_{2}: 5 6 8 .

3.2. Semistandard ribbon tableaux. In analogy of the situation for ordinary tableaux, we define, in addition to standard domino tableaux, semistandard r-ribbon tableaux, in which multiple occurrences of the same entry are allowed. They will allow a decomposition similar to proposition 3.1.2, but without the condition of disjointness of the sets or entries. In combination with the fact that the generating function of all ordinary semistandard tableaux of given shape and range of entries, weighted by the multiset of their entries, is a Schur function, this will imply that semistandard r-ribbon tableaux satisfy a similar generating function identity.

In view of the desired decomposition, we shall base our definition of semistandard r-ribbon tableaux on their standardisation, rather than on (weak and strict) monotonicity conditions for rows and columns, as is usually done for ordinary semistandard tableaux (for r = 2 such a definition is still possible however, see [2], and it is equivalent to the one we shall give). Loosely speaking, the standardisation of a semistandard tableau is a standard tableau obtained from it by renumbering its entries such that the relative order of distinct entries is preserved, and equal entries are made increasing from left to right. A condition is needed to ensure that there is a well defined left to right ordering among ribbons with equal entries: we require such ribbons to have distinct positions, and ordering them by increasing position should give a valid standard tableaux. For ordinary tableaux this is equivalent to requiring weak increase of entries along rows, and strict increase down columns.

3.2.1. Definition. Let a standard r-ribbon tableau S of shape λ/μ with entries { i ∈ N | i < k } be given, and a sequence ω = (m_{0}, m_{1}, …) with all m_{i} ∈ N and ∑ m_{i} = k. These define a semistandard r-ribbon tableau T of shape λ/μ, with for each ξ ∈ Rib(T) the entry T (ξ) defined as the unique j ∈ N such that ∑_{i<j} m_{i} ≤ S(ξ) < ∑_{i≤j} m_{i}, provided that for all ξ, ξ′ ∈ Rib(T) with T (ξ) = T (ξ′) and S(ξ) < S(ξ′), one has pos(ξ) < pos(ξ′). In this case S is called the standardisation of T, and ω its weight wt(T), and we define Rib(T) = Rib(S).

In the literature the weight is also called content or evaluation. Our definition is equivalent to the one in [9, §4]. We shall write Tab_{r}(λ/μ) for the set of semistandard r-ribbon tableaux of shape λ/μ, and Tab_{r}(λ/μ; A) for its subset of tableaux whose entries lie in A ⊆ N. Also, for any weight ω = (m_{0}, m_{1}, …) we shall write x^{ω} = ∏_{i} x_{i}^{m_{i}}, where { x_{i} | i ∈ N } is a set of commuting indeterminates. Here is an example, giving a semistandard 4-ribbon tableau T of shape (7, 7, 7, 7, 7, 5)/(4) with x^{wt(T)} = x_{1}^{4}x_{2}^{3}x_{5}^{2}:

S = 0 1 2 3 4 5  6 7 8 ,  ω = (0, 4, 3, 0, 0, 2),  T = 1 1 1 1 2 2  2 5 5 .

3.2.2. Proposition. Let r > 0, and λ, μ ∈ P with μ ≤_{r} λ; let (λ^{(0)}, …, λ^{(r−1)}) and (μ^{(0)}, …, μ^{(r−1)}) be the r-quotients of λ and μ. There is a natural bijection between the set of semistandard r-ribbon tableaux T of shape λ/μ, and the set of r-tuples (T_{0}, …, T_{r−1}) of ordinary semistandard tableaux, with T_{i} of shape λ^{(i)}/μ^{(i)}, and ∑_{i=0}^{r−1} wt(T_{i}) = wt(T). If S is the standardisation of T, so that T (ξ) = f(S(ξ)) for an appropriate weakly monotonic map f, and S corresponds under the bijection of proposition 3.1.2 to (S_{0}, …, S_{r−1}), then T_{i}(x) = f(S_{i}(x)) for each square x ∈ λ^{(i)}/μ^{(i)}.

Proof. The final sentence completely determines each T_{i}, so it will suffice to show that these T_{i} are semistandard tableaux, and that the correspondence is invertible. Let x, y ∈ λ^{(i)}/μ^{(i)} be such that T_{i}(x) = T_{i}(y) and S_{i}(x) < S_{i}(y), and define ξ, ξ′ ∈ Rib(S) = Rib(T) by S(ξ) = S_{i}(x) and S(ξ′) = S_{i}(y). Then T (ξ) = T (ξ′), so that pos(ξ) < pos(ξ′), while pos(ξ) ≡ pos(ξ′) ≡ i modulo r; therefore by proposition 3.1.2 we have pos(x) < pos(y), and T_{i} is semistandard. For invertibility we need to order all the occurrences of the same entry in any of the tableaux T_{i}, in order to determine the S_{i}; proposition 3.1.2 makes clear that these occurrences T_{i}(x) should be ordered by increasing value of r(pos(x) + d_{i}) + i.

As an example, the semistandard 4-ribbon tableau T displayed above corresponds to

T_{0}: 1 5  T_{1}: 1 1  T_{2}: 1 2 2 5  T_{3}: 2 .

3.2.3. Corollary. Let r > 0, let λ, μ ∈ P with μ ≤_{r} λ and respective r-quotients (λ^{(0)}, …, λ^{(r−1)}) and (μ^{(0)}, …, μ^{(r−1)}), and let A be a finite initial subset of N. One has

∑_{T ∈Tab_{r}(λ/μ;A)} x^{wt(T)} = ∏_{i=0}^{r−1} s_{λ^{(i)}/μ^{(i)}}(x_{A}),

where s_{λ/μ}(x_{A}) denotes the skew Schur function for λ/μ in the indeterminates { x_{i} | i ∈ A }.

Proof. Proposition 3.2.2 reduces the general case to the well known case r = 1 ([12, I (5.12)]).

3.3. Signs and spins.

Propositions 3.1.2 and 3.2.2 translate many properties of ribbon tableaux in a trivial way to those of ordinary tableaux. However, the values form(ξ) and ht(ξ) for ξ ∈ Rib(T) cannot be easily expressed in terms of the tableaux T_{0}, …, T_{r−1} that T decomposes into, and in particular the quantity ∑_{ξ∈Rib(T)} ht(ξ) provides an interesting statistic.

3.3.1. Proposition. The parity of ∑_{ξ∈Rib(T)} ht(ξ) is constant on each set Tab_{r}(λ/μ).

Proof. Fix r, and defining V (λ) = δ(λ)^{−1}(1) = { λ_{i} − i − 1 | i ∈ N }, let f_{λ/μ}: V (μ) → V (λ) be defined by the condition that for each congruence class C modulo r, the restriction of f_{λ/μ} to V (μ) ∩ C is an order preserving bijection onto V (λ) ∩ C. It is clear that for any chain μ = λ^{0} <_{r} λ^{1} <_{r} ⋯ <_{r} λ^{k} = λ in (P, ≤_{r}) one has f_{λ/μ} = f_{λ^{k}/λ^{k−1}} ∘⋯∘f_{λ^{2}/λ^{1}} ∘f_{λ^{1}/λ^{0}}, and that if λ\μ is an r-ribbon ξ, then the number of inversions of f_{λ/μ} (i.e., pairs i < j with f_{λ/μ}(i) > f_{λ/μ}(j)) is ht(ξ). Since for composition of bijections between totally ordered sets, the parity of the number of inversions is additive, the proposition follows.

3.3.2. Definition. For μ ≤_{r} λ and T ∈ Tab_{r}(λ/μ), the spin of T is Spin(T) = \frac{1}{2} ∑_{ξ∈Rib(T)} ht(ξ), and the r-sign of λ/μ is ε_{r}(λ/μ) = (−1)^{2 Spin(T)}, which is independent of T by proposition 3.3.1.

This spin statistic generalises the one defined for domino tableaux in [2, §3]; a discussion of r-signs can also be found in [13, §2]. Spin(T) lies in N or in N + \frac{1}{2} according as ε_{r}(λ/μ) is +1 or −1, and a lower bound for it is half the number of inversions of the map f_{λ/μ} in the proof above.

§4. Affine permutations and chains in ribbon tableaux.

4.1. Action of the affine Coxeter group of type Ã_{r−1}. From this point on we shall assume r ≥ 2, and all congruences mentioned will be modulo r. From the isomorphism (4) it follows that the poset (P, ≤_{r}) has very many automorphisms, in fact continuously many. We shall consider here a subgroup of automorphisms that is of particular interest.

4.1.1. Definition. S̃_{r} is the group of permutations σ of Z which preserve, for any system S of representatives of Z/r, the sum of its values: ∑ S = ∑ σ(S).

By replacing one representative by another, we see that σ(i + r) = σ(i) + r for all i ∈ Z, so that σ maps congruence classes to congruence classes, and S̃_{r} is indeed a group; moreover, its action on Z induces an action on Z/r. Every bijection σ̄: S → S′ between two systems of representatives of Z/r with ∑ S = ∑ S′ can be extended to a unique σ ∈ S̃_{r} by using σ(i+r) = σ(i)+r. The group S̃_{r} is isomorphic to the affine Coxeter group of type Ã_{r−1}, see [1]. This is the group with generators s_{0}, s_{1}, …, s_{r−1}, subject to the relations s_{i}^{2} = e for all i, s_{i}s_{j} = s_{j}s_{i} for j ≢ i ± 1, and if r ≠ 2 also s_{i}s_{j}s_{i} = s_{j}s_{i}s_{j} for j ≡ i ± 1. In a slight deviation from [1], we take for s_{i} the element of S̃_{r} that interchanges i − 1 and i, and fixes all other congruence classes; the Coxeter relations are verified immediately.

4.1.2. Proposition. The group S̃_{r} acts on (FD, ≤_{r}) by automorphisms; the action is by permutation of the bits: (σ(f))(i) = f(σ^{−1}(i)) for σ ∈ S̃_{r}, f ∈ FD and i ∈ Z. One has d(σ(f)) = d(f) for all σ ∈ S̃_{r} and f ∈ FD, so the restriction to δ(P) induces and action of S̃_{r} on (P, ≤_{r}) by automorphisms.

Proof. We have σ(f) ∈ FD because |σ(i) − i| is bounded for any σ ∈ S̃_{r}; to see that the action of σ is an automorphism of (FD, ≤_{r}), it suffices to check that if f′ is obtained from f by removal of a hook (i, i + r), then σ(f′) is obtained from σ(f) by removal of the hook (σ(i), σ(i + r)) = (σ(i), σ(i) + r). The fact that d is an invariant of the action is shown by verification for each of the generators s_{i}.

Let us describe the action of a generator s_{j} on P more explicitly. For any i ≡ j, the interchange of the bits of δ(λ) at indices i − 1 and i has no effect unless these bits differ, i.e., unless λ has either a corner or a cocorner in diagonal i; if so, the effect is to remove the corner, respectively to add the cocorner. Now s_{j} performs this operation for all diagonals congruent to j at once, so s_{j}(λ) is obtained from λ by removing those of its corners c, and adding those of its cocorners c, that have pos(c) ≡ j.

4.1.3. Proposition. If σ ∈ S̃_{r}, and λ ∈ P has r-core γ and r-quotient (λ^{(0)}, …, λ^{(r−1)}), then σ(λ) has r-core σ(γ) and r-quotient (λ^{(σ^{−1}(0))}, …, λ^{(σ^{−1}(r−1))}), interpreting superscripts to λ as elements of Z/r.

Proof. This follows immediately from (the explicit description of) the isomorphism (4).

The action of S̃_{r} on P can be restricted to C_{r}; the generators act as follows in terms of the parametrisation provided by d^{r} ∘ δ: C_{r} → Z^{r}. Let γ ∈ C_{r} have parameters (d_{0}, …, d_{r−1}), then s_{j}(γ) has parameters (d_{0}, …, d_{j}, d_{j−1}, …, d_{r−1}) if j ≠ 0, while s_{0}(γ) has parameters (d_{r−1} + 1, d_{1}, …, d_{r−2}, d_{0} − 1). Therefore this action of S̃_{r} on C_{r} corresponds precisely to the standard action of S̃_{r} by affine transformations of the root lattice of the Weyl group of type A_{r−1}. In particular, the action is transitive, and since the stabiliser of ∅ ∈ C_{r} is ⟨s_{1}, …, s_{r−1}⟩ ≅ S_{r}, it gives a bijection between C_{r} and S̃_{r}/S_{r}. It is shown in [1, Theorem 6.3] that partial ordering ‘⊆’ on C_{r} corresponds to the Bruhat order on S̃_{r}/S_{r} (the “unit increase monotonic function” φ corresponding to γ is given by φ(j) = |{ i ∈ Z | i < j − 1 ∧ δ(γ)(i) = 0 }|).

4.1.4. Proposition. The action of S̃_{r} on (P, ≤_{r}) induces an action on standard r-ribbon tableaux, such that σ ∈ S̃_{r} sends standard r-ribbon tableaux of shape λ/μ to standard r-ribbon tableaux of shape σ(λ)/σ(μ), with the same set of entries; if the chain in (P, ≤_{r}) of a standard r-ribbon tableau S is λ^{0} <_{r} ⋯ <_{r} λ^{k} in (P, ≤_{r}), then σ(S) has the chain σ(λ^{0}) <_{r} ⋯ <_{r} σ(λ^{k}). Using proposition 3.1.2, if S corresponds to (S_{0}, …, S_{r−1}) by the bijection for λ/μ, then σ(S) corresponds to (S_{σ^{−1}(0)}, …, S_{σ^{−1}(r−1)}) (with the subscripts interpreted in Z/r) by the bijection for σ(λ)/σ(μ).

Since the ribbon ξ = λ^{i+1} \ λ^{i} ∈ Rib(S) corresponds to the ribbon ξ′ = σ(λ^{i+1}) \ σ(λ^{i}) ∈ Rib(σ(S)), it seems that σ acts independently on each individual ribbon. However, this is not true, since ribbons are just skew diagrams, and so ξ does not uniquely determine λ^{i} and λ^{i+1}; for other pairs of partitions ν, ν′ with ξ = ν \ ν′ one may have σ(ν) \ σ(ν′) ≠ ξ′.

To better understand the situation, consider the case that σ is a generator s_{j}. From the description of the action of s_{j} on P it follows that for any square x with pos(x) ≢ j, one has x ∈ λ if and only if x ∈ s_{j}(λ), and therefore x ∈ ξ if and only if x ∈ ξ′; we shall call such squares fixed for s_{j}. All but one of the squares of ξ are fixed, so ξ′ can only differ from ξ by the replacement of its non-fixed square by another one. Now pos(ξ′) = s_{j}(pos(ξ)), which differs from pos(ξ) if either pos(ξ) ≡ j − 1 or pos(ξ) ≡ j, so if this non-fixed square lies at one of the ends of the ribbon ξ, it will be replaced by a square at the other end; otherwise the only possible change is the replacement of a square by another one on the same diagonal. In the latter case form(ξ′) is in fact obtained from form(ξ) by interchanging two adjacent bits, and the indicated change happens whenever these two bits differ; in particular ξ′ is determined by ξ alone. In the cases where pos(ξ′) ≠ pos(ξ), the bits of form(ξ′) are those of form(ξ) shifted one place left or right, with a bit disappearing at the side of the non-fixed square of ξ, and an unrelated bit appearing at the other end. This new bit is what makes ξ′ depend on λ^{i+1}/λ^{i} in this case, rather than just on ξ.

The new bit that enters into form(ξ′) is a bit of δ(λ^{i+1}), just outside the hook (k, l) whose removal leads to δ(λ^{i}) (so l = pos(ξ) and k = l − r): it is δ(λ^{i+1})(l + 1) if pos(ξ) ≡ j − 1, or δ(λ^{i+1})(k − 1) if pos(ξ) ≡ j (this bit is unaffected by the hook removal, so one may replace λ^{i+1} by λ^{i} in these expressions). In this situation we define the fixed-end square of ξ to be the square at the opposite end of ξ as its nonfixed square, and the discriminant square of ξ to be the next square in the same anti-diagonal in the direction away from ξ, i.e., one place above and to the right of the fixed-end square if pos(ξ) ≡ j − 1, or one place below and to the left of it if pos(ξ) ≡ j; like the fixed-end square, the discriminant square is fixed for s_{j}. The value of the new bit of ξ′ is determined by whether or not the discriminant square x of ξ lies in N × N \ λ^{i}. If x ∈ ξ_{0} for some ξ_{0} ∈ Rib(S), then this question is equivalent to S(ξ_{0}) > S(ξ); otherwise x ∉ λ \ μ, and the question is equivalent to x ∈ N × N \ λ (here the shape λ/μ of S is explicitly used). If in the former case the ribbons ξ and ξ_{0} are adjacent along at least one edge, then this adjacency already determines whether S(ξ_{0}) > S(ξ), so a comparison of entries of S is needed only if ξ and ξ_{0} are non-adjacent; in that case, the discriminant square of ξ is also the fixed-end square of ξ_{0} and vice versa.

As an example we take the 3-ribbon tableau S shown before, and j = 0. For each ξ ∈ Rib(S) with ξ′ ≠ ξ, we draw an arrow either from the non-fixed square of ξ (if pos(ξ′) = pos(ξ)), or from the fixed-end square of ξ (otherwise), to the square in ξ′ \ ξ. We have similarly drawn arrows in s_{0}(S) for the reverse transformation.

S:  0 ←  1 ↖ 2 3 ↖ 4 ← 5 → 6 ↑  7 8 ↑ 9  \underleftrightarrow{s_{0}}  0→1↘ 2 3↘ 4→ 5 ↓  6 ←  7 8 ↓ 9

Of the ribbons ξ ∈ Rib(S) with pos(ξ) ≡ 1, the straight ones (with entries 2, 7 and 9) are unchanged, while for the bent ones (1 and 3) the middle square moves within its diagonal. The ribbons 5, 6 and 8 with pos(ξ) ≡ 2 move one place to the top right; the ribbons 0 and 4 with pos(ξ) ≡ 0 move to the bottom left. The discriminant squares of the ribbons with entries 0, 4, 5, 6, 8 lie in the ribbons with entries 2, 5, 4, 8, 9 respectively; the ribbons whose entries are compared are non-adjacent only for the entries 4 and 5. In s_{0}(S) the ribbons with entries 0, 5, and 6 have a discriminant square that does not lie in any ribbon; for the ribbon with entry 5, the effect of applying s_{0} cannot be determined from the display of the tableau alone (without indication of the origin or of the shape λ/μ of the tableau).

4.2. Open and closed chains of ribbons.

From the discussion above it can be seen that it may be possible to obtain a valid ribbon tableau from S by replacing only a subset of its ribbons by their corresponding ribbons in s_{j}(S); the minimal non-empty subsets of Rib(S) with this property are essentially what we shall call the chains in S for s_{j} (not to be confused with the chain in (P, ≤_{r}) of S). In the tableau S above, the chains are the sets of ribbons with entries {8, 1, 0}, {5, 6, 4, 3}, and the singletons {2}, {7}, {9} for ribbons that do not move. There is in fact more structure to a chain than just that of a set of ribbons: if for a ribbon ξ_{0} ∈ Rib(S) its corresponding ribbon ξ′_{0} ∈ Rib(s_{j}(S)) has one square in common with ξ_{1} ∈ Rib(S), then ξ_{1} can be considered to be the successor of ξ_{0} in its chain in S for s_{j}; therefore chains will be formally defined in a slightly different way. For r = 2, the partition of Rib(S) into chains has been described elsewhere: chains coincide with the cycles in a domino tableau in [5, (1.5.18)], and with the connected components in the labyrinth of a domino tableau in [2, §8]. While our definitions are more general, the case r = 2 remains of particular interest, and has special properties not valid for r > 2.

Denote by D_{j}(λ/μ) the set of squares x with pos(x) ≡ j that either lie in λ \ μ or are a cocorner of λ or a corner of μ. Let a bipartite graph G_{j}(S) on Rib(S) ∪ D_{j}(λ/μ) de defined as follows: for a ribbon ξ = λ^{i+1} \ λ^{i} ∈ Rib(S) with corresponding ribbon ξ′ = s_{j}(λ^{i+1}) \ s_{j}(λ^{i}) ∈ Rib(s_{j}(S)), there is an edge labelled 0 between ξ and x ∈ D_{j}(λ/μ) whenever x ∈ ξ, and an edge labelled 1 whenever x ∈ ξ′. Then the chains in S for s_{j} are defined as connected components of G_{j}(S). The valency in G_{j}(S) of any vertex in Rib(S) is 2: it has one edge labelled 0 and one labelled 1. For a vertex x ∈ D_{j}(λ/μ) the valency is at most 2 (at most one edge with either label), which value is assumed if and only if x ∈ (λ \ μ) ∩ (s_{j}(λ) \ s_{j}(μ)). If for x ∈ D_{j}(λ/μ) there is an edge labelled 1 to ξ, and an edge labelled 0 to ξ′, with ξ′ ≠ ξ, then ξ′ is called the successor of ξ for s_{j}. The subset of vertices in D_{j}(λ/μ) with no edge labelled 1 will be denoted by d^{−}, which is the disjoint union of d_{o}^{−} = λ\s_{j}(λ) and d_{i}^{−} = s_{j}(μ)\μ, and the subset of vertices in D_{j}(λ/μ) with no edge labelled 0 by d^{+}, which is the disjoint union of d_{o}^{+} = s_{j}(λ) \ λ and d_{i}^{+} = μ \ s_{j}(μ).

A chain will be called open if it has some vertex with valency less than 2, and closed otherwise. Of the vertices with valency less than 2 in an open chain there is one in d^{−}, called the starting square of the chain, and one in d^{+}, called the ending square of the chain; when these coincide the chain contains no ribbons, and is called empty. A closed chain either consists of a ribbon and a square linked by two edges, in which case the chain is called trivial, or of a single cycle containing at least 2 ribbons.

For any chain C in S for s_{j}, a new tableau S′ can be formed by moving the chain C. It is obtained by modifying each partition λ^{i} of the saturated chain λ^{0} <_{r} ⋯ <_{r} λ^{k} in (P, ≤_{r}) of S as follows: each square that occurs as a vertex of C and is a corner or cocorner of λ^{i} is removed from respectively added to λ^{i}. This means that a ribbon ξ ∈ Rib(S) changes if and only if it occurs in C, in which case it is replaced by the corresponding ribbon ξ′ ∈ Rib(s_{j}(S)), i.e., the square joined in C to ξ by an edge labelled 0 is removed from it, and the square joined to it by an edge labelled 1 is added. It is easily verified that S′ is indeed a standard r-ribbon tableau. In the cases where C is an empty or a trivial chain,, the ribbons of S′ and their entries are the same as for S; however, S′ = S holds only if C is a trivial chain, since for empty chains the shape λ/μ is replaced by another shape, although the skew diagram λ\μ containing the ribbons does not change. Because distinct chains in S for s_{j} are disjoint, the operations of moving them commute mutually, and moving all of them gives s_{j}(S). After moving a chain in S for s_{j}, its modified ribbons again form a chain for s_{j}, and moving that chain gives back S.

We have seen above how chains can be located by finding for each ribbon the square connected to it in G_{j}(S) by an edge labelled 1; one may also work in the opposite direction, and find for each square x ∈ G_{j}(S) \ d^{−} the ribbon connected to it by an edge labelled 1. Excluding the easy case that x is part of a trivial chain, the choice is either between the ribbons containing the two neighbouring squares of x in the outward direction, or those in the inward direction: if x ∈ d^{+} only one direction is possible, and otherwise x ∈ ξ for some ξ ∈ Rib(S), and the direction that contains another square of ξ is not considered. The choice between the neighbours of x in the proper direction is given by a rule very similar to that of jeu de taquin: if there is only one candidate ribbon, it wins, and if there are two candidates, the one with the smallest entry wins in case of outward neighbours, and the one with the largest entry in case of inward neighbours. Like the rule for jeu de taquin, this rule just reflects the requirement that the change preserves the tableau condition. Note that here the shape λ/μ of S is used only to determine the set of squares x to consider in the first place, not in finding the indicated ribbon for given x.

4.3. Chains in semistandard r-ribbon tableaux.

4.3.1. Proposition. Let T be a semistandard r-ribbon tableau, C a chain in its standardisation S for s_{j}, and S′ the standard r-ribbon tableau obtained by moving C in S. There is another semistandard r-ribbon tableau T′ with standardisation S′ and wt(T′) = wt(T), said to be obtained by moving C in T, unless C is a closed chain with exactly 2 ribbons ξ, η, with T (ξ) = T (η).

Proof. Assume that S′ and wt(T) do not define a semistandard r-ribbon tableau; this means that there are ξ, η ∈ Rib(S) with S(η) = S(ξ) + 1 and T (ξ) = T (η), so that pos(ξ) < pos(η), while the corresponding dominoes ξ′, η′ ∈ Rib(S′) have pos(ξ′) ≥ pos(η′). Because the positions of ribbons change by at most 1 when moving a chain, and consecutive ribbons cannot have equal positions, we must have that both ξ and η occur in C, and pos(η) = pos(ξ) + 1 = pos(ξ′) while pos(η′) = pos(ξ′) − 1. Therefore ξ ∪ η = ξ′ ∪ η′, so C is indeed a closed chain, with {ξ, η} as its set of ribbons.

We define the chains for s_{j} in a semistandard r-ribbon tableau to be those in its standardisation, but the ones excluded in proposition 4.3.1 will be called forbidden chains. The proposition shows that no action of S̃_{r} on semistandard r-ribbon tableaux can be defined that commutes with taking the standardisation. However, the second part of proposition 4.1.4 provides a way to define an action of S̃_{r} on semistandard r-ribbon tableaux, if one uses the bijections of proposition 3.2.2 instead of proposition 3.1.2. This action can also be described as follows, using the fact that a semistandard r-ribbon tableau T is completely determined by specifying its shape λ/μ and for each entry i the set pos_{i}(T) = { pos(ξ) | ξ ∈ Rib(T) ∧ T (ξ) = i }. For σ ∈ S̃_{r} the shape of σ(T) is σ(λ)/σ(μ) and one has pos_{i}(σ(T)) = { σ(p) | p ∈ pos_{i}(T) }. The effect of the generators s_{j} of S̃_{r} can be understood in terms of moving chains: one can obtain s_{j}(T) from T by moving all its chains for s_{j} except the forbidden ones. To see this, consider the list of integers pos(ξ), for all ξ ∈ Rib(T) in order of increasing entries in the standardisation of T; this is just a concatenation of all pos_{i}(T) for increasing i, with the elements within each pos_{i}(T) arranged in increasing order. Now the analogous list for s_{j}(T) can be obtained by applying s_{j} to each of the the numbers in the original list, except that the elements within each pos_{i}(T) may need to be reordered to keep them increasing. Since |s_{j}(i) − i| ≤ 1 for all i, this is only needed when pos_{i}(T) contains two consecutive numbers that are interchanged by s_{j}, and reordering will return this pair of numbers to their original state (before s_{j} was applied). Such pairs correspond precisely to forbidden chains in T for s_{j}, and the specialisation of s_{j}(T) differs from the result of applying s_{j} to the specialisation of T only in the fact that the ribbons of such chains have remained in their original positions in T. We summarise our findings as follows.

4.3.2. Proposition. There is a weight preserving action of S̃_{r} on the set of semistandard r-ribbon tableaux, such that s_{j}(T) is obtained from T by moving all its chains for s_{j} except the forbidden ones. For σ ∈ S̃_{r} we have, using proposition 3.2.2, that if T corresponds to (T_{0}, …, T_{r−1}) by the bijection for λ/μ, then σ(T) corresponds to (T_{σ^{−1}(0)}, …, T_{σ^{−1}(r−1)}) (with the subscripts interpreted in Z/r) by the bijection for σ(λ)/σ(μ).

4.4. Chains and spin change. For an r-ribbon tableau, the sets d^{−} and d^{+} of starting and ending squares of its open chains for s_{j} depend only on its shape λ/μ. When building up the tableau by successive addition of ribbons in order of increasing entries, the sets d_{i}^{−} and d_{i}^{+} do not change (they depend only on μ), while the changes to d_{o}^{−} and d_{o}^{+} are directly related to the way the set of chains for s_{j} evolves. Initially, when the shape is μ/μ (no ribbons), d_{o}^{−} = d_{i}^{+} is the set of corners x of μ with pos(x) ≡ j, and d_{o}^{+} = d_{i}^{−} is the analogous set of cocorners; there is one empty chain for each element of d^{−} = d^{+}. Now assume the shape is λ/μ and a ribbon ξ = λ′ \ λ is added; put ξ′ = s_{j}(λ′) \ s_{j}(λ). If pos(ξ) = pos(ξ′), then the only possible change to d_{o}^{−} or d_{o}^{+} is the replacement of a square by the next one on the same diagonal, which happens if that diagonal meets ξ; if so ξ joins the chain starting or ending in that square, and otherwise ξ becomes a trivial chain. If pos(ξ) ≠ pos(ξ′), let x ∈ ξ and y ∈ ξ′ be the non-fixed squares (so |pos(x) − pos(y)| = r), and distinguish the cases where 0, 1, or 2 of them lie in d_{o}^{−} ∪ d_{o}^{+}. If neither of them does, then x and y are added respectively to d_{o}^{−} and d_{o}^{+}, and ξ starts a new open chain, starting in x and ending in y. If one of them lies in d_{o}^{−} ∪ d_{o}^{+}, then ξ joins the open chain that starts or ends at that square, which square is replaced by the other one of {x, y} as element of d_{o}^{−} or d_{o}^{+}. If both x and y lie in d_{o}^{−} ∪ d_{o}^{+}, then x is removed from d_{o}^{+} and y from d_{o}^{−}, and there are two further possibilities, depending on whether or not the chains starting in y and ending in x coincide. If they do, then ξ joins that chain and transforms it to a closed chain; otherwise ξ joins the two chains to a single open chain. When a closed chain is formed, we say that it moves counter-clockwise if pos(x) < pos(y), and clockwise if pos(y) < pos(x).

4.4.1. Proposition. Let T be a (semi)standard r-ribbon tableau, and let T′ be obtained from T by moving a chain C in T for s_{j}, then Spin(T) and Spin(T′) are related according to the following cases.

1. C is an open chain, with starting square x and ending square y. a. Either x ∈ d_{o}^{−} and y ∈ d_{i}^{+} or x ∈ d_{i}^{−} and y ∈ d_{o}^{+}: Spin(T′) = Spin(T). b. Either x ∈ d_{o}^{−}, y ∈ d_{o}^{+} and pos(x) > pos(y), or x ∈ d_{i}^{−}, y ∈ d_{i}^{+} and pos(x) < pos(y):

Spin(T′) = Spin(T) + \frac{1}{2}. c. Either x ∈ d_{o}^{−}, y ∈ d_{o}^{+} and pos(x) < pos(y), or x ∈ d_{i}^{−}, y ∈ d_{i}^{+} and pos(x) > pos(y):

Spin(T′) = Spin(T) − \frac{1}{2}.

2. C is a closed chain.

a. C moves counter-clockwise: Spin(T′) = Spin(T) + 1.

b. C moves clockwise: Spin(T′) = Spin(T) − 1.

Proof. This follows by induction on the number of ribbons of T, using the given description of the evolution of chains. Let ξ, ξ′ be as in that description; if either ξ does not belong to C, or ht(ξ) = ht(ξ′), there is no change in Spin(T) − Spin(T′), and the induction is trivial. The cases remain where ξ forms a new chain, closes an open chain, or joins two open chains; in the first two of these the proposition follows easily. In the final case ξ contributes ±\frac{1}{2} to Spin(T) − Spin(T′), and each of the open chains being joined can be as in 1a, 1b, or 1c, so there are many more cases to distinguish; however, because these two chains cannot cross each other, the proposition can be established in all cases.

There is a more intuitive way to understand the proposition. We may draw arrows, as was done earlier, to indicate the movement of ribbons of C; for each ribbon ξ of C there is an arrow pointing into it and one pointing out of it (we include an arrow into the first ribbon of an open chain). Then ht(ξ) changes only if of these two arrows one points inward and the other points outward; if so, it increases when the chain turns to the left at ξ, and it decreases when the chain turns to the right. It then follows from topological considerations that the accumulated amount of turning along an open chain is at most half a turn left or right, in accordance with the subcases of 1 in the proposition, and along a closed chain it is a full turn either left or right, in accordance with case 2. Here is an example of a domino tableau with various chains.

0 ↓ 2 ↓9↑ 7 ↑↘ 1↑ ↖ 5→ 10 → ↖ 8 ↑ 4 ↓ 6 ← 3 ↑

The chain of dominoes with entries 8, 4, 6, 3 is of type 1a, the one with entry 1 is of type 1b, the one with entries 5, 10 is of type 1c, and the closed chain with entries 0, 2, 9, 7 is of type 2a. There are “left turns” at ribbons 4, 1, 0, and 9, and “right turns” at ribbons 6 and 5; at the remaining ribbons no turn is registered, because there is no change from inward to outward movement.

4.5. Moving open chains only.

4.5.1. Definition. Let 0 ≤ j < r and let T be a semistandard r-ribbon tableau; s_{j} ∘ T is the semistandard r-ribbon tableau obtained from T by moving all open chains in T for s_{j}.

Clearly, the shape of s_{j} ∘ T is the same as that of s_{j}(T). This definition is stated mainly for future reference; its importance lies in the observation that moving open chains has certain nice properties, particularly in the case of domino tableaux, that do not hold in general for closed chains. Proposition 4.3.1 gives a first indication in this direction, as does [6, theorem 2.2.9], which states, loosely speaking, that moving open chains in domino tableaux, as well as moving certain closed ones, commutes with the process of Schensted insertion defined in [5] (see also [10, 4.2]). An obvious question is whether T ↦ s_{j} ∘T defines an action of S̃_{r}; this turns out to be the case only for r = 2.

4.5.2. Proposition. The operations T ↦ s_{j} ∘ T for j = 0, 1 extend to a weight preserving action of S̃_{2} on the set of semistandard domino tableaux.

Proof. The only relations to check are s_{j} ∘ s_{j} ∘ T = T for j = 0, 1, which are obvious.

As an example that the Coxeter relations of S̃_{r} do not hold for r > 2, we display here the successive stages in the computation of s_{2} ∘ s_{0} ∘ s_{2} ∘ s_{0} ∘ s_{2} ∘ s_{0} ∘ S for a standard 3-ribbon tableau S.

S:  0 1 2 3 \underrightarrow{s_{0}}  0 1 2 3  \underrightarrow{s_{2}}  0 1 2 3  \underrightarrow{s_{0}} 0 1  2 3  \underrightarrow{s_{2}} 0 1 2 3  \underrightarrow{s_{0}} 0 1 2 3  \underrightarrow{s_{2}} 0 1 2 3

We note some other properties specific to the domino case. Both generators s_{0}, s_{1} of S̃_{2} act on Z without fixed points, so the cases pos(ξ) = pos(ξ′) above do not occur; there are no trivial chains, and closed chains always have an even number of dominoes. Since form(ξ) consists of a single bit, the form of a domino before and after its chain is moved are completely unrelated.

Any σ ∈ S̃_{2} has a unique reduced expression, which is a product of generators s_{0} and s_{1} in which they occur alternatingly. If one determines σ(S) by successive application of these generators, and tracks some ξ ∈ Rib(S) through the successive steps, then pos(ξ) either increases at each step or decreases at each step; which of the two happens depends on the original parity of pos(ξ). Loosely speaking, the ribbons are divided into two cohorts, that march in opposite directions; the interaction between them is limited to sideways movements (up and down along diagonals). If the reduced expression is sufficiently long, the two groups of dominoes will eventually pass each other completely, and the domino tableau will be divided into two parts that are directly related to the tableaux (S_{0}, S_{1}) corresponding to S in the bijection of proposition 3.1.2; such a domino tableau will be called a segragated tableau in the sequel [11] to this paper. There, a more important operation will in fact be the computation of σ ∘ S, in which case the use of the reduced expression of σ is essential. The difference with the process just described, is that whenever a domino is part of a closed chain, it halts for one step. This makes it reverse its direction and join the opposite cohort, until possibly it becomes part of another closed chain at some later step. Since the shape of σ ∘ S is the same as that of σ(S), the domino tableau eventually becomes segragated here as well, but since the occurrence of closed chains is hard to predict, it is not easy to tell which of the original dominoes will end up in which part of the segragated tableau. We conclude by displaying such a “collision experiment”.

0 ← 1 ↑ 2 ↑  3 ← 4 ↑ 5→  6 ← 7 ↑  8 ←  0 ← 1 ↑ 2 ↑ 3 ↓ 4 ↑  5↑  6 ← 7 ↑  8 ↓  0 ← 1 ↑ 2→ 3↑ 4 ↑  5 ←  6 ↓ 7→  8 ←  0 ← 1→ 2↑ 3→ 4 ↑ 5 ↓  6 ← 7↑ 8 ↓  ^{0 ↓1↑ 2→3 ← 4→ 5 → 6→ 7 ←  8 ←}

0 → 1 ↓ 2 ← 3→ 4 ↓ 5 ↓  6 → 7↑ 8 ↑  0 → 1 ↓ 2 ↓  3 → 4 ↓ 5↑  6 → 7 ↓ 8→  0 → 1 ↓ 2 → 3 → 4 ↓ 5 ↓  6 → 7 ↓  8 →  0 → 1 ↓  2 → 3 → 4 ↓ 5 ↓  6 → 7 ↓  8 →

References.

[1] A. Björner and F. Brenti, Affine permutations of type A, Electronic J. of Combinatorics 3 (no. 2), R18, (1996), 35 pp.

[2] C. Carré and B. Leclerc, Splitting the square of a Schur function into its symmetric and antisymmetric parts, J. of algebraic combinatorics 4, (1995), 201–231.

[3] E. Date, M. Jimbo, A. Kuniba, T. Miwa, and M. Okado, Paths, Maya diagrams and representations of 𝔰̂𝔩(r, C), Advanced Studies in Pure Mathematics 19, (1989), 149–191. Integrable Systems in Quantum Field Theory and Statistical Mechanics.

[4] S. Fomin and D. Stanton, Rim hook lattices, Institut Mittag-Leffler report No. 23, (1991/92).

[5] D. Garfinkle, On the classification of primitive ideals for complex classical Lie Algebra’s, I, Compositio Mathematica 75, (1990), 135–169.

[6] D. Garfinkle, On the classification of primitive ideals for complex classical Lie Algebra’s, II, Compositio Mathematica 81, (1992), 307–366.

[7] F. Garvan, D. Kim, and D. Stanton, Cranks and t-cores, Inventiones Math. 101, (1990), 1–17.

[8] G. James and A. Kerber, The representation theory of the symmetric group, Encyclopedia of mathematics and its applications (G.-C. Rota, ed.) Vol. 16, Addison-Wesley, Reading MA, 1981.

[9] A. Lascoux, B. Leclerc and J.-Y. Thibon, Ribbon tableaux, Hall-Littlewood functions, quantum affine algebras and unipotent varieties, J. Math. Physics 38, (1997), 1041–1068.

[10] M. A. A. van Leeuwen, The Robinson-Schensted and Schützenberger algorithms, an elementary approach, Electronic J. of Combinatorics 3 (no. 2), R15, (1996), 32 pp.

[11] M. A. A. van Leeuwen, Some bijective correspondences involving domino tableaux, Electronic J. of Combinatorics 7 (1), R35, (2000), 25 pp.

[12] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Mathematical Monographs, Clarendon press, Oxford, 1979.

[13] A. O. Morris and J. B. Olsson, On p-quotients for spin characters, Journal of Algebra 119, (1988), 51–82.

[14] J. B. Olsson, Frobenius symbols for partitions and degrees of spin characters, Math. Scandinavica 61, (1987), 223–247.

[15] J. B. Olsson, Combinatorics and Representations of finite groups, Vorlesungen aus dem Fachbereich Mathematik der Universität GH Essen 20, Univ. Essen, 1993.

[16] D. W. Stanton and D. E. White, A Schensted algorithm for rim hook tableaux, J. Combin. Theory, Ser. A 40, (1985), 211–247.