Some bijective correspondences involving domino tableaux

Marc A. A. van Leeuwen

Université de Poitiers, Département de Mathématiques, UFR Sciences SP2MI, Téléport 2, BP 30179, 86962 Futuroscope Chasseneuil Cedex, France

                        maavl@mathlabo.univ-poitiers.fr
                URL: http://wwwmathlabo.univ-poitiers.fr/~maavl/

Submitted: April 13, 2000; Accepted: July 11, 2000.

ABSTRACT

We define a number of new combinatorial operations on skew semistandard domino tableaux that complement constructions defined by C. Carré and B. Leclerc, and clarify the link with ordinary skew semistandard tableaux and the Littlewood-Richardson rule. These operations are: (1) a bijection between semistandard domino tableaux and certain pairs of ordinary tableaux of the same weight that together fill the same shape, and which determine the “plactic class” of the domino tableau; (2) a weight preserving reversible transformation of domino tableaux into ordinary tableaux of a related shape (the correspondence involves 2-quotients) mapping the subset of Yamanouchi domino tableaux onto that of the Littlewood-Richardson tableaux; (3) a correspondence between Yamanouchi domino tableaux of shape λ and weight μ and Yamanouchi domino tableaux of shape μ′ and weight λ, where μ′ is μ scaled horizontally and vertically by a factor 2. The essential properties of (1) and (2) are obtained by proving their commutation with the “coplactic” (or crystal) operations (which for domino tableaux were defined by Carré and Leclerc). Construction (2) allows algorithmic separation of the Littlewood-Richardson tableaux describing the decomposition of the tensor square of a general linear group representation into contributions to its symmetric and alternating parts.

Mathematics Subject Classification 2000: 05E10. Keywords and Phrases: domino tableau, bijective proof.

§1. Introduction.

The oldest form of the Robinson-Schensted correspondence, given in [Rob], associates to any semistandard skew tableaux T of shape λ/μ and weight α, a pair (L, P) consisting, for some partition ν, of a Littlewood-Richardson tableau L of shape λ/μ and weight ν, and a semistandard Young tableau P of shape ν and weight α (cf. [vLee5, (8)]). In [CaLe], an analogue for domino tableaux of this construction was given, associating to a domino tableau D a pair consisting of a so-called Yamanouchi domino tableau Y, and a semistandard Young tableau P. As a result, a decomposition rule for products of Schur functions similar to the Littlewood-Richardson rule is derived, counting Yamanouchi domino tableaux instead of Littlewood-Richardson tableaux; it has the additional advantage that for the square of a Schur function, its decomposition into its (representation theoretic) symmetric and alternating parts can be read off.

In this paper we define three bijective constructions complementing these results. The first associates to a semistandard domino tableau a pair of ordinary semistandard tableaux called a self-switching tableau pair. This provides a direct description of the association D ↦ P, of which the original description in [CaLe], like that of T ↦ P in [Rob], is quite indirect, and not even obviously well defined. The rôle of this first construction is therefore analogous to that of jeu de taquin, which describes the correspondence T ↦ P. Our second construction is a weight preserving transformation of domino tableaux of shape λ/μ into ordinary tableaux of a shape determined by the 2-quotients of λ and μ, which maps Yamanouchi domino tableaux to Littlewood-Richardson tableaux; it relates the Littlewood-Richardson rule to its counterpart using domino tableaux. Our third construction defines a bijection between certain sets of Yamanouchi domino tableaux, which exhibits the identity of two different combinatorial expressions for the scalar product ⟨s_{λ}, ψ^{2}(s_{μ})⟩, given respectively in Corollary 4.3 and Theorem 5.3 of [CaLe].

To define these bijections, we apply algorithmic constructions defined elsewhere, notably in [vLee3] and [vLee5]. In addition, a central rôle is played by coplactic operations (cf. [vLee5, §3]), operating on domino tableaux; an implicit definition of these operations is contained in the algorithm [CaLe, 7.1].

This paper is organised as follows. In §2 we define our main bijective correspondences, and state (without proof) their fundamental properties. In §3 we give the definition of coplactic on domino tableaux used in this paper, which is in terms of so-called augmented domino tableaux. In §4 we relate these coplactic operations to those on ordinary tableaux; in particular the fundamental property of our first bijective correspondence is established by proving commutation with coplactic operations. In §5 we do the same for the other correspondences, which involve moving chains in domino tableaux.

The current paper depends strongly on notions developed in [vLee3] (of which we only use the special case r = 2 of dominoes), and in [vLee5]; we shall now recall, and in some cases extend, their notations. The set of partition is denoted by P, and it subset of 2-cores by C_{2}. The parameters d^{2}(δ(γ)) of a 2-core γ always have the form (c, −c) for c ∈ Z, so we shall denote the 2-core so parametrised by γ_{c}; explicitly, γ_{c} = (k, k − 1, …, 1), where k = −2c if c ≤ 0 and k = 2c − 1 if c > 0. We define skew standard tableaux as sequences of partitions (saturated chains in the Young lattice); unlike in [vLee3] we do not specify a set of entries (an initial subset of N is always assumed). We define standard domino tableaux similarly, using the 2-rim hook lattice (P, ≤_{2}) instead of the Young lattice. Semistandard (domino) tableaux are determined by their standardisation and their weight. We write SST(λ/μ) for the set of all semistandard tableaux of shape λ/μ, and SSDT(λ/μ) for the analogous set of semistandard domino tableaux; when restricting to entries < n, we write SST(λ/μ, n) and SSDT(λ/μ, n). We denote the set of dominoes of D ∈ SSDT(λ/μ) by Dom(D); the set of squares of T ∈ SSDT(λ/μ) is just the Young diagram Y (λ/μ), independently of T. If moreover s ∈ Y (λ/μ) and x ∈ Dom(D), we write T (s) respectively D(x) for the entries of the square s and domino x, and pos(s), pos(x) for their respective positions (i.e., maximal index of a diagonal meeting the square/domino). Furthermore we shall use the spin Spin(D) of D (half the number of vertical dominoes in Dom(D)), and the 2-sign ε_{2}(λ/μ) = (−1)^{2 Spin(D)} of its shape.

The affine permutation group S̃_{2} is freely generated by two involutions s_{0}, s_{1}; each of them defines a structure of chains on the set of dominoes of any domino tableau D. Two actions of S̃_{2} are defined on semistandard domino tableaux: in the first, denoted by σ(D), the generator s_{i} moves all chains of D for s_{i} that are not forbidden (cf. [vLee3, proposition 4.3.1]); in the second, denoted by σ ∘ D, it moves only the subset of open chains (it follows that σ(D) and σ ∘ D have the same shape). Tableau switching, which is an involution on pairs (S, T) of skew semistandard tableaux whose shape fit together (i.e., S ∈ SST(μ/ν), T ∈ SST(λ/μ), for some λ, μ, ν ∈ P), is denoted by X(S, T), and the relations generated by inward respectively outward jeu de taquin slides by T ▷ T′ and S ◁ S′ (when X(S, T) = (T′, S′), these relations hold; indeed they are equivalent to having this identity for some S, S′, respectively for some T, T′).

Acknowledgements. I wish to thank Mark Shimozono for calling my attention to coplactic operations and their relation to operations on pictures. I also wish to thank Bernard Leclerc for then many stimulating discussions concerning the constructions of [CaLe], and in particular their relation with coplactic graphs.

§2. Various bijective correspondences for domino tableaux. In this section we formulate three results about domino tableaux that complement those found in [CaLe]. We introduce the algorithmic constructions involved, but postpone proofs of most of their properties. We use several concepts and constructions that were introduced in [CaLe], most notably the concept of Yamanouchi domino tableaux (a subclass of the semistandard domino tableaux analogous to that of Littlewood-Richardson tableaux for ordinary semistandard tableaux) and the bijection of [CaLe, Theorem 7.3]. Formally our Yamanouchi domino tableaux differ from those of [CaLe] in that their entries start from 0 (to remain consistent with our other definitions), but this just amounts to a trivial renumbering.

2.1. Projection from domino tableaux to Young tableaux. In this subsection we define a weight preserving map from semistandard domino tableaux to Young tableaux, which will coincide with the projection onto the second factor after applying the bijection of [CaLe, Theorem 7.3].

As mentioned in the introduction, jeu de taquin can be defined in terms of tableau switching. On its turn tableau switching is described using so-called tableau switching families of partitions (λ^{[i,j]})_{i∈I,j∈J}, where I = {k, …, l} and J = {m, …, n} are of intervals of Z. When S, T, S′, T′ are skew standard tableaux with X(S, T) = (T′, S′), then there is such a family such that S and T are respectively read off along the left (j = m) and bottom (i = l) edges of the family, while T′ and S′ are respectively read off along its top (i = k) and right (j = n) edges. The conditions for a tableau switching family are such that either (S, T) or (T′, S′) determine the entire family. If it happens that (S, T) = X(S, T), we call (S, T) a self-switching standard tableau pair; the associated tableau switching family with I = J is symmetric: λ^{[i,j]} = λ^{[j,i]} for all i, j ∈ I. By the definition of a tableau switching family, such symmetry arises if and only if the diagonal sub-family D = (λ^{[i,i]})_{i∈I} is a skew standard domino tableau, and each such domino tableau D corresponds to a unique symmetric tableau switching family (the argument is the same as given in [vLee1, §2.3]). In particular, D determines (S, T), and π_{0}: D ↦ (S, T) defines a shape preserving bijection π_{0} from skew standard domino tableaux to self-switching standard tableau pairs, where the shape of (S, T) is taken to be that of the tableau S|T obtained by joining the two skew tableaux.

As is the case with tableau switching, the bijection π_{0} can be extended to the case of semistandard tableaux; the resulting operation will be denoted by π_{1}. A pair (U, V) of semistandard tableaux satisfying X(U, V) = (U, V) is called self-switching; this means that their standardisations form a self-switching standard tableau pair, and that wt U = wt V (which we call the weight of the pair). For a semistandard domino tableau D with standardisation D_{0} and weight α, we shall define π_{1}(D) as the pair (U, V) of semistandard tableaux with weight α and standardisations (S, T) = π_{0}(D_{0}); to justify this, we must verify that S and T are compatible with α. Let d = λ^{[i,i]} − λ^{[i−1,i−1]} and d′ = λ^{[i+1,i+1]} − λ^{[i,i]} be successive dominoes of D with equal entries, so that pos(d) < pos(d′) by the definition of semistandard domino tableaux. This is easily seen to imply that the squares s = λ^{[i,i]} − λ^{[i,i−1]} and s′ = λ^{[i,i+1]} − λ^{[i,i]} satisfy pos(s) < pos(s′); therefore the skew standard tableau K given by row i of the tableau switching family satisfies compatibility with α at the pair of entries under consideration. This compatibility is preserved by jeu de taquin, so since S ◁ K ◁ T, it holds for S and T as well. We have proved:

2.1.1. Proposition. The correspondence π_{1} defines a shape and weight preserving bijection from semistandard domino tableaux to self-switching tableau pairs.

As was done for tableau switching in [vLee5, §2.2], we may deduce a description of the computation of π_{1}(D) in terms of sliding entries of two different colours within the skew diagram. By symmetry, we need only determine the upper triangular half of the tableau switching family. We label each vertical difference λ^{[i+1,j]} − λ^{[i,j]} by a red entry, and each horizontal difference by a blue one; for each colour, the multiset of entries is that of D. At each stage in the sliding process one has a shuffle of the weakly increasing sequences of red and blue numbers which, by concatenation of the associated vertical and horizontal steps, determines a lattice path through the tableau switching family. Each number in the shuffle corresponds to an entry in the diagram; among equal numbers of the same colour, the correspondence preserves left to right order. Whenever a red and blue number are transposed in the shuffle, the corresponding entries in the diagram are interchanged if and only if they are in adjacent squares. Initially each domino of D is filled with a blue copy of its entry in its inward square and a red copy in its outward square, corresponding to the shuffle in which each red number immediately follows the same blue number. This shuffle is repeatedly modified until all blue numbers precede all red ones, at which point the blue and red entries define the two component tableaux of π_{1}(D). For example, for the computation of

π_{1} ( 1 1 2 2 3 3 4  ) = ( 2 3 1 1 3 2 4 , 3 1 2 2 3 1 4 ) ,  (1)

some intermediate stages, with their shuffles, are (with bold face representing blue, and italics red):

11 11 22 22 33 33 44 2 3 1 1 2 3 1 1 3 2 2 3 4 4  11 11 2233422334 2 3 1 1 3 3 1 1 2 2 2 3 4 4  11223341122334 2 3 1 1 3 3 2 1 2 4 2 3 1 4

Reordering the shuffle from right to left, as in the example, amounts to performing inward jeu de taquin slides on the blue entries, into the squares indicated by the red entries, in decreasing order. Reordering from the left would amount to performing outward slides on the red entries into the squares of the blue ones, in increasing order. Since for (U, V) = π_{1}(D) we have U ◁ V by construction, we can define:

2.1.2. Definition. A weight preserving map π from the set of semistandard skew domino tableaux to the set of semistandard Young tableaux is defined by the condition π(D) ◁ U ◁ V, where (U, V) = π_{1}(D).

2.1.3. Theorem. For any domino tableau D, the second component of the pair associated to it by the bijection of [CaLe, Theorem 7.3] is equal to π(D). In particular, if wt D = λ ∈ P, then D is a Yamanouchi domino tableau if and only if π(D) = 1_{λ}, the unique Young tableau with shape and weight λ.

For instance, for the domino tableau D of (1) we have π(D) = 1 1 2 3 2 3 4, in agreement with the Young tableau computed in [CaLe, 7.2, example 2]. The method by which the Young tableau is obtained is entirely different however, and the proof of theorem 2.1.3 will be a rather indirect one.

2.2. Yamanouchi domino tableaux and Littlewood-Richardson tableaux. In [CaLe, Corollary 4.4] Littlewood-Richardson coefficients are expressed as the cardinalities of certain sets of Yamanouchi domino tableaux. We shall exhibit an algorithmic bijection from the corresponding sets of Littlewood-Richardson tableaux to these sets of domino tableaux. In particular this defines a partitioning of the set of Littlewood-Richardson tableaux describing the square of a Schur function, into contributions to the symmetric and alternating part of the square, by means of the spins of the associated Yamanouchi domino tableaux. These spins cannot be predicted without performing the algorithm, which may explain why earlier attempts to describe such a partitioning by combinatorial means have failed.

We first give a general expression of the multiplication of skew Schur functions in terms of Yamanouchi domino tableaux (only a special case is stated explicitly in [CaLe]), after introducing some notation for skew shapes and tableaux characterised by 2-quotients and 2-cores.

2.2.1. Definition. For i = 0, 1 let λ^{(i)}/μ^{(i)} be a skew shape, T_{i} ∈ SST(λ^{(i)}/μ^{(i)}), and let γ ∈ C_{2}.

(1) cq_{2}(γ, λ^{(0)}, λ^{(1)}) is the unique partition with 2-core γ and 2-quotient (λ^{(0)}, λ^{(1)});

(2) cq_{2}(γ, λ^{(0)}/μ^{(0)}, λ^{(1)}/μ^{(1)}) = cq_{2}(γ, λ^{(0)}, λ^{(1)})/ cq_{2}(γ, μ^{(0)}, μ^{(1)});

(3) cq_{2}(γ, T_{0}, T_{1}) is the semistandard domino tableau of shape cq_{2}(γ, λ^{(0)}/μ^{(0)}, λ^{(1)}/μ^{(1)}) corresponding to (T_{0}, T_{1}) under the bijection of [vLee3, proposition 3.2.2].

2.2.2. Theorem [Carré & Leclerc]. Let χ, χ′ be skew shapes and γ ∈ C_{2}; then

s_{χ} · s_{χ′} = ∑_{ν∈P} #Yam_{2}(cq_{2}(γ, χ, χ′), ν)s_{ν},

where Yam_{2}(ψ, ν) denotes the set of all Yamanouchi domino tableaux of shape ψ and weight ν.

Proof. By [vLee3, corollary 3.2.3] we have

∑_{D∈SSDT(cq_{2}(γ,χ,χ′),n)} x^{wt(D)} = s_{χ}(n) · s_{χ′}(n),

while by [CaLe, Theorem 7.3],

∑_{D∈SSDT(ψ,n)} x^{wt(D)} = ∑_{ν∈P} (#Yam_{2}(ψ, ν) ∑_{T ∈SST(ν,n)} x^{wt(T)}) = ∑_{ν∈P} #Yam_{2}(ψ, ν)s_{ν}(n).

It follows as a special case that the Littlewood-Richardson coefficient c_{λ,λ′}^{ν} is equal to #Yam_{2}(ψ, ν), where ψ is the skew shape cq_{2}(γ, λ/0, λ′/0) = cq_{2}(γ, λ, λ′)/γ, for an arbitrary 2-core γ. This coefficient is traditionally described as the cardinality of one of several sets of Littlewood-Richardson tableaux (see for instance [vLee2, 2.6]); we choose the set LR(λ ∗ λ′, ν) of such tableaux of the shape λ ∗ λ′ and weight ν, where λ∗λ′ is the skew shape obtained by attaching the diagram of λ to the left and below that of λ′. The general case of the theorem then has a similar interpretation: the cardinality of Yam_{2}(cq_{2}(γ, χ, χ′), ν) is equal to that of LR(χ ∗ χ′, ν).† We shall give a bijective proof of this identity: for any 2-core γ and any skew shapes χ, χ′ we shall construct a weight preserving bijection LR(χ ∗ χ′) → Yam_{2}(cq_{2}(γ, χ, χ′)). In fact, the nature of the construction is such that it simultaneously defines a weight preserving bijection LR(χ ∗ χ′) → Yam_{2}(cq_{2}(γ, χ′, χ)) as well; this is remarkable since there is no obvious bijection between LR(χ∗χ′) and LR(χ′∗χ). These bijections will be obtained by restriction of appropriate weight preserving bijections from SST(χ ∗ χ′) to SSDT(cq_{2}(γ, χ, χ′)) and SSDT(cq_{2}(γ, χ′, χ)); to this end we must find such bijections that map Littlewood-Richardson tableaux precisely to Yamanouchi domino tableaux.

Without the final condition, such weight preserving bijections are already provided by the maps Σ_{c}: T_{0} ∗ T_{1} ↦ cq_{2}(γ_{c}, T_{0}, T_{1}) and Σ′_{c}: T_{0} ∗ T_{1} ↦ cq_{2}(γ_{c}, T_{1}, T_{0}), for c ∈ Z; these do not however in general map Littlewood-Richardson tableaux to Yamanouchi domino tableaux. This can be understood from the definitions of such tableaux, which require the word formed by reading the entries of the tableau in a particular order to be a lattice permutation: for Littlewood-Richardson tableaux this can be any valid reading order as described in [vLee5, §1.5], while for Yamanouchi domino tableaux this is the reverse of the column reading order of [CaLe] (a Yamanouchi word is a reverse lattice permutation). Each entry of Σ_{c}(T_{0} ∗ T_{1}) or Σ′_{c}(T_{0} ∗ T_{1}) has a matching entry in T_{0} ∗ T_{1}, but the reading order used in the domino tableau does not always correspond to a valid reading order in T_{0} ∗T_{1}. This even fails for the components T_{0} and T_{1} individually, but more importantly, their entries are interleaved in the reading of the domino tableau, while all entries of T_{1} precede those of T_{0} first factor in any valid reading of T_{0} ∗ T_{1}.

However, if |c| is sufficiently large, the situation is different. According to [vLee3, proposition 3.1.2], a domino d in cq_{2}(γ_{c}, U, V) corresponding to a square s of U satisfies pos(d) = 2(pos(s) + c), while it satisfies pos(d) = 2(pos(s)−c)+1 if it corresponds to a square s of V. Therefore Σ_{c} preserves the relative order of positions when c ≪ 0, and Σ′_{c} does so when c ≫ 0. Here is a concrete exemple to illustrate what happens: we display T_{0} ∗ T_{1}, followed by Σ′_{3}(T_{0} ∗ T_{1}), Σ_{−2}(T_{0} ∗ T_{1}), Σ′_{2}(T_{0} ∗ T_{1}), and Σ_{−1}(T_{0} ∗ T_{1}).

† Strictly speaking, we did not unambiguously define the shape χ ∗ χ′, and if we did, we would not be able to

reconstruct χ and χ′ uniquely from it in all cases. Formally we define tableaux T_{0} ∗ T_{1} ∈ SST(χ ∗ χ′) simply

as pairs (T_{0}, T_{1}) ∈ SST(χ) × SST(χ′), but with the convention that, for the purpose of reading orders (as

in defining LR(χ ∗ χ′, ν)), all entries of T_{1} are considered to lie above and to the right of those of T_{0}.

0 0 0 1 1 2 0 3 2  _{2}_{0} _{3}_{1} _{2} _{1} 0 0 0 Σ′_{3}  _{2}_{0} _{3}_{1} _{2} _{1} 0 0 0 Σ_{−2}  _{2}_{0} _{3}_{1} _{2}_{1} 0 0 0 Σ′_{2}  _{2}_{0} _{3}_{1} _{1} _{2} 0 0 0 Σ_{−1}

In the first two domino tableaux displayed, the dominoes corresponding to squares of T_{0} and T_{1} form disjoint subtableaux, the former consisting entirely of vertical dominoes and the latter of horizontal ones; in both components the correspondence between squares and dominoes is linear, and independent of the other component. Then the reading order in T_{0} ∗ T_{1} induced by the column reading order for the domino tableau is a valid one, so the fact that T_{0} ∗ T_{1} is a Littlewood-Richardson tableau implies that the indicated domino tableaux are Yamanouchi. For the third domino tableaux above most of these statements loose their validity, and the fourth one is in fact no longer a Yamanouchi domino tableau. The condition that characterises the simpler situation in the first two domino tableaux can be stated in terms of the dominoes d and d′ corresponding respectively to the top-right square s of T_{0} and the bottom-left square t of T_{1}: it is pos(d) ≤ pos(d′)−3 (so that the diagonal with index pos(d)+1 separates the two components), which in view of the expression given above becomes 2c ≤ pos(s) − pos(t) − 1 in case of Σ_{c}, and 2c ≥ pos(t) − pos(s) + 2 for Σ′_{c}. Indeed, in the example pos(s) − pos(t) = −1 − 2 = −3, so these conditions are met for c ≤ −2 respectively for c ≥ 3. Concluding, our reasoning leads to the following definition and proposition.

2.2.3. Definition. Let T_{0} ∈ SST(λ/μ) and T_{1} ∈ SST(λ′/μ′); then Σ_{c}(T_{0} ∗ T_{1}) (respectively Σ′_{c}(T_{0} ∗ T_{1})) is called a segregated tableau for T_{0}∗T_{1} when 2c ≤ −n+1 (respectively when 2c ≥ n), where n = λ_{0}+(λ′)_{0}^{t}.

2.2.4. Proposition. If a domino tableau Σ_{c}(T_{0}∗T_{1}) or Σ′_{c}(T_{0}∗T_{1}) is segregated, then it is a Yamanouchi domino tableau if and only if T_{0} ∗ T_{1} is an Littlewood-Richardson tableau.

Our goal is now to extend the proposition by replacing Σ_{c}(T_{0} ∗ T_{1}) and Σ′_{c}(T_{0} ∗ T_{1}), in case they are not segregated, by appropriate other domino tableaux of the same shape and weight. To this end observe that the collection of all domino tableaux Σ_{c}(T_{0} ∗ T_{1}) and Σ′_{c}(T_{0} ∗ T_{1}) for c ∈ Z forms an orbit for the action (σ, D) ↦ σ(D) of the group S̃_{2} on semistandard domino tableaux. Indeed s_{i}(cq_{2}(γ, T_{0}, T_{1})) = cq_{2}(s_{i}(γ), T_{1}, T_{0}) for i = 0, 1 by the description of [vLee3, proposition 4.3.2], while s_{0}(γ_{c}) = γ_{1−c} and s_{1}(γ_{c}) = γ_{−c}; the orbit can be depicted as follows (omitting the arguments T_{0} ∗ T_{1}):

⋯ Σ′_{2} \underleftrightarrow{s_{0}} Σ_{−1} \underleftrightarrow{s_{1}} Σ′_{1} \underleftrightarrow{s_{0}} Σ_{0} \underleftrightarrow{s_{1}} Σ′_{0} \underleftrightarrow{s_{0}} Σ_{1} \underleftrightarrow{s_{1}} Σ′_{−1} \underleftrightarrow{s_{0}} Σ_{2} ⋯

If we go far enough to the left in this diagram, the domino tableaux Σ_{c} and Σ′_{c} will be segregated. We shall choose such a segregated domino tableau S in this orbit, and then replace the orbit by the orbit of S for the other action (σ, D) ↦ σ ∘ D of S̃_{2} (cf. [vLee3, proposition 4.5.2]). Recall that whereas in the former action application of s_{i} amounts to moving all non-forbidden chains for s_{i}, this is limited in the latter action to moving the subset of open chains. Since it is easily seen that a segregated tableau contains only open chains (both for s_{0} and for s_{1}), the part of the two orbits consisting of segregated tableaux will be identical, whence our construction is independent of the choice of S.

2.2.5. Definition. For any skew shapes χ, χ′ and c ∈ Z, maps Φ_{c} and Φ′_{c} from SST(χ∗χ′) to respectively SSDT(cq_{2}(γ¸,χ, χ′)) and SSDT(cq_{2}(γ¸,χ′, χ)) are defined as follows. Let S be a segregated domino tableau for T_{0} ∗ T_{1} ∈ SST(χ ∗ χ′); then Φ_{c}(T_{0} ∗ T_{1}) and Φ′_{c}(T_{0} ∗ T_{1}) are the unique elements in the orbit of S for the action (σ, D) ↦ σ ∘ D, of respective shapes cq_{2}(γ, χ, χ′) and cq_{2}(γ, χ′, χ): if σ, σ′ ∈ S̃_{2} are such that σ(S) = Σ_{c}(T_{0} ∗ T_{1}) and σ′(S) = Σ′_{c}(T_{0} ∗ T_{1}), then Φ_{c}(T_{0} ∗ T_{1}) = σ ∘ S and Φ′_{c}(T_{0} ∗ T_{1}) = σ′ ∘ S.

As an example we compute Φ_{1}(T_{0} ∗ T_{1}) for the tableau T_{0} ∗ T_{1} of the previous example. We start with the third domino tableau desplayed earlier, which is the first non-segregated one, and is part of the orbit for either of the actions; after this point there is divergence, and the action (σ, D) ↦ σ ∘D proceeds:

2_{0} _{3}_{1} _{2}_{1} 0 0 0 Φ′_{2}  _{2}_{0} _{3}_{1} _{2}_{1} 0 0 0 Φ_{−1}  _{2}_{0} _{3}_{1} _{1}_{2} 0 0 0 Φ′_{1}  _{2}_{0} _{3} _{1} _{1}_{2}_{0} 0 0 Φ_{0}  ^{2 0 3 1 1 2 0 0 0} Φ′_{0}  ^{2 0 3 1 1 2 0 0 0} Φ_{1}

Note that these are all Yamanouchi domino tableaux. As we shall prove, this is no coincidence:

2.2.6. Theorem. By restriction, Φ_{c} and Φ′_{c} define, for any c ∈ Z, bijections from LR(χ∗χ′) respectively to Yam_{2}(cq_{2}(γ_{c}, χ, χ′)) and to Yam_{2}(cq_{2}(γ_{c}, χ′, χ)).

We shall in fact prove the stronger statement that moving any open chain is compatible with the bijection of [CaLe, Theorem 7.3]: on the first factor (the Yamanouchi domino tableau) the corresponding open chain is moved, while the second factor (the Young tableau) is unchanged.

Concerning definition 2.2.5, we note the following. While, as indicated in the example, it is clear where in the orbit each Φ_{c}(T_{0} ∗ T_{1}) and Φ′_{c}(T_{0} ∗ T_{1}) are to be found, we have initially defined these tableaux as being uniquely determined within the orbit by their shape. When the shapes χ and χ′ of T_{0} and T_{1} are distinct, this is true because the action of S̃_{2} on the shapes in the orbit is free; on the other hand when χ = χ′, each shape has a stabiliser of order 2, since cq_{2}(γ_{0}, χ, χ) is stabilised by s_{1}. In the latter case however the tableau Φ_{0}(T_{0} ∗ T_{1}) is also stabilised by s_{1} (i.e., Φ_{0}(T_{0} ∗ T_{1}) = Φ′_{0}(T_{0} ∗ T_{1})), since the fact that the shape does not change implies that all chains are closed; then the whole orbit is symmetric and each tableau is unique for its shape. This also implies that Φ_{c} and Φ′_{c} coincide for χ = χ′.

Another point that can be observed is that the image of the map Φ_{c} for the shape χ ∗ χ′ coincides with the image of Φ′_{c} for χ′ ∗ χ. Therefore we may compose the former map with the inverse of the latter, so as to obtain a bijection SST(χ ∗ χ′) → SST(χ′ ∗ χ) which, by theorem 2.2.6, restricts to a bijection X_{Dom}: LR(χ ∗ χ′) → LR(χ′ ∗ χ); the following description shows that X_{Dom}(T_{0} ∗ T_{1}) does not depend on c. One forms segregated tableau for T_{0} ∗ T_{1}, and moves though the non-segregated part of its orbit for the action (σ, D) ↦ σ ∘ D, to the other (right) end, where the domino tableau becomes segregated again, but for some other tableau T′_{1} ∗ T′_{0} = X_{Dom}(T_{0} ∗ T_{1}) of shape χ′ ∗ χ. This bijection differs from the “traditional” bijection X_{LR}: LR(χ ∗ χ′) → LR(χ′ ∗ χ) that is described in detail in [vLee4], and can be characterised in the language of [vLee5] as tableau switching on companion tableaux. In fact the two bijections have rather different characteristics: in X_{Dom} the shapes χ, χ′ play a crucial rôle (e.g., X_{Dom} is the identity for χ = χ′, by the remarks above), whereas X_{LR} only uses some reading of the tableaux (a lattice permutation); also X_{LR} does not naturally extend to a bijection SST(χ ∗ χ′) → SST(χ′ ∗ χ).

2.3. Matching two expressions for ⟨s_{λ}, ψ^{2}(s_{μ})⟩. Our third construction establishes a bijection corresponding to the identity

ε_{2}(λ)#Yam_{2}(λ, μ) = ∑_{M∈Yam_{2}(μ^{⊔ ⊓},λ)}(−1)^{|μ|−Spin(M)},  (2)

where μ^{⊔ ⊓} = cq_{2}(∅, μ, μ) is the partition obtained from the Young diagram of μ by scaling up by a factor 2 both horizontally and vertically. Since Spin(D) denotes half the number of vertical dominoes in D, and ε_{2}(λ) = ε_{2}(λ/∅) = (−1)^{2 Spin(D)} for any D ∈ SSDT(λ), the Yamanouchi domino tableaux in the first member are counted with a fixed sign determined by the parity of their number of vertical dominoes, while those in the second member are counted with a varying sign, determined by the parity of half the number of horizontal dominoes (since ε_{2}(μ^{⊔ ⊓}) = 1, and these tableaux have 2|μ| dominoes altogether).

We recall that both members of (2) are combinatorial expressions for the number ⟨s_{λ}, ψ^{2}(s_{μ})⟩, where ψ^{2} is the plethysm operator that replaces each monomial x^{α} by x^{2α}. We review briefly the derivation of this identity, as it is spread across many sections of [CaLe], and since similar arguments will be used in our bijective proof. Denoting by ϕ^{2} the dual of the linear operator ψ^{2}, so that ⟨s_{λ}, ψ^{2}(s_{μ})⟩ = ⟨ϕ^{2}(s_{λ}), s_{μ}⟩ for all λ, μ ∈ P, it is a classical fact that ϕ^{2}(s_{χ}) = ε_{2}(χ)s_{χ′}s_{χ′′} when χ = cq_{2}(γ, χ′, χ′′) for skew shapes χ′, χ′′ (see [Litw]; ϕ^{2}(s_{χ}) = 0 if the shape χ admits no domino tableaux). Therefore by theorem 2.2.2:

ϕ^{2}(s_{χ}) = ε_{2}(χ) ∑_{ν∈P} #Yam_{2}(χ, ν)s_{ν}  (3)

(cf. [CaLe, Corollary 4.3, (5)]), whence the first member of (2) equals ⟨ϕ^{2}(s_{λ}), s_{μ}⟩. The second member is obtained by evaluating in two ways the sum of (−1)^{Spin(D)}x^{wt(D)} as D ranges over SSDT(μ^{⊔ ⊓}, n). On one hand, since the map from domino tableaux to Yamanouchi domino tableaux in [CaLe, Theorem 7.3] preserves the spin, this sum decomposes as

∑_{ν∈P} (  ∑_{{M∈Yam_{2}(μ^{⊔ ⊓},ν) \atop T ∈SST(ν,n)}}(−1)^{Spin(M)}x^{wt(T)}) = ∑_{ν∈P}(  ∑_{M∈Yam_{2}(μ^{⊔ ⊓},ν)}(−1)^{Spin(M)})s_{ν}(n).  (4)

On the other hand, one can cancel from the sum all contributions of domino tableaux D among whose chains for s_{1} (which are all closed) there is least one that can be moved (cf. [vLee3, proposition 4.3.1]): the tableau obtained by moving one such chain contributes with an opposite sign by [vLee3, proposition 4.4.1]. What remains are those domino tableaux D ∈ SSDT(μ^{⊔ ⊓}, n) for which every 2×2 block corresponding to a square of μ is occupied by a pair of vertical dominoes with equal entries, forming a forbidden chain for s_{1}. These tableaux are in bijection with ordinary semistandard tableaux D′ of shape μ; since Spin(D) = |μ| and wt D = 2 wt D′, the summation becomes

∑_{D′∈SST(μ,n)}(−1)^{|μ|}x^{2 wt D′} = (−1)^{|μ|}ψ^{2}(s_{μ})(n).  (5)

Taking the coefficient of s_{λ}(n) in (4) and (5), one finds that ⟨s_{λ}, ψ^{2}(s_{μ})⟩ equals the second member of (2) (cf. [CaLe, Theorem 5.3]), which establishes that identity since ⟨s_{λ}, ψ^{2}(s_{μ})⟩ = ⟨ϕ^{2}(s_{λ}), s_{μ}⟩.

Our combinatorial construction corresponding to (2) will consist of a bijection between tableaux L ∈ Yam_{2}(λ, μ) and tableaux M in a subset B_{λ,μ} of Yam_{2}(μ^{⊔ ⊓}, λ), such that L has half as many vertical dominoes as M has horizontal dominoes (so that ε_{2}(λ) = (−1)^{2 Spin(L)} = (−1)^{|μ|−Spin(M)}), together with a proof that ∑_{M∈C_{λ,μ}}(−1)^{Spin(M)} = 0, where C_{λ,μ} is the complement of B_{λ,μ} in Yam_{2}(μ^{⊔ ⊓}, λ). That proof is similar to the argument leading to (5): we define C_{λ,μ} to be the subset of Yam_{2}(μ^{⊔ ⊓}, λ) of tableaux that contain at least one chain for s_{1} that can be moved while preserving the Yamanouchi property. The contributions of these tableaux to the sum will cancel out, provided we can show that the following holds:

2.3.1. Lemma. Let M be a Yamanouchi domino tableau, s ∈ {s_{0}, s_{1}}, and let S be the set of closed chains C in M for s, for which the tableau obtained from M by moving C is again a Yamanouchi domino tableau. Then the tableau obtained from M by simultaneously moving the chains of any subset of S is also a Yamanouchi domino tableau.

In other words, the set S itself is not affected by moving any of its chains. This means that the relation between Yamanouchi domino tableaux of being obtainable from one another by moving a subset of the chains of S is an equivalence relation, whose equivalence classes have size 2^{#S}; since moving any one chain changes the parity of Spin(M), the sum of (−1)^{Spin(M)} over such a class is 0 if S ≠ ∅. A similar fact, but with “Yamanouchi” replaced by “semistandard”, was needed in the derivation of (5), but that fact is simpler: it follows directly from [vLee3, proposition 4.3.1]. We note that a remark is made in [CaLe] (after its Lemma 8.5) that appears to claim the validity our lemma 2.3.1; however this remark is neither justified nor used there, and so we shall provide a proof of the lemma below.

Given L ∈ Yam_{2}(λ, μ), we construct a filling M of Y (μ^{⊔ ⊓}) using an augmentation of domino tableaux similar to that of ordinary tableaux in [vLee5, (15)], by attaching subscripts called ordinates to the entries of L. We do this in such a way that if the dominoes d with fixed entry L(d) = i are listed by decreasing value of pos(d) (i.e., from right to left), then their ordinates increase by unit steps, starting at 0. This being done, the domino containing i_{j} (entry i with ordinate j) determines two dominoes of M, which occupy the 2×2 block {2i, 2i+1}×{2j, 2j+1} of squares in Y (μ^{⊔ ⊓}). These two dominoes will be horizontal if d is vertical, and vice versa; their two entries are the row numbers of the two squares forming d (which are equal if the dominoes are vertical, and different in they are horizontal, in which case of course the top domino gets the smaller entry). While it is not obvious that M is a Yamanouchi (or even a semistandard) domino tableau, it is clear that it has twice as many horizontal dominoes as T has vertical dominoes.

2.3.2. Theorem. For any λ, μ ∈ P and L ∈ Yam_{2}(λ, μ), the filling M of Y (μ^{⊔ ⊓}) constructed above lies in the subset B_{λ,μ} of Yam_{2}(μ^{⊔ ⊓}, λ) (i.e., none of its chains for s_{1} can be moved without destroying the Yamanouchi property); moreover the construction defines a bijection Yam_{2}(λ, μ) → B_{λ,μ}.

As an example, consider λ = (6, 5, 3, 3, 3) and μ = (4, 3, 2, 1). Now there is just one L ∈ Yam_{2}(λ, μ), displayed here together with the corresponding element M ∈ Yam_{2}(μ^{⊔ ⊓}, λ), both with augmentation:

L = 0_{3} 0_{2} 0_{1} 0_{0} 1_{2} 1_{1} 1_{0} 2_{1} 2_{0} 3_{0}  M =  1_{0} 0_{0} 1_{1} 0_{1} 0_{2} 0_{3} 0_{4} 0_{5}  2_{0} 2_{1} 2_{2} 1_{2} 1_{3} 1_{4}  4_{0} 3_{0} 3_{1} 3_{2} 4_{1} 4_{2}

As can be seen, in addition to the fact that the entries of each pair of dominoes in a 2 × 2 block of M give the row numbers of the squares of the corresponding domino of L, their ordinates give the column numbers. The four tableaux of the remainder C_{λ,μ} of Yam_{2}(μ^{⊔ ⊓}, λ) form a single equivalence class, for which the set S of lemma 2.3.1 for s_{1} consists of two closed chains, each occupying one 2 × 2 block:

1_{0} 0_{0} 1_{1} 0_{1} 0_{2} 0_{3} 0_{4} 0_{5}  3_{0} 2_{0} 2_{1} 1_{2} 1_{3} 1_{4}  4_{0} 3_{1} 3_{2} 2_{2}4_{1} 4_{2} Spin = 4 ⟷ 1_{0} 0_{0} 1_{1} 0_{1} 0_{2} 0_{3} 0_{4} 0_{5}  3_{0} 2_{0} 1_{2} 2_{1} 1_{3} 1_{4}  4_{0} 3_{1} 3_{2} 2_{2}4_{1} 4_{2} Spin = 5

↕  ↕

1_{0} 0_{0} 1_{1} 0_{1} 0_{2} 0_{3} 0_{4} 0_{5}  3_{0} 2_{0} 2_{1} 1_{2} 1_{3} 1_{4}  4_{0} 3_{1} 3_{2} 2_{2}4_{1} 4_{2} Spin = 5 ⟷ 1_{0} 0_{0} 1_{1} 0_{1} 0_{2} 0_{3} 0_{4} 0_{5}  3_{0} 2_{0} 1_{2} 2_{1} 1_{3} 1_{4}  4_{0} 3_{1} 3_{2} 2_{2}4_{1} 4_{2} Spin = 6

We have added ordinates in these tableaux as well; one can see that the blocks of the chains in S have pairs {1_{2}, 2_{1}} and {3_{1}, 4_{0}} of entry-ordinate combinations that do not correspond to adjacent squares.

§3. Coplactic operations. We shall now study in detail the algorithm defining the bijection of [CaLe, Theorem 7.3], which is given in [CaLe, 7.1]. It is modelled after Robinson’s algorithm, which is defined in [Rob, §5], but is more clearly described in [Macd, I 9]. The basic steps of Robinson’s algorithm are the coplactic operations, for a the detailed discussion of which we refer to [vLee5]. Similar operations can be defined for domino tableaux as well; these are the basic steps of the first algorithm mentioned above, and will also be called coplactic operations. We recall that the basic definition of coplactic operations is the one for words, which is then transferred to ordinary semistandard tableaux by applying it to words obtained by reading the entries of the tableaux in some specific order. The transfer to semistandard domino tableaux is more involved, for two related reasons: there is no obvious way to apply the valid reading orders for ordinary tableaux to domino tableaux, and coplactic operations may involve rearrangement of dominoes (sometimes a coplactic operation is applicable, but no proper result can be obtained by just changing the entry of a domino).

The method of definition adopted in [CaLe] is to use a particular reading order called the column reading of a domino tableau, which detects whether a coplactic operation can be applied, and if so makes a change to one entry as a first approximation of the operation; in case the result is not a semistandard domino tableau, a transformation called R_{1} or a sequence of transformations called R_{2} is applied, yielding the desired result. This method is not without difficulties; the effect of the transformations on further coplactic operations is hard to perceive, as they entail permutations of the letters of the column reading. In particular it is not obvious that the “coplactic graph” associated to a domino tableau is always isomorphic to that of some ordinary tableau, or equivalently, of some word; in any case one cannot always take the column reading word. Yet this property is essential for establishing the bijection of [CaLe, Theorem 7.3], since the second component of the pair it associates to a domino tableau D can be described as “the Young tableau that is in the same place within its coplactic graph as D is” (because of a similar characterisation for Robinson’s bijection, cf. [vLee5, §4.2]). Alternatively, our bijection π_{1} could be taken as basis for the definition of coplactic operations on domino tableaux: it follows from [vLee5, theorem 3.3.1] that if π_{1}(D) = (U, V), and a coplactic operation c is applicable to U (and V), then (c(U), c(V)) is again a self-switching tableau pair, whence one could define c(D) = π_{1}^{−1}(c(U), c(V)). Then the mentioned isomorphism of coplactic graphs is obvious, but it is not easy to understand directly the effect of a coplactic operation on a domino tableau. It is the essence of theorem 2.1.3 to establish a link between these two possible definitions of coplactic operations. As a preliminary step we shall in this section recast the definition of [CaLe] into a more manageable form that avoids the choice of a particular reading order.

3.1. Augmented domino tableaux. As a basis of our definitions we shall use the notion of ν/κ-dominance of domino tableaux, which refines that of Yamanouchi domino tableaux, and is analogous to the same notion for ordinary tableaux defined in [vLee5, 1.4.1]. Definitions using “companion tableaux” or a reading of the entries would, while possible, be less natural in the case of domino tableaux; nevertheless a simple definition is possible, using augmentation of the domino tableaux with ordinates added to the entries, as in the construction of theorem 2.3.2.

3.1.1. Definition. An augmentation of a semistandard domino tableau D ∈ SSDT(λ/μ) for a skew shape ν/κ is an assignment of ordinates to all d ∈ Dom(D), such that the conditions below are satisfied; if such an augmentation exists (which is then unique) D will be called ν/κ-dominant. The combination of the entry i and ordinate j of a domino d will be written as i_{j}, and pos(d) will then be denoted by π(i_{j}). a. Each i_{j} occurs at most for one domino, and it does so if and only if (i, j) ∈ Y (ν/κ); b. π(i_{j+1}) < π(i_{j}) whenever {(i, j), (i, j + 1)} ⊆ Y (ν/κ); c. π((i + 1)_{j}) < π(i_{j}) whenever {(i, j), (i + 1, j)} ⊆ Y (ν/κ).

Conditions a and b imply that among the dominoes with a fixed entry i, the ordinates increase from right to left by units steps, starting at κ_{i}; the test for ν/κ-dominance then amounts to verification of condition c. Like for ordinary tableaux, D can only be ν/κ-dominant if wt D = ν − κ, and we shall say that D is simply κ-dominant if it is ν/κ-dominant for ν = κ + wt D; note that it is still required that ν be a partition. We shall show that D is a Yamanouchi domino tableau if and only if it is 0-dominant.

The definition above appears to be symmetric with respect to entries i and ordinates j, but is not really so due to the requirement that D be a semistandard domino tableau: ordering dominoes by increasing entries and then (for equal entries) by decreasing ordinates defines a standard domino tableau. We shall see that it is possible as well to order dominoes by ordinate first; these should decrease, and among dominoes with equal ordinates, the entries should increase. In fact we shall prove the following.

3.1.2. Proposition. Let D ∈ SSDT(λ/μ) be augmented for ν/κ, and let ‘≺’ be a total ordering of the set { i_{j} | (i, j) ∈ Y (ν/κ) } with the property that i_{j} ⪯ k_{l} whenever i ≤ k and j ≥ l. Then there exists a standard domino tableau D_{≺}, called the specialisation of D for ‘≺’, with Dom(D_{≺}) = Dom(D), and in which these dominoes are added in increasing order for ‘≺’ of their entry-ordinate combinations in D.

This means essentially that a domino containing i_{j} can be added to the tableau as soon as the dominoes containing (i − 1)_{j} and i_{j+1} (if they exist) are present. The stronger formulation of the proposition is necessary however: requiring only (i − 1)_{j} ≺ i_{j} and i_{j+1} ≺ i_{j} may fail to imply i_{j} ≺ k_{l} for i < k and j > l by transitivity, as intermediate entry-ordinate combinations may be absent (by contrast, definition 3.1.1 does imply π(k_{l}) ≤ π(i_{j}) whenever k ≥ i and l ≥ j, by convexity of skew diagrams). Note that the orderings ‘≺’ allowed by the proposition are just the valid reading orders of the skew diagram Y (ν/κ). To prove the proposition, we use the following general lemma (a standard fact of some theory, no doubt), which allows us to focus on changing the order between just a single pair of values.

3.1.3. Lemma. Let X be a finite set, S the set (of cardinal (#X)!) of all total orderings of X, and Γ the graph on S in which there is an edge between two orderings if and only if they differ only in the comparison of a single pair of elements of X (this is a Cayley graph of S_{#X}). Then for any partial ordering ‘<’ on X, the subgraph of Γ on the orderings that extend ‘<’ is connected.

Proof. It is readily checked that any minimal length path in Γ between points s, t in the subgraph remains within the subgraph. Some may find the following form of this argument clearer: arranging X in a linear array according to s, and then bubble sorting it using t as sorting criterion, any comparable pair of elements of X for ‘<’ remains in the correct relative order throughout the sorting process. Proof of proposition 3.1.2. It will suffice to prove that if the proposition holds for some ‘≺’, and {i_{j}, k_{l}} with i < k and j < l are adjacent for ‘≺’, then the proposition holds also for the ordering ‘≺′’ in which these two combinations are interchanged. To this end we consider the standard domino subtableau of D_{≺} consisting of the corresponding two dominoes. Using edge sequences one easily classifies the possible standard domino tableaux with the same shape as a given tableau with two dominoes d, d′, in terms of | pos(d) − pos(d′)|: when this value is 2, only one such tableau exists, when it is 1, there are two tableaux, but with different sets of dominoes (in this case the skew diagram is a 2 × 2 block), and in the remaining case of a value exceeding 2 (since pos(d) = pos(d′) is impossible), there are two tableaux, with the same sets of dominoes, which are added in either order. In view of definition 3.1.1, we therefore only have to exclude the possibility that π((i+1)_{j+1}) = π(i_{j})−2 for some i, j. Assuming that, one necessarily has π(i_{j+1}) = π((i + 1)_{j}) = π(i_{j}) − 1; calling this value p, the fact that the domino containing i_{j+1} is followed in the standardisation of D, after some intermediate dominoes, by a domino containing (i + 1)_{j} that has the same position p, necessitates the presence among those intermediate dominoes of a domino with position p + 2, and one with position p − 2. Those intermediate dominoes are the ones with entry i and ordinates ≤ j, followed by those with entry i + 1 and ordinates > j (each ordered by decreasing ordinates); therefore the domino with position p + 2 can only be the one containing i_{j−1}, while the one with position p − 2 must be the one containing (i + 1)_{j+2}. But then one has π((i + 1)_{j}) = π(i_{j−1}) − 2 and π((i + 1)_{j+2}) = π(i_{j+1}) − 2; taking j to be either minimal or maximal, one arrives at a contradiction.

As an instance of this proposition, each augmented domino tableau has a specialisation for the Kanji order of entry-ordinate pairs (i_{j} ≺ k_{l} whenever j > l, or j = l and i < k). Consequently, the union of a pair of dominoes a, b respectively containing i_{j} and (i + 1)_{j} is a skew diagram; in particular, a does not extend to the left beyond b (as in \begin{matrix}a \\ b \end{matrix} ), nor does b extend to the right beyond a (as in \begin{matrix}a \\ b \end{matrix} ).

3.1.4. Proposition. A semistandard domino tableau is Yamanouchi if and only if it is 0-dominant.

Proof. Recall that a domino tableau is Yamanouchi when its column reading is a Yamanouchi word, and that the column reading orders dominoes by their leftmost column, and in case of equality by their bottommost row. Yamanouchi words can be characterised as follows: if one attaches to each letter an ordinate counting the occurrences of the same letter to its right in the word, then for any letter (i + 1)_{j}, the letter i_{j} occurs to its right. It is easily verified that if D is a Yamanouchi domino tableau, then attaching these ordinates of letters to the corresponding entries of D, the conditions of definition 3.1.1 are satisfied: one obtains an augmentation of D for ν/0, where ν = wt D. Conversely, let D be a semistandard domino tableau augmented for ν/0; if (i + 1)_{j} occurs, then so will i_{j}, and by the remarks above, the domino containing (i+1)_{j} will precede the one containing i_{j} in the column reading.

3.2. Coplactic operations on domino tableaux. We now proceed to define coplactic operations on domino tableaux, using augmentations. A similar description of coplactic operations for ordinary tableaux can be found in [vLee5, §3.4]; it essentially consists of performing a jeu de taquin slide on the set of entry-ordinate pairs, viewed as coordinates of squares. In the case of domino tableaux we proceed similarly, but a few additional cases have to be treated. We shall first describe this procedure, then show that this gives a proper definition of coplactic operations, and finally show that the operations defined in [CaLe] produce the same effect as ours.

Like in the case of ordinary tableaux, the coplactic operations e_{i} and f_{i} only involve the part of the tableau with entries i and i + 1; for the purpose of defining these operations, we may therefore ignore any other dominoes. So let D be a semistandard domino tableau, all of whose entries are in {i, i + 1}, and for the moment consider only the operation e_{i}. There exists some κ for which D is κ-dominant (it suffices that κ_{i} − κ_{i+1} be sufficiently large), and we equip D with the augmentation for ν/κ, where ν = κ + wt D. If κ_{i} = κ_{i+1}, then e_{i} cannot be applied (D is then 0-dominant, hence Yamanouchi); otherwise we shall construct a κ′-dominant tableau E with corresponding augmentation, where κ′ is obtained from κ by decreasing the part κ_{i} by 1. It may be that D is already is κ′-dominant, in which case we shall get E = D (only ordinates will have changed); if so, the construction is restarted with the new augmentation found (in other words, κ is replaced by κ′). The more interesting case is when D is not κ′-dominant (so κ_{i} − κ_{i+1} is minimal for κ-dominance of D); then obviously E ≠ D, and we define e_{i}(D) = E.

We construct E (with its augmentation) by transforming the augmentation of D in a sequence of steps, which as indicated above resemble those of jeu de taquin, performed on the set of entry-ordinate combinations. At each stage there is one such combination i_{j} with (i, j) ∈ Y (ν/κ′) that does not occur. Then we consider the combinations i_{j+1} and (i + 1)_{j}; if neither occurs (so (i, j) is a corner of Y (ν)), then the process terminates. Otherwise, the process may proceed by changing one of these combinations into i_{j} (written i_{j} ← i_{j+1} or i_{j} ← (i + 1)_{j}): this simple case applies when either just one of these two combinations occurs, or when the union of the dominoes containing these combinations forms a skew diagram; the change then affects the domino d of these two for which pos(d) is larger.

In the remaining case that dominoes exist containing i_{j+1} and (i + 1)_{j}, but their union is not a skew diagram, one of the following two transformations is applied, which rearrange several dominoes at once. To allow a compact display, we subtract i from all entries and j from all ordinates, so that for instance i_{j+1} and (i + 1)_{j} are drawn respectively as 0_{1} and 1_{0}. The first possible transformation is

T_{0}:  C_{0} = 0_{1} 1_{1} 1_{0} ⟶ 0_{1} 0_{0} 1_{0} .  (6)

The second possible transformation may involve an arbitrarily large number of dominoes; the largest part of D that matches the left hand pattern C_{1} is transformed into the corresponding right hand pattern:

T_{1}:  C_{1} = 0_{k} 1_{k} . . . . . . 0_{2} 1_{2} 0_{1} 1_{1} 1_{0} ⟶ 0_{k} 0_{k−1} 1_{k−1} . . . . . . 0_{1} 1_{1} 0_{0} 1_{0} .  (7)

We define the active region of the application of e_{i} in the simple case as the domino whose entry changes, and otherwise as the pattern C_{0} or C_{1} being transformed.

As an example, consider the following domino tableau D, augmented for λ/μ = (5, 5, 4)/(2, 1, 0).

D = 0_{4} 0_{3} 0_{2} 1_{4} 1_{3} 1_{2} 1_{1} 2_{3} 2_{2} 2_{1} 2_{0}

Application of e_{0} is achieved by the sequence of replacements 0_{1} ← 0_{2} ← 0_{3} ← 1_{3} ← 1_{4} (where we ignore the dominoes with entry 2); these only involve the simple case of the definition, since each of the pairs of dominoes containing {0_{2}, 1_{1}}, {0_{3}, 1_{2}}, and {0_{4}, 1_{3}} occupies a skew diagram. Application of e_{1} to D however involves the replacement 1_{0} ← 1_{1}, followed by a transformation T_{0} changing the configuration

1_{2} 2_{2} 2_{1}  into  1_{2} 1_{1} 2_{1} ,

and finally the replacement 2_{2} ← 2_{3}; one therefore finds

e_{0}(D) = 0  0 0 1 0 1 1 2 2 2 2  and  e_{1}(D) = 0  0 0 1 1 1 1 1 2 2 2 .

Note that retaining the ordinates found after computing e_{0}(D), one would not get an augmentation of that tableau, which is a consequence of ignoring the entries 2 in the construction, in order to isolate an application of e_{0}: while it would in a way be more natural to end the process with 1_{3} ← 2_{3} instead of 1_{3} ← 1_{4}, that would compute e_{1}(e_{0}(D)) in one go rather than e_{0}(D) (we shall say a bit more about this below). As we are in fact computing just e_{i}(D), there is no real need to continue the process after the “hole” has propagated into row i + 1 of Y (ν/κ′), either after a replacement i_{j} ← (i + 1)_{j} or a transformation T_{0} or T_{1}; this helps however to relate to the inverse operation f_{i}. That operation is defined by reversing the above process in the obvious ways: entry-ordinate pairs are modified as in an outward jeu de taquin slide, with in addition the inverse transformations of T_{0} and T_{1}. Applying f_{i} to e_{i}(D) constitutes a step-by-step reversal of the application of e_{i} to D.

Observe in the computation of e_{1}(D) that the augmented tableau contains ^{13}_{23} ^{22} , matching C_{1} for i_{j} = 1_{2} and k = 1; nevertheless T_{1} does not apply, since the “hole” never reaches 1_{2} (there is no replacement 1_{1} ← 1_{2} because the dominoes containing {1_{2}, 2_{1}} in D do not form a skew diagram).

We shall now proceed to show that the definition above is a proper one, i.e., that it handles all cases that can arise, and that the result is always a semistandard domino tableau. Assume first that the simple case of the definition applies at all steps; then the result can be seen to be semistandard by comparison of dominoes, as follows. To facilitate the formulation, let us define relations ‘<_{h}’ and ‘<_{v}’ between dominoes, where a <_{h} b and a <_{v} b both imply that pos(a) < pos(b) and that a ∪ b is a skew diagram, in addition to which a <_{h} b means that there is a standard domino tableau that adds the domino a and then b, and a <_{v} b that there is a standard domino tableau that adds b and then a. Then either a <_{v} b <_{h} c or a <_{h} b <_{v} c imply pos(c) − pos(a) ≥ 3, and hence both a <_{h} c and a <_{v} c. We may assume there is a replacement of the form i_{j} ← (i + 1)_{j} (otherwise there is nothing to prove); denote the domino affected by that replacement by d, and by d_{k,l} any other domino containing k_{l} at that moment. Now from the original contents of the dominoes, and the tests leading to the replacement i_{j} ← (i + 1)_{j}, one deduces d_{i+1,j+1} <_{v} d_{i,j+1} <_{h} d <_{h} d_{i+1,j−1} <_{v} d_{i,j−1} (with the proviso that some of the d_{k,l} may not exist, but the dominoes actually present form a contiguous subsequence); the required semistandardness follows.

In the case that at some point the dominoes containing i_{j+1} and (i + 1)_{j} do not unite to a skew diagram, we argue using the same notation, again referring to the contents of dominoes at this point. By proposition 3.1.2, there is a standard domino tableau that adds the dominoes of D in the following order of their original contents: i_{j+1}, (i + 1)_{j+1}, i_{j}, (i + 1)_{j} (where (i + 1)_{j+1} and/or i_{j} may be absent). The domino originally containing i_{j}, if present, is now d_{i,j−1}, and since d_{i+1,j} <_{h} d_{i+1,j−1} <_{v} d_{i,j−1}, it can be interchanged in the ordering with d_{i+1,j}; this leaves d_{i+1,j+1} as the only domino possibly intervening between d_{i,j+1} and d_{i+1,j}, and since by assumption d_{i+1,j} cannot be added directly after d_{i,j+1}, the domino d_{i+1,j+1} must be present. It then follows that one either has a configuration C_{0}, or C_{1} for k = 1; after extending the latter if possible to a maximal match of C_{1}, one finds the transformation T_{0} or T_{1} that is to be applied. The fact that the result of this transformation is semistandard is verified easily: for T_{0} one uses that presence of (i + 1)_{j+2} implies that of i_{j+2}; for T_{1}, one uses that the presence of (i + 1)_{j+k+1} implies that of i_{j+k+1}, plus the maximality of the match of C_{1}, and d_{i+1,j} <_{h} d_{i,j−1} as found above.

For tableaux with entries i and i+1 only, the final entry-ordinate pairs define a proper augmentation, so e_{i}(D) is κ′-dominant, as claimed. To obtain a similar result in the presence of arbitrary entries, the construction simulating jeu de taquin can be extended across more rows of Y (ν/κ′), as was hinted at above. This requires extending the configurations in (6) downwards, in a similar way as the configurations in (7) are extended leftwards, again choosing a maximal match for the transformation to be applied. The effect of this extended construction on the underlying domino tableau (forgetting the ordinates) will be application of a sequence e_{i}, e_{i+1}, … of operations with increasing index. If D is κ-dominant and κ′ is obtained from κ by decreasing the part κ_{i} by 1, then the length of this sequence is the minimal one for which the final result is κ′-dominant; this is the same as what happens in the case of ordinary tableaux [vLee5, theorem 3.4.1]. Since this construction will not be used in the sequel, we leave the precise formulations and verifications to the interested reader; they are quite similar to the ones above.

We now verify that the operations of [CaLe] coincide with ours; we may assume all entries to be in {i, i + 1}. First observe that there can be no other dominoes sharing a column with the active region; therefore it splits the column reading word into a prefix, an active part, and a suffix. Then the prefix is a Yamanouchi word, and the suffix is an anti-Yamanouchi (i.e., reverse anti-dominant) word; to see this one reasons as in the proof of proposition 3.1.4, using the ordinates at the time of the replacement i_{j} ← (i+1)_{j}, or of the transition T_{0} or T_{1}. For the simple case this already shows that application of e_{i} to D induces application of e_{i} on the reverse column reading word; for the other cases it reduces the verification to that for C_{0} and C_{1}. The definitions of [CaLe] produce

101 ⟶ 100 \underrightarrow{R_{1}} 010

in the first case and

0 1 . . . . . . 0 1 1 ⟶ 0 1 . . . . . . 0 1 0 \underrightarrow{R_{2}} 0 1 . . . . . . 0 0 1 \underrightarrow{R_{2}} ⋯ \underrightarrow{R_{2}} 0 0 1 . . . . . . 0 1

in the second case; in either case the overall effect matches that of T_{0} respectively T_{1}.

§4. Self-switching tableau pairs and coplactic operations. In this section we shall prove that under the bijection π_{1} of proposition 2.1.1, application of a coplactic operation to a semistandard domino tableau D corresponds to application of the same operation to each component of the associated pair (U, V) = π_{1}(D). This will immediately prove theorem 2.1.3: the second component in the bijection of [CaLe, Theorem 7.3] is constructed from the sequence of raising operations that transform D into a Yamanouchi domino tableau, and since U and V have coplactic graphs isomorphic to that of D, the result is the same as the second component of Robinson’s bijection applied to U or V, which is the Young tableau associated to either of them by jeu de taquin (cf. [vLee5]). This commutation of π_{1} with coplactic operations is easy to verify in the basic configurations affected by these operations, in the various situations that can arise. Nevertheless, the proof in the general case is difficult, because of the way π_{1} is defined in terms of the standardisation of D, and the fact that in terms of the standardisation, the effect of coplactic operations is not localised (although it is in terms of dominoes and entries). The reduction to the case that D contains entries i and i + 1 is fairly easy, but to further reduce to a situation simple enough to allow a uniform description of the entire computation of π_{1}(D) presents difficulty, as relatively distant dominoes intervene in the standardisation. We shall resolve this problem by showing that other specialisations of an augmentation of D can also be used to compute π_{1}(D), in particular the one for the Kanji order; the augmentation will be the one used in defining the coplactic operation.

4.1. Self-switching tableau pairs and augmentation. In order to show that alternative orders of dominoes can be used to compute π_{1}(D), let us consider conditions under which the interchange of two successive entries in a standard domino tableau leads under application of π_{0} to the interchange of the corresponding entries in each component of the pair of self-switching standard tableaux. Interchanging the order of two successive entries in a standard domino or ordinary tableau (when this is possible) will affect exactly one partition in the associated chain; the case we are interested in is when in the tableau switching family computing π_{0}, the change of the member λ^{[k,k]} causes a change of the members λ^{[k,j]} and λ^{[i,k]} for all i, j, and of no others. Now if in a tableau switching family (λ^{[i,j]})_{i∈I,j∈J} with I = {k−1, k, k+1}, none of the skew diagrams Y (λ^{[k+1,j]}/λ^{[k−1,j]}) is a domino, then another tableau switching family can be obtained by changing each partition λ^{[k,j]} into the unique other partition between λ^{[k+1,j]} and λ^{[k+1,j]}. This amounts to observing that if during some sequence of slides applied to a skew tableau of size 2, the two squares never become adjacent, then the same sequence of slides would arise if the entries of the two squares were interchanged (since apparently the entries are never being compared); a formal proof can also easily be given by analysing all possible cases for J = {l, l + 1}. In order that our tableau switching family for π_{0} satisfy the given description, it is necessary that the subfamily with i ∈ {k − 1, k, k + 1} be of this type (and its “transpose” subfamily with j ∈ {k − 1, k, k + 1} will then be similar), and that it is still of this type when its members λ^{[k−1,k]}, λ^{[k,k]}, and λ^{[k+1,k]} are changed (this addition means the dominoes Y (λ^{[k,k]}/λ^{[k−1,k−1]}) and Y (λ^{[k+1,k+1]}/λ^{[k,k]}) are non-adjacent, so that their entries can indeed be interchanged). Recall that for ordinary tableaux one has the notions of ν/κ-dominance and augmentations, with the analogue of proposition 3.1.2; calling orderings ‘≺’ described in that proposition “valid”, we have the following.

4.1.1. Proposition. Let D be a semistandard domino tableau, and (U, V) = π_{1}(D). Then for any skew shape ν/κ, each of U and V is ν/κ-dominant if and only if D is; if so, for any valid ordering ‘≺’ of Y (ν/κ), the specialisations D_{≺}, U_{≺}, and V_{≺} of their augmentations for ν/κ are related by π_{0}(D_{≺}) = (U_{≺}, V_{≺}).

We shall derive the second part first. To be precise, we assume that U and V are ν/κ-dominant, and attach ordinates to the dominoes of D in such a way that conditions a and b of definition 3.1.1 are satisfied; we then show that there is a standard domino tableau D_{≺} in which the dominoes of Dom(D) are added in increasing order for ‘≺’, and that π_{0}(D_{≺}) = (U_{≺}, V_{≺}). This is obvious when ‘≺’ is the Semitic order (the specialisations are then standardisations), so by lemma 3.1.3, it suffices to prove that the stated property for a valid ordering ‘≺’ implies the same for another such ordering ‘≺′’ that differs from it by the exchange of two consecutive entry-ordinate pairs for ‘≺’, which are necessarily of the form {i_{j}, k_{l}} with i < k and j < l. Since jeu de taquin preserves ν/κ-dominance and is compatible with taking specialisations (cf. [vLee2, theorem 5.1.1]), the squares containing i_{j} and k_{l} are not adjacent in any tableau obtained by jeu de taquin from U_{≺} (one has π(i_{j}) < π(i_{l}) < π(k_{l}), where π(x_{y}) = pos(s) for the square s containing x_{y}). It follows that the tableau switching family for the computation of π_{0}(D_{≺}) is of the type described above with respect to the interchange of i_{j} and k_{l}, whence π_{0}(D_{≺′}) = (U_{≺′}, V_{≺′}) as required.

It remains to prove the first part of the proposition. To show that in the argument above condition c of definition 3.1.1 is satisfied for the ordinates added to D, we apply what we have just proved for the case that ‘≺’ is the Kanji order. Then any pairs i_{j} and (i + 1)_{j} are consecutive, and by the argument used to prove proposition 2.1.1, the positions of the dominoes containing these pairs in D are ordered in the same sense as positions of the corresponding squares of U, which gives the required condition. For proving conversely that U and V are ν/κ-dominant whenever D is, we cannot yet apply the relation π_{0}(D_{≺}) = (U_{≺}, V_{≺}), so a direct proof is needed, using standardisations to compute (U, V) = π_{1}(D). To show that the conditions required for the candidate augmentations of U and V for ν/κ hold, we may separately verify them for each restriction to a subtableau with entries in {i, i + 1} only. Since such a restriction is obtained by jeu de taquin from a component of the tableau switching pair computed from the similar restriction of D, we may assume that D itself has entries in {i, i + 1} only. Moreover, we may prove ν/κ-dominance for any intermediate tableau in the tableau switching family considered (establishing (U, V) = X(U, V)), in place of U and V; we choose the one at the transition between the slides into squares with entry i and with entry i+1. For any i_{j} and (i+1)_{j}, it follows from definition 3.1.1 and proposition 3.1.2 that the outward square of the domino of D containing i_{j} has a position that is strictly larger than that of the inward square of the domino containing (i + 1)_{j}; from these, the squares of the indicated intermediate tableau containing the same combinations are obtained by a sequence of outward respectively inward jeu de taquin slides, whence their positions are ordered in the same sense.

If we accept the validity of theorem 2.1.3, which will be established in the next subsection, the proposition allows us to generalise (3), or more precisely the equivalent identity ⟨ϕ^{2}(s_{χ}), s_{ν}⟩ = ε_{2}(χ)#Yam_{2}(χ, ν):

4.1.2. Corollary. For all skew shapes χ, ψ one has

⟨ϕ^{2}(s_{χ}), s_{ψ}⟩ = ε_{2}(χ)D(χ, ψ),  (8)

where D(χ, ψ) is the number of ψ-dominant tableaux in SSDT(χ).

Proof. If the bijection of [CaLe, Theorem 7.3] maps D ∈ SSDT(χ) to (Y, P) with Y ∈ Yam_{2}(χ, λ) and P ∈ SST(λ), then it follows from proposition 4.1.1, theorem 2.1.3, and the fact that jeu de taquin preserves ψ-dominance, that P is ψ-dominant if and only if D is. Then D(χ, ψ) is equal to the sum, taken over all λ ∈ P, of #Yam_{2}(χ, λ) times the number of ψ-dominant tableaux in SST(λ). The latter number equals ⟨s_{λ}, s_{ψ}⟩, so that we get ε_{2}(χ)D(χ, ψ) = ∑_{λ∈P} ⟨ϕ^{2}(s_{χ}), s_{λ}⟩⟨s_{λ}, s_{ψ}⟩ = ⟨ϕ^{2}(s_{χ}), s_{ψ}⟩.

4.2. Commutation of π_{1} with coplactic operations. Let us state explicitly what we mentioned earlier, that coplactic operations can be applied to self-switching tableau pairs; this follows by applying [vLee5, theorem 3.3.1] twice to the identity X(U, V) = (U, V).

4.2.1. Proposition. If c is a coplactic operation and (U, V) a self-switching tableau pair, then c can be applied to U if and only if it can be applied to V; if so, (c(U), c(V)) is a self-switching tableau pair.

This subsection is devoted to proving the following theorem; as we have observed above, it justifies the definition of coplactic operations for domino tableaux, and it implies theorem 2.1.3.

4.2.2. Theorem. If c is a coplactic operation, D a semistandard domino tableau, and (U, V) = π(D), then c can be applied to U and V if and only if it can be applied to D, and then (c(U), c(V)) = π_{1}(c(D)).

The proof of this theorem will consist of a reduction in two steps to a situation sufficiently simple to be verified by an explicit computation. Both reduction steps are similar in nature, although the second one is much more subtle; they consist of dividing D into three regions, of which only the middle one is affected by the coplactic operation, and showing that U and V have a similar division. In order to allow the desired conclusion to be drawn we need a small lemma, whose formulation is more awkward than that its claim is actually difficult. Recall that standard (domino) tableaux S, T, which are just chains of partitions, can be joined together into S|T when their shape match, i.e., the last partition of S coincides with the first one of T. We shall use a similar concatenation of semistandard tableaux, but do not insist that the result correspond to another semistandard tableau (although it will in the final applications of the construction); it is defined just as a formal symbol that need only determine a well defined standard tableau. Then we extend π_{1} to an operation π_{2} defined for such concatenations, using the fact that tableau switching essentially uses only the structure of standard tableaux. Formally we define π_{2}(D_{0}| ⋯ |D_{k}) = (U_{0,0}| ⋯ |U_{0,k} , V_{0,k}| ⋯ |V_{k,k}), where U_{i,j} and V_{i,j} are defined inductively for 0 ≤ i ≤ j ≤ k by (U_{i,i}, V_{i,i}) = π_{1}(D_{i}), followed by (U_{i,j}, V_{i,j}) = X(V_{i,j−1}, U_{i+1,j}) for i < j. Then we have

4.2.3. Lemma. If π_{2}(D_{0}|D_{1}|D_{2}) = (U_{0}|U_{1}|U_{2} , V_{0}|V_{1}|V_{2}), and if D_{1} satisfies π_{1}(c(D_{1})) = (c(U), c(V)) where (U, V) = π_{1}(D_{1}), for a coplactic operation c, then π_{2}(D_{0}|c(D_{1})|D_{2}) = (U_{0}|c(U_{1})|U_{2} , V_{0}|c(V_{1})|V_{2}).

Proof. This follows immediately from the definition, using [vLee5, theorem 3.3.1] where appropriate.

This lemma directly allows the first reduction, which is to the case that D has entries in {i, i+1} only, when c = e_{i} or c = f_{i}. The subtableaux D_{0}, D_{1}, and D_{2} of D are those whose dominoes have entries < i, in {i, i + 1}, and > i + 1 respectively; then (U_{0}|U_{1}|U_{2} , V_{0}|V_{1}|V_{2}) corresponds to (U, V) = π_{1}(D), and clearly c(U) and c(V) respectively correspond to U_{0}|c(U_{1})|U_{2} and V_{0}|c(V_{1})|V_{2}. Here a concatenation of semistandard tableaux is said to correspond to another semistandard tableau if their outer shapes are the same, and the set of dominoes with their entries of the latter is the (disjoint) union of those of the components of the concatenation. In this case the relation is particularly simple, since the concatenation of the standardisations form the standardisation of the combined tableau, but that will not be the case for the second reduction.

Assume now that D has entries in {i, i + 1} only, and that c = e_{i} (the case c = f_{i} will follow by reversal). The computation of e_{i}(D) is achieved by modifying an augmentation of D into an augmentation of e_{i}(D). We shall specify below values k and l, which are such that the entry-ordinate combinations i_{k} and (i + 1)_{l} lie on the path of this “slide” (i.e., each is the missing combination at some point during the construction); assume for the moment that they are given. Let D_{0}, D_{1}, and D_{2} be the semistandard subtableaux of D of those dominoes which, at the point in the construction where i_{k} is absent, have ordinates > l, in {l, l − 1, …, k}, and < k respectively; similarly let E_{0}, E_{1}, and E_{2} be the subtableaux of e_{i}(D) of those dominoes whose ordinates satisfy the same conditions respectively, but at the point where (i + 1)_{l} is absent. Since any changes other than just changing ordinates take place between these two points in the construction, we have E_{0} = D_{0}, E_{1} = e_{i}(D_{1}), and E_{2} = D_{2}, these are indeed subtableaux by proposition 3.1.2, and D_{0}|D_{1}|D_{2} and E_{0}|E_{1}|E_{2} respectively correspond to D and to e_{i}(D).

We can now apply lemma 4.2.3, but in order for the result to be of any use, we must ensure that concatenations like U_{0}|U_{1}|U_{2} correspond to the proper semistandard tableau (in the mentioned case to U in (U, V) = π_{1}(D)); this is where the specific choices of k and l become essential (for badly chosen values, U_{0}|U_{1}|U_{2} might not even correspond to any semistandard tableau at all). The standard domino tableau S associated to D_{0}|D_{1}|D_{2} is far from being the standardisation of D; however, proposition 4.1.1 allows any specialisation of the augmentation of D to be used to compute (the corresponding specialisations of) U and V. Now C is almost such a specialisation, but not quite; the only wrinkle is that, since one must of course use the original augmentation of D in which the ordinates of all entries i of D_{2} are one more than at the point where i_{k} is absent, the domino d_{2} of D_{2} initially containing i_{k} (if present) is added in C after the domino d_{1} of D_{1} containing (i + 1)_{k}, whereas i_{k} ≺ (i + 1)_{k} in any valid order ‘≺’. We may assume that i_{k} is present (otherwise we are already done), which implies the occurrence of (i + 1)_{k−1} (since i_{k} changes into i_{k−1}); if the tableau switching family computing (S, T) = π_{0}(C) can be shown to satisfy the conditions mentioned before proposition 4.1.1, with respect to interchange of d_{1} and d_{2}, then π_{2}(D_{0}|D_{1}|D_{2}) will correspond to π_{1}(D). Similar considerations will be needed for E_{0}|E_{1}|E_{2} and e_{i}(D); here the dominoes containing i_{l} and (i + 1)_{l} in the augmentation of e_{i}(D) must be exchanged.

We start with considerations independent of the choice of k. Since the domino d_{2} can be added after d_{1}, the two are not adjacent. We shall now argue that in the tableau switching family computing π_{0}(C), the conditions required to the right of the diagonal member λ^{[m,m]} affected by interchange of d_{1} and d_{2} are always met; these conditions are that Y (λ^{[m+1,n]}/λ^{[m−1,n]}) is a not domino for any n ≥ m. If any of them were, it would be a horizontal domino, since pos(d_{1}) < pos(d_{2}). We claim that this cannot happen, because the square s of the final difference λ^{[m+1,n]}/λ^{[m,n]} (i.e., for maximal n) lies in a row strictly above that of λ^{[m,m]}/λ^{[m−1,m]} (the outer square of d_{1}); since the squares of the supposed horizontal domino are obtained from these by inward respectively outward slides, this gives a contradiction. In fact, we show that s lies strictly above the outer square t of the domino d_{3} of D containing (i + 1)_{k−1}, which lies weakly above the outer square of d_{1}. We augment D_{2} as at its definition, so that d_{2} contains i_{k−1} and d_{3} contains (i + 1)_{k−1}; by proposition 4.1.1, the second component of π_{1}(D_{2}) has a similar augmentation. Its square containing i_{k−1}, which is s, then lies strictly above the one containing (i + 1)_{k−1} which, being obtained by an outward slide from t, already at the bottom of its column in D, lies in the same row as t.

It remains to show that the conditions required to the left of λ^{[m,m]} are also met. For this we need an additional assumption, namely that the square of λ^{[m+1,m]}/λ^{[m,m]} (the inner square of d_{2}) lies strictly above any square of D_{1}; it then lies in particular above any square obtained by inward slides from that of λ^{[m,m]}/λ^{[m−1,m]}, which suffices as above. To verify the assumption, we choose k to be the largest ordinate for which the inner square of the domino containing i_{k} in the initial augmentation of D lies in a row strictly above the active region for the application of e_{i}, or if no such k exists, the one for which the combination i_{k} is initially absent. The considerations for e_{i}(D) are symmetric, and lead to choosing for l the smallest ordinate for which the outer square of the domino containing (i + 1)_{l} in the final augmentation of e_{i}(D) lies in a row strictly below the active region, or if no such l exists, the one for which the combination (i + 1)_{l} is finally absent. With these choices, we have achieved a reduction of the verification of theorem 4.2.2 for D to that for D_{1}. Proof of theorem 4.2.2. By the above reductions we may assume that D has entries in {i, i + 1} only, and that all dominoes lie in the rows containing the active region; we may moreover assume that if transforming the augmentation of D into that of e_{i}(D) starts with i_{k} absent and ends with (i + 1)_{l} absent, then k ≤ j ≤ l for all ordinates j. If the active region for the application of e_{i} to D consists either of a single domino or of a configuration C_{1}, its top right corner contains i + 1 in D, and its bottom left corner contains i in e_{i}(D), so that there can be no entries i to the right nor entries i + 1 to the left; it then follows that D is reduced to the active region. In these cases the theorem is verified by a simple computation, displayed below. Like before we distinguish the components of the tableau switching pairs by italic and bold entries, and subtract i from all entries, so that they become 0 or 1; we also display ordinates, running from 0 up to r, with r′ = r − 1. Horizontal arrows denote applications of e_{i} (to each component in case of tableau switching pairs), and vertical arrows applications of π_{1}:

\begin{aligned}1_{0} & → & 0_{0} \\ ↓ & & ↓ \\ 1_{0} 1_{0} & → & 0_{0} 0_{0} \end{aligned} ; \begin{aligned}1_{0} & → & 0_{0} \\ ↓ & & ↓ \\ 1_{0} 1_{0} & → & 0_{0} 0_{0} \end{aligned} ; \begin{aligned}0_{r} 1_{r} 0_{r′} 1_{r′} . . . . . . 0_{1} 1_{1} 1_{0} & → & 0_{r} 0_{r′} 1_{r′} . . . . . . 0_{1} 1_{1} 0_{0} 1_{0} \\ ↓ & & ↓ \\ 0_{r}  0_{1} 1_{0} 0_{r}  0_{1} 1_{r}  1_{1} 1_{r}  1_{1} 1_{0} ⋯  · · · · · ·  ⋯ & → & 0_{r} 0_{r′}  0_{0} 0_{r′}  0_{0} 1_{r′}  1_{0} 0_{r} 1_{r′}  1_{0} ⋯  · · · · · ·  ⋯ \end{aligned} .

The case involving a transformation T_{0} is more complicated. In the top row of the active region, there may be horizontal dominoes with entry i to its right, and in the bottom row there may be dominoes with entry i + 1 to its left; these are accompanied by an equal number of entries i + 1 respectively i in the remaining rows, each of which may be divided into a number of horizontal and vertical dominoes. Hence this case is governed by four free parameters; in the diagram below these are determined by the values of the ordinates 0 ≤ n < p ≤ q ≤ r (as before we subtract a common offset from all ordinates to make the smallest one equal to 0). We indicate certain sequences of horizontally repeated dominoes or squares with equal entries by an ellipsis, but to avoid excessive width, we alternatively indicate such repetition by displaying just one domino or square, with an asterisk attached to its entry; in that case the ordinate given is the leftmost (largest) one of the sequence. Primes attached to ordinates signify subtraction of 1.

0_{r}^{∗} 0_{q}^{∗} 0_{p} 0_{p′}  0_{1} 1_{r} ⋯ 1_{p} 1_{p′} · · 1_{n} ⋯ 1_{0} · · · · ·  →  0_{r}^{∗} 0_{q}^{∗} 0_{p} 0_{p′} 0_{p′′}  0_{0} 1_{r′} ⋯ 1_{p′} · · 1_{n} ⋯ 1_{0} · · · · ·

↓  ↓

0_{r}^{∗} 0_{q}  0_{1} 1_{0} 1_{r} · · 1_{p}  1_{1} 0_{r} · · 0_{p} 0_{p′}  0_{1} 1_{r} 1_{r′}  1_{n}  1_{n′}^{∗} 1_{0}· · · · · · · · · · · · · · ·  →  0_{r}^{∗} 0_{q}  0_{1} 0_{0} 1_{r′} · · 1_{p′}  1_{0} 0_{r′} · · 0_{p′}0_{p′′}  0_{0} 0_{r} 1_{r′}  1_{n}  1_{n′}^{∗} 1_{0}· · · · · · · · · · · · · · ·

The shape of the tableaux is indicated only schematically, and away from the active region, vertical alignment is mostly accidental; however, in the bottom left diagram the alignment of 1_{p} and 1_{r} and that of 1_{0} and 0_{p} are always as indicated, as are the corresponding alignments in the bottom right diagram. It may be verified that the diagram correctly describes the computation for all possible parameter values.

§5. Moving chains and coplactic operations. In this section we shall consider the same kind of questions as in the previous one, but replacing the correspondence π_{1} by the operation of moving chains. In will be necessary to limit the type of chains in order to obtain the desired properties; in particular commutation with coplactic operations is obtained for the operation of moving open chains.

5.1. Moving chains in augmented domino tableaux. Let a semistandard domino tableau D be given, and a chain C for s ∈ {s_{0}, s_{1}} in D that is not a forbidden chain, then [vLee3, proposition 4.3.1] tells us that it can be moved in D, resulting in another semistandard domino tableau D′. We suppose that D is ν/κ-dominant, and ask under which circumstances the same is true for D′; this generalises the question when moving a chain preserves the Yamanouchi property. It is easy to see that if we augment D for ν/κ, and move the ordinates of the dominoes in C along with that domino, then conditions a and b of definition 3.1.1 are satisfied (in fact the forbidden chains are precisely those that would violate condition b); therefore our question is equivalent to asking whether condition c is satisfied. Fix i, j for which there are dominoes in Dom(D) containing respectively i_{j} and (i + 1)_{j}, at least one of which lies in C. The positions of their fixed squares for s are congruent modulo 2, and a violation of condition c can only occur if these positions are equal. If so, we have a configuration

\begin{matrix}i_{j} \\ i^{+} & j \end{matrix} ,  (9)

(where i^{+} denotes i + 1), with the fixed squares for s on its main diagonal. If the top domino lies in C, then either the bottom domino is its successor in C, or there is another configuration (9) directly to the left of the one considered, but with ordinates j + 1 instead of j; similarly if the bottom domino lies in C, then either the top domino is its successor in C, or there is another configuration (9), with ordinates j −1, to the right of this one. It follows that condition c of definition 3.1.1 is violated if and only if C meets a configuration (9), in which case it is a closed chain, all of whose dominoes occur in such a configuration. The following definition covers both such pairs of dominoes and the ones forming a forbidden chain.

5.1.1. Definition. Let D be an semistandard domino tableau, provided with an augmentation for ν/κ. A pair of dominoes of D is called blocked for s ∈ {s_{0}, s_{1}} if the positions of their fixed squares for s are equal, and their entry-ordinate combinations correspond to adjacent squares of Y (ν/κ). A chain in D for s is called blocked if any of its dominoes occurs in a blocked pair, and unblocked otherwise.

5.1.2. Proposition. Let D be a semistandard domino tableau, provided with an augmentation for ν/κ, and C a chain in D for s ∈ {s_{0}, s_{1}}. A ν/κ-dominant tableau can be obtained from D by moving C if and only if C is unblocked, which is the case as soon as any domino of C is not part of a blocked pair.

The notions of blocked pairs and blocked chains depend on the augmentation of D. However, open chains are never blocked, so in particular moving open chains in preserves the Yamanouchi property; this proves our second main theorem, 2.2.6. Also, whether or not a chain in an augmented tableau is blocked does not change when other (unblocked) chains are moved, which proves lemma 2.3.1.

5.1.3. Proposition. If D is semistandard domino tableau, provided with an augmentation, then any unblocked chain C in D for s is also a chain in any specialisation of the augmentation of D.

Proof. Let D′ be the result of moving C in D, which by proposition 5.1.2 can be augmented for the same skew shape as D was; for every occurring i_{j}, the dominoes of D and D′ containing that combination have their fixed square for s in common. Then for any valid order ‘≺’ the fact that D_{≺} and D′_{≺} are standard domino tableaux (proposition 3.1.2) implies that C is a chain of D_{≺}. We may also formulate this as follows. To determine the successor and predecessor relations of the chain C, the entries in the standardisation of D of certain pairs of dominoes in Dom(D) had to be compared, which is equivalent to comparing their entry-ordinate combinations using the Semitic order. The corresponding two dominoes in Dom(D′) are always adjacent, and since D′_{≺} is a well defined standard domino tableau, this implies that the comparison of their entry-ordinate combinations using ‘≺’ gives the same result as using the Semitic order.

The fact that, by definition 5.1.1, the entry-ordinate combinations in a blocked pair of a domino tableau augmented for ν/κ define a domino inside Y (ν/κ), is the key to the construction of theorem 2.3.2. Proof of theorem 2.3.2. Recall that, for each individual domino d of an augmented Yamanouchi domino tableau in Yam_{2}(λ, μ), we constructed a pair of dominoes forming a 2×2 block inside the diagram Y (μ^{⊔ ⊓}), with top-left corner at (2i, 2j) if d contains i_{j}. These dominoes, considered in isolation, can be made into a blocked pair for s_{1}, by giving them entry-ordinate combinations corresponding to the coordinates of the squares of d (using the inward square of d for the domino with the larger position). Note that these entries agree with the ones we assigned in the construction, and that the assignment of ordinates was also already shown in our example in §2. It is easy to see that this gives is a bijective correspondence between on one hand tilings L of Y (λ) with dominoes, each provided with an entry and ordinate, satisfying only condition a of definition 3.1.1 for ν/κ = μ/0 (without requirement of belonging to a semistandard domino tableau), and on the other hand tilings M of Y (μ^{⊔ ⊓}) with blocked pairs of dominoes, with the entries and ordinates again satisfying only condition a of definition 3.1.1, but for ν/κ = λ/0. What remains to be shown is that L defines an augmentation of a semistandard domino tableau if and only if M does so.

First note the semistandardness of an assignment of entries to a tiling of a diagram with dominoes can be tested by comparing adjacent dominoes: when two dominoes touch along a vertical edge, their entries should increase weakly from left to right, and when they touch along a horizontal edge, their entries should increase strictly from top to bottom. This test can be seen to succeed for L or M if the other satisfies definition 3.1.1. For M, we need only consider edges between different 2 × 2 blocks. For horizontal edges, the condition follows because both squares of the domino containing (i + 1)_{j} in L lie strictly below those of the domino containing i_{j}. For vertical edges one similarly uses weak increase of row numbers from i_{j} to i_{j+1}, which fails only in one case when i_{j} and i_{j+1} themselves fill a 2 × 2 block in L, but that case is readily checked to cause no problem either. Semistandardness of L is verified similarly, but here row numbers are divided by 2 (and truncated to an integer), which causes strict increase down columns to be the subtler of the two conditions: if square (r, c) belongs to a different domino of L than (r + 1, c), then the domino of M containing r_{c} cannot lie entirely in an even row 2i, which forces its row number to remain strictly smaller than that of the domino containing (r + 1)_{c}, even after division by 2 and truncation. The verification of conditions b and c of definition 3.1.1 proceed almost by reversal of these arguments, but in addition to monotonicity of entries one uses strict decrease of ordinates along rows and weak decrease down columns (which is easily checked), so that the difference j − i for combinations i_{j} decreases strictly both along rows and down columns (not counting the places where one stays within a domino, of course). For M this suffices to establish the mentioned conditions, since the necessary comparisons of the positions of dominoes can be done based only on the 2×2 blocks containing them (which may be assumed distinct); for L one observes that for these comparisons one may compare the contents of the inward dominoes of the corresponding 2 × 2 blocks in M, or equivalently the contents associated to the top-left squares of these blocks.

The fact that L and M have partition shapes plays no rôle at all in the proof above; these conditions are simply remnants of the fact that we had not yet introduced the notion of ν/κ-dominance when stating theorem 2.3.2, but only the notion of Yamanouchi domino tableau. We can therefore generalise as follows:

5.1.4. Corollary. For any pair of skew shapes χ, ψ with |χ| = 2|ψ|, there is a bijection between the set of ψ-dominant domino tableaux L of shape χ, and the set of χ-dominant domino tableaux M of shape ψ^{⊔ ⊓} for which there is no chain for s_{1} that can be moved without destroying its χ-dominance. The bijection is given by the construction of theorem 2.3.2, applied to the appropriate augmentations; in particular 2 Spin(L) = |ψ|−Spin(M) (i.e., M has twice as many horizontal dominoes as L has vertical dominoes).

In the particular case that χ = λ/μ is a horizontal strip (its columns have length at most 1), every domino tableau M of weight λ−μ is χ-dominant. Then any M in the corollary consists only of forbidden chains for s_{1}, and the set of all such M is in bijection, not just with the indicated set of domino tableaux L, but more directly (by shrinking each forbidden chain to a single square) with the set of M′ ∈ SST(ψ) with wt M′ = \frac{1}{2}(λ − μ); it is the latter correspondence that was used in the derivation of equation (5).

5.2. Coplactic operations and moving open chains. We have now proved all the facts announced in §2, but one more question deserves to be considered, namely whether coplactic operations commute with moving open chains. We already know that moving open chains does not affect the applicability of coplactic operations (since it preserves ν/κ-dominance), and the close analogy to [vLee5, theorem 3.3.1] is a strong indication for expecting commutation. That one does in fact have commutation, as we shall now demonstrate, is therefore not surprising, but a proof still requires a considerable amount of work, and the verification of quite a few particular cases.

5.2.1. Theorem. Coplactic operations on domino tableaux commute with moving of open chains, in the following sense. If D ∈ SSDT(χ), C is an open chain in D for s ∈ {s_{0}, s_{1}}, and D′ is obtained by moving C in D, then c(D) is defined if and only if c(D′) is, for any coplactic operation c; if so, the result of moving the open chain C′ of c(D) starting in the same square as C is equal to c(D′).

Proof. We may assume that c = e_{i}, and (since the statement about applicability of coplactic operations is already proved) that e_{i}(D) is defined. We set E = e_{i}(D), and denote the result of moving C′ in E by E′; we then have to show that E′ = e_{i}(D′). We provide D with the augmentation that is transformed into one of E by the definition of coplactic operations, and provide D′, E′, and e_{i}(D′) with corresponding augmentations.

Assume first that C = C′ (i.e., these chains consist of the same sequence of dominoes; their entries and ordinates in D respectively E may differ); we must show that in this case the steps performed in the application of e_{i} to D (replacements of entry-ordinate pairs and possibly a transformation T_{0} or T_{1}) are matched exactly in the application of e_{i} to D′. It is clear that if a transformation T_{0} or T_{1} occurs, the affected configuration C_{0} or C_{1} is disjoint from C, since all dominoes of C must remain in E in order to have C = C′. It therefore suffices to show that every replacement i_{j} ← i_{j+1} or i_{j} ← (i + 1)_{j} during the computation of e_{i}(D) has its counterpart in the computation of e_{i}(D′). We may assume that both candidate combinations i_{j+1}, (i + 1)_{j} for this replacement are present in the augmentation of D (and of D′), for otherwise the statement is obvious for lack of choice; let {x, y} ⊆ Dom(D) be the dominoes containing these combinations, with the one of x actually being replaced (so pos(x) > pos(y)). Denoting by x′, y′ ∈ Dom(D′) the corresponding dominoes after moving C, it follows from C′ = C that x′, y′ ∈ Dom(E′), and that x′ contains i_{j} in the augmentation of E′, while y′ contains the same combination ((i + 1)_{j} or i_{j+1}) as it does in the augmentation of D′. This implies that the union of x′ and y′ is a skew diagram, and that pos(x′) > pos(y′), which proves the required statement.

The remainder of the proof, which shows that in all cases with C ≠ C′ one has commutation as well, will appeal mainly to the kind of people who like to study the solutions of chess problems (but those who prefer to find the solution themselves may stop reading and do just that). We shall start by listing a number of variants in which the theorem can be seen to hold, and then show that with C ≠ C′, there is no way to avoid running into one of them. From any variant ϕ, three others can be obtained by the following symmetries related to those of the “rectangle” of tableaux [{D \atop D′} {E \atop E′} ]; these will not be listed separately. A variant denoted by ϕ^{↕} is obtained by interchanging D ↔ D′ and E ↔ E′ and reversing the movement of the chains C and C′. A variant denoted by ϕ^{↔} is obtained by interchanging D ↔ E and D′ ↔ E′ while rotating all tableaux a half-turn and renumbering entries and ordinates in the opposite order, so as to interchange the rôles of i and i + 1. The third variant is ϕ^{×} = ϕ^{↕↔} = ϕ^{↔↕}.

We do not make the assumption that D has entries in {i, i + 1} only, since suppression of the remaining entries might change the structure of the chain C. However, we shall focus on a specific part of D only, in which all entries are in {i, i + 1}, and which in all cases has the property that the dominoes not lying in the explicitly indicated part of C are member of a blocked pair for s, whence they cannot be part of C, regardless of the suppressed context (the situation for E, D′ and E′ is similar). Some cases involve transformations T_{1}, and correspondingly have one or more parameters describing how often certain elements of the configurations are repeated horizontally. We include the case of zero repetitions, whenever this makes sense; we then also consider a replacement i_{j} ← (i + 1)_{j} in a vertical domino as an instance of the transformation T_{1} with k = 0. We display entries with their ordinates (as before subtracting offsets to make the smallest ones 0), and indicate the relevant part of the open chain in each tableau by arrows. The fact that the chains and the effect of e_{i} are as displayed, implies that any repeatable element is included in the display as often as the context allows. We start giving variants that we shall call α(k, l), for parameters k ≥ l ≥ 0 (variant α(0, 0) has C = C′, and may be excluded).

\begin{matrix}D: 0_{k} 1_{k} . . . . . . 0_{l+1} 1_{l+1} 1_{l} 0_{l} 1_{l−1} . . . . . . 0_{1} 1_{0} → → → ↑ ← ← ← & \underrightarrow{e_{i}} & E: 0_{k} 0_{k−1} 1_{k−1} . . . . . . 0_{l} 1_{l} 0_{l−1} 1_{l−1} . . . . . . 0_{1} 1_{0} ← ← ⟷ → → ↑ \\ ↓C & \underline{\overline{\underline{\overline{α(k, l)}}}} & ↓C′ \\ D′: 0_{k} 1_{k} . . . . . . 0_{l+1} 1_{l+1} 0_{l} 1_{l} . . . . . . 0_{1} 1_{1} 1_{0} ↓ ← ← ⟷ → → & \underrightarrow{e_{i}} & E′: 0_{k} 1_{k−1} . . . . . . 0_{l+1} 1_{l} 0_{l} 0_{l−1} 1_{l−1} . . . . . . 0_{1} 1_{0} → → → ↓ ← ← ← \end{matrix}

Note that variant α(k, l)^{×} coincides with α(k, k − l). Then one has variants β(k) for k > 0, obtained by modifying α(k, 0) slightly: upward arrows at the end of chains C and C′ in α(k, 0) are replaced by rightward arrows in β(k), which does not affect the essential characteristics of the configuration.

\begin{matrix}0_{k} 1_{k} . . . . . . 0_{1} 1_{1} 1_{0}→ & \underrightarrow{e_{i}} & 0_{k} 0_{k−1} 1_{k−1} . . . . . . 0_{0} 1_{0} ← ← ⟷ → → → \\ ↓C & \underline{\overline{\underline{\overline{β(k)}}}} & ↓C′ \\ 0_{k} 1_{k} . . . . . . 0_{1} 1_{1} 1_{0} ↓ & \underrightarrow{e_{i}} & 0_{k} 1_{k−1} . . . . . . 0_{1} 1_{0} 0_{0} → → → ↓ ← ← ← \end{matrix}

A third family of variants is γ(k) for k ≥ 1. Here both a transformation T_{1} (for e_{i} applied to D) and a transformation T_{0} (for e_{i} applied to D′) occur. Similar variants γ′(k) are obtained from γ(k) by changing the direction at the beginning of the chains C and C′.

\begin{matrix}0_{k} 1_{k} . . . . . . 1_{1} 0_{1} 1_{0} ← & \underrightarrow{e_{i}} & 0_{0} 1_{0} 0_{k} . . . . . . 0_{1} 1_{1} ← ⟷ →  ↓ ← ↑ \\ ↓C & \underline{\overline{\underline{\overline{γ(k)}}}} & ↓C′ \\ 0_{k} 1_{k} . . . . . . 1_{1}0_{1}1_{0} ↑ & \underrightarrow{e_{i}} & 0_{1} 0_{0} 1_{0} 0_{k} 1_{k−1} . . . . . . → → ↓ ← ← ↑ ↑ \end{matrix}  \begin{matrix}0_{k} 1_{k} . . . . . . 1_{1} 0_{1} 1_{0} ← & \underrightarrow{e_{i}} & 0_{0} 1_{0} 0_{k} . . . . . . 0_{1} 1_{1} ← ⟷ →  ↓ ← ↑ \\ ↓C & \underline{\overline{\underline{\overline{γ′(k)}}}} & ↓C′ \\ 0_{k} 1_{k} . . . . . . 1_{1}0_{1}1_{0}→ & \underrightarrow{e_{i}} & 0_{1} 0_{0} 1_{0} 0_{k} 1_{k−1} . . . . . . → → ↓ ← ← → ↑ \end{matrix}

The final variants involve transformations T_{0} in applying e_{i} both to D and to D′, but at different (overlapping) places; they have no parameters. The direction of C and C′ can be varied at both ends, giving 4 such variants: δ, δ′ and δ′′ displayed below, and δ^{′×}.

\begin{matrix}0_{1} 0_{2} 1_{2} 1_{1} 1_{0} ← ↓ ↓ & \underrightarrow{e_{i}} & 0_{0} 1_{0} 1_{1} 0_{2} 0_{1} ↓ ← ↓ \\ ↓C & \underline{\overline{\underline{\overline{δ}}}} & ↓C′ \\ 0_{1} 0_{2} 1_{2} 1_{1} 1_{0} ↑ → ↑ & \underrightarrow{e_{i}} & 0_{0} 1_{0} 1_{1} 0_{2} 0_{1} ↑ ↑ → \end{matrix}  \begin{matrix}0_{1} 0_{2} 1_{2} 1_{1} 1_{0} ← ↓ ↓ & \underrightarrow{e_{i}} & 0_{0} 1_{0} 1_{1} 0_{2} 0_{1} ↓ ← ↓ \\ ↓C & \underline{\overline{\underline{\overline{δ′}}}} & ↓C′ \\ 0_{1} 0_{2} 1_{2} 1_{1} 1_{0}→ → ↑ & \underrightarrow{e_{i}} & 0_{0} 1_{0} 1_{1} 0_{2} 0_{1} → ↑ → \end{matrix}  \begin{matrix}0_{1} 0_{2} 1_{2} 1_{1} 1_{0} ← ↓ ← & \underrightarrow{e_{i}} & 0_{0} 1_{0} 1_{1} 0_{2} 0_{1} ↓ ← ← \\ ↓C & \underline{\overline{\underline{\overline{δ′′}}}} & ↓C′ \\ 0_{1} 0_{2} 1_{2} 1_{1} 1_{0}→ → ↑ & \underrightarrow{e_{i}} & 0_{0} 1_{0} 1_{1}0_{2} 0_{1} → ↑ → \end{matrix}

We now proceed to show that C′ ≠ C implies that, up to the mentioned symmetries, one of these variants arises. We label the cases that can arise in the application of e_{i} to D as follows: case a means a replacement i ← (i + 1)_{j} occurs in a horizontal domino; case b means that a transformation T_{0} occurs; case c means that a transformation T_{1} occurs (which we take to include a replacement i ← (i + 1)_{j} in a vertical domino). In all cases the active region for the application of e_{i} is rectangular, and of its top-left and bottom-right corner squares exactly one is fixed for s; by applying the symmetry ϕ → ϕ^{↔} if necessary, we assume that it is the top left square.

Assuming C ≠ C′ as we do, there are two possibilities for the first point of divergence between C and C′: (1) some domino of C does not occur in Dom(E) (due to rearrangement of dominoes), and (2) the successor y in C of some domino x does occur in Dom(E), but it is not the successor of x in C′. Recall from [vLee3, 4.1] that successor of x is determined by comparing its entry to that of the domino occupying its “discriminant square”, which is one step in the anti-diagonal direction away from the fixed square (for s) of x (if the discriminant square lies outside D, then the test depends only on the shape of D, and we cannot have possibility (2)). Therefore, possibility (2) requires that the entry either of x itself or of the domino containing the discriminant square is changed by e_{i}, and in such a way that the result of the comparison changes. Now in each of the cases there is a unique fixed square t_{0} for s for which application of e_{i} changes the entry of its domino: t_{0} is the left square of the active domino in case a, in case b it is the right square of the middle row of C_{0}, and in case c, it is the top-right corner of C_{1}. Let t_{0} be part of a domino x_{0} ∈ Dom(D) containing (i + 1)_{j}, and let t_{1} be the discriminant square of x_{0} (it lies to the bottom-left of t_{0} in case a, and to the top-right of t_{0} otherwise); if in D the square t_{1} is part of a domino containing either (i + 1)_{j+1} (case a) or i_{j} (other cases), then we define x_{1} to be that domino. If possibility (2) applies, the crucial comparison must be between the entries of x_{0} and x_{1}; moreover, in case c it must be that x = x_{1} (since x_{0} ∉ Dom(E)), but in case b, even if x_{1} is defined, its successor lies in C_{0} and therefore not in Dom(E), which excludes possibility (2) altogether.

Suppose first that we are in case a; then Dom(D) = Dom(E), so we have possibility (2). Since x_{0} undergoes a replacement i_{j} ← (i+1)_{j} and x_{1} contains (i+1)_{j+1} in D, there is a domino x_{2} containing i_{j+1} in D, with x_{1} <_{v} x_{2} <_{h} x_{0}. Since x_{0} is horizontal, the only possible configuration is _{x_{1}}^{x_{2}} ^{x_{0}} , so x_{1} and x_{2} form a blocked pair for s, which forces x = x_{0}. By including any further blocked pairs for s with entries i and i + 1 occurring directly to the left of x_{1} and x_{2}, we find an occurrence of β(k)^{↕}.

Suppose next that we are in case b. Now the bottom left domino of C_{0} (containing (i + 1)_{j+1}) is the successor for s of the top domino (containing i_{j+1}). It may be that the remaining domino x_{0} of C_{0} (containing (i + 1)_{j}) forms a blocked pair for s with a domino containing (i + 1)_{j−1} in D; if it does, x_{1} is defined, and one gets one of the variants δ, δ′, δ^{′×}, or δ′′. Otherwise x_{1} may still be defined, but then since its contents is replaced i_{j−1} ← i_{j} when applying e_{i}, it forms a 2 × 2 block of horizontal dominoes with a domino containing (i + 1)_{j−1} in D. Reasoning similarly we may find more such 2 × 2 blocks with entries i and i+1 directly to the right, but the chain through x_{0} eventually turns back and passes through the top and bottom left domino of C_{0}; if k blocks were found, we have a variant γ(k + 1)^{×} or γ′(k + 1)^{×}.

Suppose finally that we are in case c. If x_{1} is not defined we have possibility (1), and the domino where C and C′ diverge must be x_{0} (being in C_{1} and not part of a blocked pair); this leads to a variant α(k, 0) or β(k). Otherwise, since e_{i} causes a replacement i_{j−1} ← i_{j} in x_{1}, there is a domino x_{2} containing (i + 1)_{j−1} in D, with x_{0} <_{h} x_{2} <_{v} x_{1}, and it is the successor of x_{0} for s in D. If vertical, x_{2} forms a blocked pair for s with x_{0}, so that C does not meet C_{1}, and we must have possibility (2); this leads to variant γ(k) or γ′(k). If x_{2} is horizontal, then so is x_{1}, and the two form a 2 × 2 block. As above we may need to include more such blocks with entries i and i+1 to the right, but the chain through x_{0} eventually turns back to pass through x_{1}, excluding possibility (2); this leads to a variant α(k, l) with l > 0.

For the record we mention that more grandiose versions of the commutation theorems 4.2.2 and 5.2.1 can be obtained, by replacing the coplactic operations by the extended construction simulating jeu de taquin on all entry-ordinate pairs that was indicated in subsection 3.2. The argument that reduces these commutation theorems to the ones given is the same as used for [vLee5, corollary 3.4.3]: the number of coplactic operations that correspond to a single jeu de taquin slide can be read off from the coplactic graph, and it therefore does not change when π_{1} is applied or an open chain is moved. The theorems also have a consequence that does not refer to coplactic operations at all; we do not know a direct proof of it.

5.2.2. Corollary. If D′ is obtained from D by moving open chains, then π(D) = π(D′).

Proof. By theorems 5.2.1, 4.2.2, and [vLee5, theorem 3.3.1], we can reduce to the case that D is a Yamanouchi domino tableaux, and D′ will be one as well. But then π(D) = 1_{wt D} = 1_{wt D′} = π(D′).

§6. Concluding remarks.

The complements we have given to the facts stated in [CaLe] result in a fairly complete and elegant theory for domino tableaux, which forms a nice parallel to the theory for ordinary tableaux, as described in [vLee5]. Yet, one may well wonder why all this works out so nicely, and if there is some deeper algebraic significance behind the combinatorial facts. The most general and natural algebraic interpretation of (augmented) domino tableaux that we know of, stated in corollary 4.1.2, seems to cry for a generalisation to higher plethysm operators, involving r-ribbon tableaux for r > 2. However, none of the constructions of this paper generalise well to r-ribbon tableaux, and no reasonable generalisation of the definition of augmented (or even just Yamanouchi) domino tableaux seems to give the correct values (e.g., it is hard to decide which tableaux should correspond to ⟨ϕ^{3}(s_{(4,4,4)}), s_{(2,2)}⟩ = 1 = ⟨ϕ^{3}(s_{(3,3,3,3)}), s_{(2,2)}⟩). The interested reader may check that every analysis in this paper depends on properties of domino tableaux that fail for r-ribbon tableaux with r > 2 (or, as in the case of π_{1}, on constructions that have no analogue at all). One may surmise that the special place of domino tableaux has some relation with classical groups of types other than A_{n}, rather than just with plethysms; such a connection certainly does exist (see [Garf], where even moving chains play a rôle), but at present we cannot indicate any concrete links.

References.

[BeSoSt] G. Benkart, F. Sottile, J. Stroomer, “Tableau switching: algorithms and applications”, J. Combin. Theory, Ser. A 76, (1996), 11–43.

[CaLe] 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.

[FomSt] S. Fomin and D. Stanton, “Rim hook lattices”, St. Petersburg Math. Journal 9, (1998), 1007–1016.

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

[KaNa] M. Kashiwara and T. Nakashima, “Crystal graphs for representations of the q-analogue of classical Lie algebras”, Journal of Algebra 165, (1994), 295–345.

[Knuth] D. E. Knuth, “Permutations, matrices and generalized Young tableaux”, Pacific Journal of Math. 34, (1970), 709–727.

[LaSch] A. Lascoux and M. P. Schützenberger, “Le monoïde plaxique”, Quad. Ricerca Scientifica C.N.R. 109, (1981), 129–156.

[LeTh] B. Leclerc and J.-Y. Thibon, “The Robinson-Schensted correspondence, crystal bases, and the quantum straightening at q = 0”, Electronic J. of Combinatorics 3 (no. 2), R11, (1996), 24 pp.

[vLee1] 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.

[vLee2] M. A. A. van Leeuwen, “Tableau algorithms defined naturally for pictures”, Discrete Mathematics 157, (1996), 321–362.

[vLee3] M. A. A. van Leeuwen, “Edge sequcences, ribbon tableaux, and an action of affine permutations”, European J. of Combinatorics 20, (1999), 179–195.

[vLee4] M. A. A. van Leeuwen, “An analogue of jeu de taquin for Littelmann’s crystal paths”, Séminaire Lotharingien de Combinatoire B41b, (1998), 23 pp.

[vLee5] M. A. A. van Leeuwen, The Littlewood-Richardson rule, and related combinatorics, math.CO/9908099, Submitted to Math. Soc. of Japan Memoirs.

[Litm1] P. Littelmann, “A Littlewood-Richardson rule for symmetrizable Kac-Moody algebras”, Inventiones mathematicae 116, (1994), 329–346.

[Litm2] P. Littelmann, “A plactic algebra for semisimple Lie algebras”, Advances in Math. 124 (2), (Dec. 1996), 312–331.

[Litw] D. E. Littlewood, “Modular representations of symmetric groups”, Proc. Royal Soc. A 209, (1951), 333–353.

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

[Rob] G. de B. Robinson, “On the representations of the symmetric group”, American Journal of Math. 60, (1938), 745–760.

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