1 Introduction

Tableau algorithms defined naturally for pictures

Marc A. A. van Leeuwen CWI Kruislaan 413 1098 SJ Amsterdam The Netherlands

                                email: M.van.Leeuwen@cwi.nl

Abstract We consider pictures as defined in [Zel1]. We elaborate on the generalisation of the Robinson-Schensted correspondence to pictures defined there, and on the result in [FoGr] that shows that this correspondence is natural, i.e., independent of the precise “reading” order of the squares of skew diagrams that is used in its definition. We give a simplified proof of this result by showing that the generalised Schensted insertion procedure can be defined without using this order at all. Our main results involve the operation of glissement defined in [Schü2]. We show that glissement can be generalised to pictures, and is natural. In fact, we obtain two dual forms of glissement; consequently both tableaux corresponding to a permutation in the Robinson-Schensted correspondence can be obtained by glissement from one picture. We show that the two forms of glissement commute with each other. From this fact the main properties of glissement follow in a much simpler way than their original derivation in [Schü2].

§1. Introduction. A picture between skew diagrams is a bijection of their squares satisfying certain conditions that will be given below. For special choices of the domain and/or image diagram, pictures are equivalent to other concepts, such as standard and semi-standard (skew) tableaux, Littlewood-Richardson fillings, and permutations; moreover some well known properties and constructions for these special cases can be generalised to pictures. Zelevinsky has shown in [Zel1] that the number of pictures between any pair of skew diagrams equals the intertwining number of the corresponding representations of the symmetric group, which generalises the Littlewood-Richardson rule, and that the Robinson-Schensted and Schützenberger correspondences have generalisations to pictures. In the definition of these correspondences a particular total ordering ‘≤_{J}’ on Z×Z is used, that also occurs in the definition of pictures themselves; using this ordering on the images of squares, pictures can be viewed as a tableaux, and then the construction of these correspondences coincides with the usual constructions for the tableau case. However, both in the definition of pictures and of the Robinson-Schensted correspondence the use of ‘≤_{J}’ turns out to be inessential: in [ClSt] it was shown that ‘≤_{J}’ can be replaced by the more natural partial ordering ‘≤_{↙}’, and in [FoGr] it was shown that in the definition of the Robinson-Schensted correspondence for pictures ‘≤_{J}’ can be replaced by any total ordering compatible with ‘≤_{↙}’ without affecting the correspondence.

Following [FoGr], let us call a construction involving pictures a natural generalisation of a similar construction for tableaux, when it reduces to that construction by totally ordering the set of images of a picture by some ordering compatible with ‘≤_{↙}’, and when moreover the outcome of the construction is independent of the total ordering used. We investigate the naturality of the Robinson-Schensted and Schützenberger correspondences and the procedures used to define them, and whether the operation of glissement defined in [Schü2] has a natural generalisation to pictures; we find the following results. The Schensted insertion and extraction procedures can be defined for pictures directly in terms of ‘≤_{↙}’, without choosing a total ordering (lemma 3.3.2), which directly implies the naturality of these procedures; thus we obtain a simpler more direct proof of the naturality of the Robinson-Schensted correspondence for pictures than was given in [FoGr] (theorem 3.2.1). Considering the Robinson-Schensted correspondence in relation to symmetries of the plane that preserve the picture property, and using the well known relation between the Robinson-Schensted and Schützenberger correspondences, we find that the Schützenberger correspondence for pictures is also natural (theorem 4.2.1); however the deflation (or evacuation) procedure used to define the Schützenberger correspondence is not natural. We also obtain a (non-obvious) bijection between the sets of pictures with given domain and image and those with the transposed domain and image (theorem 4.3.1).

We show that glissement of skew tableaux has a natural generalisation to pictures (theorem 5.1.1). In this case naturality is in fact a necessary condition for having a proper definition at all; like for the Schensted 2 Pictures

insertion procedure the use of a total ordering can be avoided altogether. The Robinson-Schensted and Schützenberger correspondences can both be expressed in terms of glissement (this holds for pictures in the same way as for tableaux). Due to the fact that the inverse map of a picture is again a picture, we obtain a dual form of glissement as well, that changes the shape of the image rather than that of the domain. This additional operation adds power and symmetry to the theory of glissement; e.g., whereas using ordinary glissement one of the two tableaux associated to a permutation under the Robinson-Schensted correspondence can be obtained from the corresponding skew tableau, one can obtain both these tableaux from the picture corresponding to the permutation, using the two forms of glissement (theorem 5.1.1). A crucial result is that both forms of glissement commute with each other (theorem 5.3.1). This fact sheds light on the fundamental properties of glissement: they follow easily from it (theorem 5.4.1), without using the results of [Schü2], or the properties of the Robinson-Schensted correspondence these are based on. Thus glissements of pictures provide an independent and elementary approach to the theory of the Robinson-Schensted and Schützenberger correspondences, both for pictures and for tableaux.

This paper is organised as follows. In §2 we give definition and basic properties of pictures, and indicate connections with other combinatorial concepts and with the Littlewood-Richardson rule. In §3 we treat the Robinson-Schensted correspondence for pictures, and discuss questions of its naturality. In §4 we continue by studying the relation of the Robinson-Schensted correspondence with symmetries of the set of pictures, and the Schützenberger correspondence. These two sections contain relatively few new results; emphasis lies on describing the correspondences and their properties, and the meaning of naturality. In §5, the theory of glissement for pictures is developed. For this §3 and §4 only serve to provide motivation: their results are not required for the theory, on the contrary, it gives an alternative way to obtain those results.

§2. Pictures.

2.1. Orderings on Z × Z. The starting point for all the objects that we shall study is the integer lattice Z × Z. Its elements will be depicted, and often referred to, as squares, and we shall let the first coordinate increase downwards and the second increase to the right, like matrix indices. We shall employ two different partial orderings on this set; one is the natural coordinatewise ordering that will be denoted by ‘≤_{↖}’, and is defined by

(i, j) ≤_{↖} (i′, j′) ⟺ i ≤ i′ ∧ j ≤ j′

and the other is a transverse ordering denoted by ‘≤_{↙}’ and defined by

(i, j) ≤_{↙} (i′, j′) ⟺ i ≥ i′ ∧ j ≤ j′.

The arrows attached to the ‘≤’ signs are intended as a reminder of the definition, and point in the direction of the smaller elements (like the ‘<’ sign itself). As usual, x <_{↙} y means x ≤_{↙} y and x ≠ y, and similarly for ‘<_{↖}’. Remark. Both the choice of the transverse ordering and the symbols used to represent the orderings are somewhat arbitrary, and not always in agreement with other literature on the subject; for instance in [FoGr] the opposite transverse ordering is used but it is denoted by the same symbol ‘≤_{↙}’. We apologise for any confusion that might result, but since it is impossible to be in agreement with all literature, we have chosen for conventions that are consistent and easy to remember: moving from left to right we increase in both orderings.

Because of the use of different orderings, we shall denote a partially ordered set (or poset for short) explicitly as a pair (A, ≤_{A}) of a set with a partial ordering. Recall that a poset morphism (A, ≤_{A}) → (B, ≤_{B}) is a map f: A → B such that for any a_{1}, a_{2} ∈ A with a_{1} ≤_{A} a_{2} one has f(a_{1}) ≤_{B} f(a_{2}). An order ideal of a partially ordered set (S, ≤) is a subset I of S such that for all x ∈ S and y ∈ I with x ≤ y we have x ∈ I; the complement C = S \ I, which has the property that for all x ∈ C and y ∈ S with x ≤ y we have y ∈ C, is called an order coideal. For future reference we state an alternative characterisation of poset morphisms.

2.1.1. Proposition. A map f: A → B is a poset morphism (A, ≤_{A}) → (B, ≤_{B}) if and only if the inverse image of any order ideal of (B, ≤_{B}) is an order ideal of (A, ≤_{A}).

2.2 Skew diagrams

2.2. Skew diagrams. A skew diagram χ is a finite subset of Z × Z that is convex with respect to the natural ordering, i.e., if x, z ∈ χ and x <_{↖} y <_{↖} z then y ∈ χ; denote the set of all skew diagrams by S. A typical skew diagram can be depicted as follows:

Let P ⊆ S be the set of Young diagrams, i.e., of finite order ideals of (N × N, ≤_{↖}); these correspond bijectively to partitions. The the non-empty Young diagrams are just the skew diagrams that, viewed as poset by the natural ordering, contain the origin (i.e., the square (0, 0)) as unique minimal element. For each μ, ν ∈ P with μ ⊆ ν the difference set ν \ μ is a skew diagram, and if a skew diagram is contained in N × N, it can always be written in this form. However, such an expression is not necessarily unique; for instance, the skew diagram depicted above, where we assume that the origin lies at the intersection of its first row and column, can be written as

\  but also as  \  .

For a skew diagram χ ∈ S define a corner to be a square s ∈ χ such that χ \ {s} is again a skew diagram, and a cocorner to be a square s ∉ χ such that χ ∪ {s} is again a skew diagram. A corner s of χ is called inner respectively outer if s is minimal respectively maximal in the poset (χ, ≤_{↖}), of which at least one is the case. Similarly a cocorner s of χ is called inner or outer according as s is minimal or maximal in (χ ∪ {s}, ≤_{↖}).

2.3. Definition of pictures. Various definitions have been given for pictures by different authors. We shall consider only the case that domain and image are skew diagrams, where all these definitions (and that of “good maps” in [FoGr]) become equivalent, up to some trivial symmetries*.

2.3.1. Definition. Let χ, ψ ∈ S and f: χ → ψ a bijection; f is called a picture if it is a morphism of partially ordered sets (χ, ≤_{↖}) → (ψ, ≤_{↙}), and f^{−1} is a morphism (ψ, ≤_{↖}) → (χ, ≤_{↙}).

To display a picture, we may label each square of χ and its image in ψ with a unique letter, giving for instance

\begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} χ  \underrightarrow{f}  ψ e c ; f g b ; d ; a

Let Pic(χ, ψ) denote the set of all pictures from χ to ψ. From the definition of pictures it is clear that if f is a picture, then so is f^{−1}, so that Pic(χ, ψ) is in bijection with Pic(ψ, χ). For translations t_{1}, t_{2} of Z × Z we also have an obvious bijection between Pic(ψ, χ) and Pic(t_{1}(ψ), t_{2}(χ)). The set S is closed under the operations of transposition (given by (i, j) ↦ (i, j)^{t} = (j, i)) and central symmetry (given by (i, j) ↦ −(i, j) = (−i, −j)). One easily verifies that by appropriate composition with these reflections bijections of Pic(χ, ψ) with Pic(χ^{t}, −ψ^{t}), Pic(−χ^{t}, ψ^{t}), and Pic(−χ, −ψ) are obtained. Here are the results of applying these symmetries to the picture displayed above.

f ; a d g ; b e ; c ⟶ c ; b e ; g ; a d f  c ; e b ; g d a ; f ⟶ f d a ; g ; e b ; c  \begin{aligned}& & g & f \\ & e & d \\ c & b & a \end{aligned} ⟶ a ; d ; b g f ; c e

* Our pictures are transposed at domain and image side with respect to those of [Zel1] and [ClSt]. For the

pictures of [JaPe], and the good maps of [FoGr], one should apply reflection in a horizontal axis at the image

side (the image shape is then not a skew diagram, but rather convex for ‘≤_{↙}’).

2.4 Encodings of pictures and special cases: permutations and tableaux

Applying transposition at both domain and image side does not preserve the picture conditions; nevertheless a bijection between Pic(χ, ψ) and Pic(χ^{t}, ψ^{t}) exists, and we shall construct such a bijection later.

The picture condition can be made more explicit by making a table of allowed relative positions of images. To an ordered pair of distinct squares we associate one of eight possible relative positions, by determining for both their coordinates whether that of the first square is less than, equal to, or greater than that of the second; these positions can be indicated by the eight compass directions. The following table expresses the allowed combinations of the relative position of a pair of squares and of their images under a picture. In reasoning about pictures we shall often use this table without explicit mention.

f → ↘ ↓ ↙ ← ↖ ↑ ↗
→ •  •
↘  •
↓  • •
↙  • • • • •
←  • •
↖  •
↑  • •
↗ • • • •  •

2.4. Encodings of pictures and special cases: permutations and tableaux. There are other ways of representing pictures than shown above. The row encoding (respectively column encoding) of a picture f: χ → ψ is obtained by filling each square s of χ with the number that is the first (respectively second) coordinate of f(s). For the picture shown above, these are

3 1 0 2 0 1 1  respectively  0 2 3 0 2 0 1

(where we have assumed that the origin lies in the topmost row and leftmost column of ψ). Since each row and column is totally ordered by ‘≤_{↖}’, either the row or the column encoding fully determines f, if ψ is given. The poset morphism property for f implies that in the row encoding the rows are weakly decreasing and the columns strictly decreasing, while in the column encoding rows are strictly increasing and columns weakly increasing. To obtain tableaux with weakly increasing rows and strictly increasing columns (as semistandard tableaux are usually defined) one may use negated row encoding (filling each square with minus the row coordinate of its image).

In addition to these monotonicity conditions on rows and columns, the definition of pictures poses some less obvious conditions. However, for certain kinds of skew diagrams these conditions simplify, and thus we can get various kinds of combinatorial objects as special cases of (encodings of) pictures. For instance, if ψ is an anti-chain for ‘≤_{↖}’ (i.e., no two distinct squares are comparable), then the poset morphism condition for f^{−1} is trivially satisfied, and the poset morphism condition for f similarly becomes trivial if χ is an anti-chain. Hence if both χ and ψ are anti-chains for ‘≤_{↖}’, then pictures are just arbitrary bijections or, via column encoding, permutations. If only ψ is an anti-chain, we similarly get the notion of a skew tableau, and if moreover χ is a Young diagram, that of a (standard) Young tableau. If we interchange χ and ψ, then a Young tableau will be represented by the anti-chain χ filled with numbers such that, when read from bottom left to top right, they form a “lattice permutation” or mot de Yamanouchi. Here is an example of such a picture, its column encoding, and that of its inverse.

a c e ; b g ; d ; f → g ; f ; e ; d ; c ; b ; a ,  0 2 4 1 6 3 5 ,  1 0 2 0 1 0 0

2.5 Alternative characterisations of pictures

If we take for ψ a horizontal strip, i.e., a skew diagram with at most one square in each column, then we get as negated column encodings tableaux in which identical entries allowed, subject only to the mentioned monotonicity conditions. Thus we get semistandard tableaux (called generalised Young tableaux in [Knu1]) as special cases of pictures, for instance

1 1 1 2 4 7 2 3 3 5 3 4 6 6 6 is represented by a b c e j o ; d g h k ; f i m n ; l → o ; l m n ; k ; i j ; f g h ; d e ; a b c .

If we also take for χ a horizontal strip, then a picture is fully specified by giving for each row of χ how many of its squares map to each row of ψ. These data precisely describe a generalised permutation in the sense of [Knu1], which can be represented by an integer matrix or by a two-line array. For instance, the generalised permutation represented by the matrix

( \begin{matrix}0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) or by the two-line array \binom{1 2 2 3 3 3 3 3 4 4 5 5 5 5 6}{3 6 6 1 2 3 4 6 3 5 1 1 2 4 7}

corresponds to the picture

o ; b c e j ; h k ; a d g i n ; l m ; f → o ; l m n ; k ; i j ; f g h ; d e ; a b c .

Finally, if we take for χ a vertical strip (no two squares in one row) while ψ remains a horizontal strip, then pictures are more restricted, since the image of any column of χ can have at most one square in common with any single row of ψ; these pictures correspond to the restricted generalised permutations in [Knu1], that can be represented by zero-one matrices.

2.5. Alternative characterisations of pictures. Using proposition 2.1.1, we can characterise pictures f: χ → ψ as follows: f is a bijective poset morphism (χ, ≤_{↖}) → (ψ, ≤_{↙}) that maps each order ideal of (χ, ≤_{↙}) to an order ideal of (ψ, ≤_{↖}) (which is a skew diagram). In view of this it is desirable in checking the picture condition to replace ‘≤_{↙}’ by a stronger ordering (fewer incomparable pairs); then there will be fewer order ideals to test. The following proposition states that, surprisingly, this can be done in an arbitrary way without weakening the condition; it was found independently by the author [vLee1] and by Fomin and Greene [FoGr, Lemma 3.4].

2.5.1. Proposition. Let f: χ → ψ be a bijection between two skew diagrams, and assume that for all pairs x, y ∈ χ the following two conditions hold:

(i) we do not simultaneously have x <_{↖} y and f(y) <_{↙} f(x), (ii) we do not simultaneously have f(x) <_{↖} f(y) and y <_{↙} x. Then f is a picture.

Proof. The proof is fairly simple, but it essentially uses the two defining conditions for skew diagrams, namely finiteness and convexity with respect to ‘≤_{↖}’. Suppose f satisfies the conditions of the proposition but is not a picture. Then possibly after replacing f by f^{−1}, we may assume the existence of a pair x, y ∈ χ with x <_{↖} y but f(x) ≮_{↙} f(y); moreover by convexity we may assume x to lie either in the same row or in the same column as y. The latter case may be reduced to the former by replacing f by the corresponding bijection χ^{t} → −ψ^{t}, so assume x and y lie in the same row. It then follows from the assumptions that f(x) <_{↖} f(y) and in fact f(y) lies strictly to the right and below f(x). There may be several pairs (x, y) with these properties, but by finiteness of χ we may choose (x, y) among such pairs to lie in the first (i.e., highest) possible row of χ. Now let p be the square lying in the same column as f(x) and in the same row as f(y) (see the illustration below); by convexity of ψ we have p ∈ ψ. From the conditions given it follows that f^{−1}(p) lies in some row above that of x (and y) and in some column to the left of that of y. Now let q be the point in the same row as f^{−1}(p) and in the same column as y; by convexity of χ we have q ∈ χ. By similar reasoning as for f^{−1}(p) we argue that f(q) lies below the row of f(y) (and p) and to the right of the column of p.

\begin{matrix}f^{−1}(p) & q \\ x & y \end{matrix}  χ  ψ  \begin{aligned}f(x) \\ p & f(y) \\ & f(q) \end{aligned}

But then we have p ≮_{↙} f(q), whence (f^{−1}(p), q) is a pair of points with the same properties as (x, y), but in a row above them, contradicting the choice of (x, y). Therefore the assumption that f is not a picture must have been false.

2.5.2. Corollary. Let f: χ → ψ be a bijection between skew diagrams, and let ‘≤_{χ}’ and ‘≤_{ψ}’ be partial (or total) orderings on χ and ψ respectively such that x ≤_{↙} y implies x ≤_{χ} y for x, y ∈ χ, and x ≤_{ψ} y for x, y ∈ ψ. Then f is a picture if and only if f is a poset morphism (χ, ≤_{↖}) → (ψ, ≤_{ψ}) and f^{−1} is a poset morphism (ψ, ≤_{↖}) → (χ, ≤_{χ}).

Proof. Clearly the stated conditions are necessary. On the other hand, if they hold, then the conditions of proposition 2.5.1 will also hold, and f is a picture.

As indicated above, a practical application of this corollary is to reduce the amount of work in testing the poset morphism condition for f^{−1} in terms of order ideals. Taking for ‘≤_{χ}’ a total ordering, and for ‘≤_{ψ}’ simply ‘≤_{↙}’, one finds that a bijection f: χ → ψ is a picture if and only if it is a poset morphism f: (χ, ≤_{↖}) → (ψ, ≤_{↙}), and the image of each order ideal of (χ, ≤_{χ}) is an order ideal of (ψ, ≤_{↖}). The order ideals of (χ, ≤_{χ}) can be enumerated by starting with the empty set and successively adjoining the squares of χ in increasing order for ≤_{χ}; the image of each new square must be an outer cocorner of the skew diagram formed by the images of the squares already present in the previous order ideal. Testing the poset morphism condition for f can be done in the same order, by simply comparing the image of each new square with individual images of previous squares; by the convexity of χ it suffices to consider only the squares directly below and to the left of the new square, whenever they lie in χ.

For a total ordering compatible with ‘≤_{↙}’ there are two particularly obvious candidates, namely the orderings ‘≤_{r}’ by rows and ‘≤_{c}’ by columns, defined by

(i, j) ≤_{r} (i′, j′) ⟺ i > i′ ∨ (i = i′ ∧ j ≤ j′) and (i, j) ≤_{c} (i′, j′) ⟺ j < j′ ∨ (j = j′ ∧ i ≥ i′). The total ordering ‘≤_{J}’ that is used instead of ‘≤_{↙}’ in the definition of pictures in [Zel1] and [ClSt] is the opposite of ‘≤_{r}’, and therefore not compatible with our ‘≤_{↙}’; to match their pictures with ours everything must be transposed, in which case ‘≤_{J}’ corresponds to ‘≤_{c}’. The special case of corollary 2.5.2 where this ordering is taken for ‘≤_{χ}’ and ‘≤_{ψ}’ was already proved by Clausen and Stötzer [ClSt, Satz 1.4]; the proof of proposition 2.5.1 above is similar to their proof.

By a construction based on these considerations we can show that in a certain sense there exists an abundance of pictures. This is not so if we fix domain and image diagrams beforehand, since there is no simple criterion for Pic(χ, ψ) to be non-empty, but if we fix only the domain, then pictures can be built up without obstruction. It will be convenient to have a notation for the squares directly above, below, left and right of a given square s; define x^{↑} = x − (1, 0), x^{↓} = x + (1, 0), x^{←} = x − (0, 1) and x^{→} = x + (0, 1).

2.5.3. Proposition. Let χ ∈ S be given, and a total ordering ‘≤_{χ}’ on χ such that x ≤_{↙} y with x, y ∈ χ implies x ≤_{χ} y; let f be a bijection from an order ideal χ′ of (χ, ≤_{χ}) to a skew diagram ψ′, such that f is a poset morphism (χ′, ≤_{↖}) → (ψ′, ≤_{↙}) and f^{−1} is a poset morphism (ψ′, ≤_{↖}) → (χ′, ≤_{χ}). Then there is at least one way to extend f to a picture χ → ψ for some ψ ∈ S; in case ψ′ ∈ P the extension can be made such that also ψ ∈ P.

2.6 Pictures and the Littlewood-Richardson rule

Proof. We reason by induction on |χ\χ′|. The case χ′ = χ is taken care of by corollary 2.5.2, so it suffices to show that if χ′ ≠ χ, then we can extend χ′ by the square x ∈ χ \ χ′ that is minimal for ‘≤_{χ}’, and define f(x) such that the stated conditions remain valid. Let p = x^{←}, r = x^{↓}, and q = p^{↓} = r^{←}. As indicated above, the conditions for f(x) are that it is an outer cocorner of ψ′, and that f(p) <_{↙} f(x) if p ∈ χ′ and f(x) <_{↙} f(r) if r ∈ χ′. For any y ∈ χ′ we have one of y ≤_{↖} p, y ≤_{↙} q or r ≤_{↖} y, where y ≤_{↖} p and r ≤_{↖} y respectively imply p ∈ χ′ and r ∈ χ′; moreover if p, r ∈ χ′ then also q ∈ χ′, and f(p) <_{↙} f(q) <_{↙} f(r). It follows that if p ∈ χ′ then f(p)^{→} ∉ ψ′, and if r ∈ χ′ then f(r)^{↓} ∉ ψ′, and if both hold, then f(p)^{→} ≤_{↙} f(r)^{↓}. It is now easy to see that in all cases there exists an outer cocorner of ψ′ that satisfies all conditions for f(x); if ψ′ is a Young diagram, it can be chosen inside N × N, so that the image remains a Young diagram.

2.6. Pictures and the Littlewood-Richardson rule. We can rephrase the procedures given above for characterising and generating pictures in terms of row and column encodings of pictures. For simplicity we first consider the case where the image is a Young diagram. Then the row or column encoding alone determines the picture: the length of row i (column i) of the image diagram equals the number of times i occurs as entry of the row (column) encoding. Defining the weight of (part of) a diagram filled with natural numbers as the sequence (a_{0}, a_{1}, …), where a_{i} is the number of times i occurs as entry, the weight of the row or column encoding must therefore be a partition (i.e., weakly decreasing). Since the image of any order ideal of (χ, ≤_{χ}) is also a Young diagram, the weight of the restriction of the row or column encoding to the order ideal must also be a partition. We can now characterise row and column encodings of pictures with a Young diagram as image.

2.6.1. Proposition. Let E be a skew diagram χ filled with natural numbers, and let ‘≤_{χ}’ be a total ordering on χ such that x ≤_{↙} y with x, y ∈ χ implies x ≤_{χ} y. Then E is the column encoding (respectively row encoding) of a picture f: χ → λ with λ ∈ P if and only if the following conditions are satisfied:

(i) the entries of E are strictly increasing (respectively weakly decreasing) along each row, (ii) the entries of E are weakly increasing (respectively strictly decreasing) along each column, (iii) the weight of the restriction of E to any order ideal of (χ, ≤_{χ}) is a partition. If so, f is uniquely determined, and λ^{t} (respectively λ) is the Young diagram of the weight of E. Furthermore, any partial filling defined on an order ideal of (χ, ≤_{χ}) that satisfies the given conditions for the defined entries can be extended to a complete filling satisfying the conditions.

Proof. It is clear that the conditions are necessary. To reconstruct a picture from its column or row encoding, the missing coordinate of the image of a square x should be taken to be the number of squares y <_{↙} x in χ with the same entry as x. With this rule, the sufficiency of the conditions follows from corollary 2.5.2, taking ‘≤_{c}’ (respectively ‘≤_{r}’) for ≤_{ψ}. From the proof of proposition 2.5.3 it follows that applying this rule to a partial filling defined on an order ideal χ′ of (χ, ≤_{χ}) will result in a poset morphism (χ′, ≤_{↖}) → (λ′, ≤_{↙}); the extendibility of such a filling then follows from proposition 2.5.3. The remaining statements are obvious. Remark. Condition (iii) is equivalent to the requirement that reading the entries of E in the increasing order for ‘≤_{χ}’ one obtains a lattice permutation, i.e., the weight of any initial subsequence is a partition.

We shall omit an detailed statement and proof of the generalisation of this proposition for pictures whose image not a Young diagram. If the image of a picture f is λ \ μ, then giving μ in addition to the row or column encoding of f suffices to determine f; the only change in the conditions for this case is that in (iii) not the weights themselves are required to be partitions, but rather the result of adding μ to the weights.

The fillings described in proposition 2.6.1 are just Littlewood-Richardson fillings. More precisely, in the traditional formulation of the Littlewood-Richardson rule (see for instance [Macd, I.9]), the allowed fillings are precisely the transposes of the fillings allowed by proposition 2.6.1 for column encodings, using ‘≤_{c}’ for ‘≤_{χ}’. The Littlewood-Richardson rule describes the structure coefficients of the ring of symmetric functions on its Z-basis of S-functions { s_{λ} | λ ∈ P }; we refer to [Macd] for precise definitions. This rule can now be restated in terms of pictures, as follows.

2.6.2. Theorem. [Littlewood & Richardson] For λ, μ ∈ P one has s_{μ}s_{ν} = ∑_{λ∈P} c_{μ,ν}^{λ}s_{λ}, where c_{μ,ν}^{λ} = |Pic(λ \ μ, ν)|.

Although pictures λ \ μ → ν correspond to Littlewood-Richardson fillings for c_{μ^{t},ν^{t}}^{λ^{t}}, that number equals c_{μ,ν}^{λ} since s_{λ} ↦ s_{λ^{t}} induces an automorphism of the ring of symmetric functions. This symmetry is not (yet) obvious for pictures, but proposition 2.6.1 does allow substantial variation in concrete formulations of the Littlewood-Richardson rule, all of which are equivalent, since they just describe the same set of pictures in different ways: various orderings can be used for ‘≤_{χ}’ (such as ‘≤_{r}’ or ‘≤_{c}’), one may use row or column encoding, and symmetries of pictures may be applied, such as f ↦ f^{−1}, which leads to filling the Young diagram ν instead of the skew diagram λ \ μ.

Endowing the ring of symmetric functions with the inner product for which the set of S-functions forms an orthonormal basis, we have c_{μ,ν}^{λ} = ⟨s_{λ}, s_{μ}s_{ν}⟩. For λ, μ ∈ P with μ ⊆ λ the skew S-function s_{λ\μ} is defined by ⟨s_{λ\μ}, s_{ν}⟩ = c_{μ,ν}^{λ}; this is well defined by the Littlewood-Richardson rule, and is invariant under translations of the skew diagram λ \ μ. The product has a direct interpretation in the form of diagonal concatenation of skew diagrams: for χ, ψ ∈ S we have s_{χ}s_{ψ} = s_{χ⊎ψ} where χ ⊎ ψ is a skew diagram (defined up to translation) built from χ and ψ as follows

χ ⊎ ψ: \begin{aligned}& ψ \\ χ \end{aligned}

(see [Macd, I (5.7)]). From this it follows that c_{μ,ν}^{λ} = c_{ρ,λ}^{π} where π, ρ ∈ P are such that μ ⊎ ν = π \ ρ. The corresponding identity |Pic(λ \ μ, ν)| = |Pic(λ, μ ⊎ ν)| can be understood directly. To see that, we first state, and prove combinatorially, an obvious consequence of the Littlewood-Richardson rule, that will also be of use in the sequel.

2.6.3. Proposition. For λ, μ ∈ P the set Pic(λ, μ) is empty unless λ = μ, in which case it has one element.

Proof. Consider a picture f: λ → μ, then the first column of λ is an order ideal of (λ, ≤_{↙}), so its image must be a Young diagram contained in μ; not having more that one square in any row, the image must be contained in the first column of μ. But since we may argue similarly for the inverse image of that column, it can only be that f maps the first column of λ onto that of μ. We can then split off the first columns, and by induction find that each column of λ is mapped onto the corresponding column of μ, so λ = μ and f is uniquely determined.

The unique element of Pic(λ, λ) will be denoted by 1_{λ}. We are now ready to demonstrate the identity mentioned above, and in fact a slightly more general one.

2.6.4. Proposition. For any λ, μ ∈ P with μ ⊆ λ and ψ ∈ S, the set Pic(λ \ μ, ψ) is in bijection with Pic(λ, μ ⊎ ψ).

Proof. Let a picture f: λ → μ ⊎ ψ be given. Since μ is an order ideal of (μ ⊎ ψ, ≤_{↙}), its inverse image is a Young diagram μ′ contained in λ; the restriction of f to μ′ is again a picture, whence μ′ = μ and the restriction is equal to 1_{μ}. The restriction of f to the complementary skew diagram λ \ μ is also a picture, and it is this picture that will correspond to f under the bijection of the proposition. One easily checks that conversely the extension of any picture λ \ μ → ψ by 1_{μ} is a picture λ → μ ⊎ ψ.

The Littlewood-Richardson rule states that |Pic(χ, ν)| = ⟨s_{χ}, s_{ν}⟩ for all χ ∈ S and ν ∈ P. This suggests that the same might be true more generally, with ν replaced by an arbitrary skew diagram ψ. This is indeed the case, and can already be deduced from the facts presented do far.

2.6.5. Proposition. [Zelevinsky] For all χ, ψ ∈ S one has |Pic(χ, ψ)| = ⟨s_{χ}, s_{ψ}⟩.

Proof. It will suffice to prove this for χ = λ \ μ with λ, μ ∈ P and μ ⊆ λ. Then by proposition 2.6.4 we have |Pic(λ \ μ, ψ)| = |Pic(λ, μ ⊎ ψ)|, which by the Littlewood-Richardson rule is equal to ⟨s_{λ}, s_{μ⊎ψ}⟩ = ⟨s_{λ}, s_{μ}s_{ψ}⟩ = ⟨s_{λ\μ}, s_{ψ}⟩, where the final equality follows by linearity from ⟨s_{λ}, s_{μ}s_{ν}⟩ = ⟨s_{λ\μ}, s_{ν}⟩ for ν ∈ P, since (by the Littlewood-Richardson rule) s_{ψ} can be written as a linear combination of such s_{ν}.

This fact was originally stated by Zelevinsky [Zel1, Theorem 2], and proved by constructing a bijection, the Robinson-Schensted correspondence for pictures that we shall describe below. As we have indicated, the enumerative identity can already be derived without using that construction.

3 The Robinson-Schensted correspondence

§3. The Robinson-Schensted correspondence.

3.1. The Robinson-Schensted algorithm applied to pictures. Since { s_{λ} | λ ∈ P } is an orthonormal basis of the ring of symmetric functions, proposition 2.6.5 is equivalent to |Pic(χ, ψ)| = ∑_{λ∈P}|Pic(λ, χ)| · |Pic(λ, ψ)|. The Robinson-Schensted correspondence for pictures is a bijection corresponding to this identity.

3.1.1. Theorem. [Zelevinsky] For all χ, ψ ∈ S there is a bijection Pic(χ, ψ) →^{∼} ∐_{λ∈P} Pic(λ, ψ) × Pic(λ, χ).

The bijection is obtained by using the (ordinary) Robinson-Schensted algorithm. In one formulation of that algorithm, it defines a bijective correspondence between the set of bijections f: A → B of two totally ordered sets of n elements, and pairs (P, Q) of poset morphisms P: λ → B and Q: λ → A for some λ ∈ P. Here f corresponds to a permutation of n and P and Q to Young tableaux of shape λ, but it is natural to take the elements of B as entries for P, since P is formed by inserting the images of f into an initially empty tableau using the Schensted insertion procedure; similarly it is natural to take the elements of A as the entries of Q. Applying the algorithm to any bijection χ → ψ, where χ and ψ are totally ordered by ‘≤_{c}’, one obtains a pair of bijections λ → ψ and λ → χ for some λ ∈ P. (As before we have transposed everything with respect to [Zel1]; there the transpose Robinson-Schensted algorithm is used.) The essential point of the theorem is that the bijection χ → ψ is a picture if and only if the same is true for the bijections λ → ψ and λ → χ computed from it. We omit a proof of this theorem, since we shall prove a stronger statement below.

While the enumerative substratum of this theorem follows from the Littlewood-Richardson rule, a converse implication is practically and historically much more relevant. Using the theorem we can deduce the Littlewood-Richardson rule from a special instance of the identity |Pic(χ, ψ)| = ⟨s_{χ}, s_{ψ}⟩, namely where ψ is a horizontal strip ψ_{μ} for μ ∈ P, defined by ψ_{μ} = μ_{0} ⊎ μ_{1} ⊎ ⋯, where μ_{i} is (a copy of) row i of μ. The function s_{ψ_{μ}} is the product h_{μ} of the complete symmetric functions h_{μ_{i}} associated to the parts of μ; the elements of Pic(χ, ψ_{μ}) correspond under negated row encoding to semistandard tableaux of shape χ and weight μ, and for this case the identity can be established directly (see [Macd, I (5.14)]). Using this fact and theorem 3.1.1, we can prove theorem 2.6.2: Proof of the Littlewood-Richardson rule. We have ⟨s_{χ}, h_{μ}⟩ = |Pic(χ, ψ_{μ})| = ∑_{λ∈P}|Pic(λ, χ)|·|Pic(λ, ψ_{μ})| = ∑_{λ∈P}|Pic(λ, χ)|⟨s_{λ}, h_{μ}⟩, which, since the functions h_{μ} are known to be a Z-basis of the ring of symmetric functions, implies that s_{χ} = ∑_{λ∈P}|Pic(λ, χ)|s_{λ}, and therefore ⟨s_{λ}, s_{χ}⟩ = |Pic(λ, χ)|. Remark. We have followed the proof of [Macd, I (9.2)], but its crucial claim (9.4) was deduced from theorem 3.1.1; this reduces the 5-page proof to the few lines above. Since [Macd] predates the introduction of pictures, its proof uses a different language than ours, but it is easy to interpret the objects manipulated as pictures. Note that Macdonald’s proof is a reconstruction and completion of the incomplete proof in [Rob] (which was reproduced in [Litt]), where the Robinson-Schensted correspondence was first defined. It appears that the main aspect in which Robinson’s proof was incomplete, is that it fails to prove the preservation of the properties that correspond, in their disguised form, to the picture conditions. So one might say that the correspondence that Robinson should have defined is not the one that has become known as the (ordinary) Robinson-Schensted correspondence, but rather Zelevinsky’s generalised version! (This is not quite fair, since the pictures for which one needs the correspondence in the proof are not completely general ones, but still the point is remarkable.)

3.2. Independence of choice of total orderings. In [FoGr] it was shown that in the construction of the bijection of theorem 3.1.1 one may replace the ordering ‘≤_{c}’, used to make χ and ψ into totally ordered sets, by other total orderings compatible with ‘≤_{↙}’ (this is called choosing ‘readings’ of χ and ψ), and still obtain the same bijection. This resembles what we have seen for the various ways to characterise pictures, so we shall say that the correspondence of theorem 3.1.1 is a natural one (this terminology was introduced in [FoGr]). Nonetheless, this property is quite a non-trivial addition to theorem 3.1.1, since changing the orderings on χ and ψ can have a significant effect on the permutation that corresponds to the picture, causing the insertion process to proceed quite differently.

3.3 Insertion and extraction using ‘≤_{↙}’

We shall now formulate a stronger version of theorem 3.1.1, that makes both the naturality and the relation with the ordinary Robinson-Schensted correspondence explicit; we first need some definitions. For n ∈ N let [n] be the n-element set { i ∈ N | i < n }, and identify the symmetric group S_{n} with the set of bijections [n] → [n]. For λ ∈ P let T_{λ} be the set of bijective poset morphisms (λ, ≤_{↖}) → ([n], ≤); these are the Young tableaux of shape λ. Put P_{n} = { λ ∈ P | |λ| = n }, and let RS_{n}: S_{n} → ∑_{λ∈P_{n}} T_{λ} × T_{λ} denote the ordinary Robinson-Schensted correspondence (using row-insertion), see for instance [Sche], [Knu2], [vLee3]. It will be convenient to represent a total ordering ‘≤_{χ}’ on a skew diagram χ by the unique poset isomorphism α: (χ, ≤_{χ}) → ([n], ≤) (this is essentially a reading of [FoGr]); compatibility of ‘≤_{χ}’ with ‘≤_{↙}’ is expressed by the fact that α is also a poset morphism (χ, ≤_{↙}) → ([n], ≤).

3.2.1. Theorem. [Fomin & Greene] There is a bijection RS_{χ,ψ}: Pic(χ, ψ) → ∐_{λ∈P_{n}} Pic(λ, ψ) × Pic(χ, λ) for any χ, ψ ∈ S, such that if n = |χ| = |ψ| and RS_{χ,ψ}(f) = (p, q), then for any pair of bijective poset morphisms α: (χ, ≤_{↙}) → ([n], ≤) and β: (ψ, ≤_{↙}) → ([n], ≤) one has RS_{n}(β ∘ f ∘ α^{−1}) = (β ∘ p, α ∘ q^{−1}).

With respect to theorem 3.1.1 we have inverted the second picture (q), so that χ always occurs as domain, just as ψ always occurs as image; this does not affect the meaning of the theorem, but will make it match nicer with glissements, that will be discussed later.

The proof of the naturality statement given in [FoGr] is quite technical. It shows that one can transform the reading α into a standard reading of χ (corresponding to ‘≤_{c}’) by small steps, such that the corresponding changes to the permutation β ∘ f ∘ α^{−1} are ‘right Knuth transformations’ (a subset of the elementary transformations of permutations given in [Knu1]), and that for each such step correspondence between pictures is unchanged. The author independently obtained the naturality result, using the simpler and more direct proof presented below. We show that Schensted insertion and extraction procedures for pictures can be described directly in terms of the ordering ‘≤_{↙}’ on ψ, without using the reading β at all, and that they preserve the picture conditions; thus the correspondence defined is automatically independent of β. Like in [FoGr] it suffices to prove naturality on one side, since for the other side it follows by the well known symmetry property of RS_{n}.

3.3. Insertion and extraction using ‘≤_{↙}’. Before we can construct RS_{χ,ψ} and prove the theorem, we need some simpler results. For λ ∈ P and k ∈ N, let λ_{(k)} = ({k} × N) ∩ λ denote the row k of λ, and put λ_{(>k)} = λ_{(≥k+1)} = ⋃_{i>k} λ_{(i)} and λ_{(<k)} = λ \ λ_{(≥k)}.

3.3.1. Lemma. Let λ ∈ P, ψ ∈ S, p ∈ Pic(λ, ψ), and let s be an outer cocorner of ψ. Then ‘≤_{↙}’ induces a total ordering on p(λ_{(0)}) ∪ {s}. If moreover s is not the maximum of this totally ordered set, then its successor min_{≤_{↙}} { y ∈ p(λ_{(0)}) | s <_{↙} y } is an outer cocorner of p(λ_{(>0)}).

Proof. Note first that λ_{(0)} is an order coideal of (λ, ≤_{↙}), so that its image p(λ_{(0)}) is an order coideal of (ψ, ≤_{↖}), which is moreover (being the image of a row) totally ordered by ‘≤_{↙}’, and in fact a horizontal strip. If s were incomparable with respect to ‘≤_{↙}’ to any square x ∈ p(λ_{(0)}), then x would lie strictly to the left and above s, so that x^{↓} ∈ ψ, and since p(λ_{(0)}) is an order coideal, x^{↓} ∈ p(λ_{(0)}); this would contradict the fact that p(λ_{(0)}) is a horizontal strip. If s has a successor, say t, within the set p(λ_{(0)}) ∪ {s}, as mentioned in the lemma, then t can only lie in a row above that of s, and therefore must be the leftmost element of its row within p(λ_{(0)}). But then t is a minimal element of the order coideal p(λ_{(0)}) of (ψ, ≤_{↖}), and therefore an outer cocorner of its complementary order ideal p(λ_{(>0)}).

We now come to the Schensted insertion and extraction procedures for pictures.

3.3.2. Lemma. There is a pair of mutually inverse procedures that transform into each other the following sets of data: on one side a pair (p, s) with p ∈ Pic(λ, ψ) for some λ ∈ P and ψ ∈ S, and with s an outer cocorner of ψ; on the other side a pair (x, p′) with p′ ∈ Pic(λ′, ψ′) for some λ′ ∈ P and ψ′ ∈ S and with x an outer corner of λ′. The correspondence is such that ψ′ = ψ ∪ {s} and λ = λ′ \ {x}. Moreover, for any injective poset morphism β: (ψ′, ≤_{↙}) → (N, ≤) the Young tableau β ∘ p′ is the result of inserting the number β(s) into β ∘ p by the ordinary Schensted row-insertion procedure.

For any choice of β, the final requirement completely determines the effect of the procedures; indeed for β corresponding to the ordering ‘≤_{c}’, the constructions will exactly match those of [Zel1]. Nevertheless we need to describe the procedures explicitly, in order to show that this can be done without referring to β. Our proof then will consist of two elements: the description of the procedures, and the proof that they preserve the picture conditions. Since in the latter part independence of β is not important, we could have confined ourselves to referring for it to the proof in [Zel1]. Thanks to proposition 2.5.1 however, our proof is much simpler and more concise than that proof, which is actually contained in an appendix of [Zel2], and is given only for the insertion procedure.

Proof. Let a pair (p, s) as in the lemma be given. We construct a sequence x_{0}, …, x_{r} for some r ∈ N, with x_{i} ∈ λ for i < r and x_{r} an outer cocorner of λ (which will in fact be the square x of the lemma), and a corresponding sequence s_{0}, …, s_{r} with s_{0} = s and s_{i} = p(x_{i−1}) ∈ ψ for i > 0. We shall have moreover that each s_{i} is an outer cocorner of p(λ_{(≥i)}). The terms of the sequences are determined successively; assume the we have constructed all x_{i} for i < k, and consequently all s_{i} for i ≤ k, and that s_{k} is an outer cocorner of p(λ_{(≥k)}). Then by restricting to λ_{(≥k)} and applying lemma 3.3.1 we find that p(λ_{(k)}) ∪ {s_{k}} is totally ordered by ‘≤_{↙}’. Put x_{k} = (k, j_{k}), where j_{k} = |{ x ∈ λ_{(k)} | p(x) <_{↙} s_{k} }|; either x_{k} is the leftmost square x of λ_{(k)} for which s_{k} <_{↙} p(x), or, if there are no such squares, it is the first square in row k beyond the right end of λ_{(k)}. In the latter case we put r = k and x = x_{r}, and the construction is complete; otherwise we have by lemma 3.3.1 that s_{k+1} = p(x_{k}) is an outer cocorner of p(λ_{(>k)}), and we may proceed to the next step of the construction. When the construction is complete we put λ′ = λ ∪ {x}, and define p′: λ′ → {s} ∪ ψ by p′(x_{i}) = s_{i} for 0 ≤ i ≤ r and p′(y) = p(y) for y ∈ λ \ {x_{0}, …, x_{r−1}}. For any β it is clear that if we replace the squares of ψ′ by their images under β, then the construction reduces to ordinary Schensted insertion.

For the inverse procedure we trace our steps backwards. Let (p′, x) as in the lemma be given, and let x occur in row r. We start by setting x_{r} = x and s_{r} = p′(x_{r}); since x_{r} is maximal in (λ′_{(≥r)}, ≤_{↙}), its image s_{r} is an inner cocorner of the order coideal p′(λ′_{(<r)}) of (ψ′, ≤_{↖}). Then x_{r−1}, …, x_{0} and s_{r−1}, …, s_{0} are defined as follows, meanwhile showing that each s_{i} is an inner cocorner of p′(λ′_{(<i)}). Assuming this for i = k + 1, we have analogously to lemma 3.3.1 that {s_{k+1}} ∪ p′(λ′_{(k)}) is totally ordered by ‘≤_{↙}’; moreover s_{k+1} is not its minimum, as p′(x_{k+1}^{↑}) <_{↙} p′(x_{k+1}) = s_{k+1}. Put x_{k} = (k, j_{k}), where j_{k} = |{ x ∈ λ′_{(k)} | p′(x) <_{↙} s_{k+1} }| − 1, and s_{k} = p′(x_{k}); then s_{k} is the predecessor of s_{k+1} in {s_{k+1}} ∪ p′(λ′_{(k)}) with respect to ‘≤_{↙}’, which lies at the end of its row within p′(λ′_{(k)}), and therefore is an inner cocorner of p′(λ′_{(<k)}). At the end we put s = s_{0}, λ = λ′ \ {x}, ψ = ψ′ \ {s}, and define p: λ → ψ by p(x_{i}) = s_{i+1} and p(y) = p′(y) for y ∈ λ \ {x_{0}, …, x_{r−1}}. Like before, if for any β we replace the squares of ψ′ by their images under β, then the construction reduces to ordinary Schensted extraction; in particular, the two procedures are each others inverses, provided that we can show that they preserve the picture conditions.

To prove that the result of an insertion or extraction is again a picture, we use proposition 2.5.1. For any choice of β, the fact that β ∘ p and β ∘ p′ are Young tableaux obtained from each other by ordinary Schensted insertion and extraction implies that condition 2.5.1(i) is satisfied in both cases, and also that x_{r} <_{↙} ⋯ <_{↙} x_{0}. Now consider the case of insertion; suppose that condition 2.5.1(ii) is not satisfied for p′, i.e., there are squares y, z ∈ λ′ with p′(y) <_{↖} p′(z) and z <_{↙} y. Since we know that p is a picture, one easily sees that this can only occur if z ∈ {x_{0}, …, x_{r}}, say z = x_{k}, and y ∉ {x_{0}, …, x_{r}}. Then p′(z) = s_{k} is an outer cocorner of p(λ_{(≥k)}), so that p(λ_{(≥k)}) ∪ {s_{k}} = p′(λ′_{(≥k)}) is an order ideal of (ψ′, ≤_{↖}); since p′(y) <_{↖} p′(z) this order ideal also contains p′(y), and so y ∈ λ_{(≥k)}. Now z <_{↙} y implies y ∈ λ_{(k)}, so that k < r, and p(y) lies in a column to the right of p(z) = s_{k+1}; this contradicts p′(y) <_{↖} s_{k} <_{↙} s_{k+1}. In the case of extraction, a violation p(y) <_{↖} p(z) ∧ z <_{↙} y of condition 2.5.1(ii) can only occur if y = x_{k} and z ∉ {x_{0}, …, x_{r−1}} Then p(z) lies in the the order coideal {s_{k+1}} ∪ p′(λ′_{(<k+1)}) = p(λ_{(<k+1)}) ∪ {s} of (ψ′, ≤_{↖}), whence z ∈ λ′_{(k)}, leading to a contradiction with p′(y) = s_{k} <_{↙} s_{k+1} = p(y) <_{↖} p(z) = p′(z).

Let us give an example to illustrate the procedures. If we apply the insertion procedure, taking for p the picture displayed on the left below, and for s the outer cocorner of its image marked d, then the result will be that p′ is the picture displayed on the right, and x is the square in its domain marked m.

a b c g k ; e f i j ; h m ; l ; n \underrightarrow{p} n ; l m ; h i j k ; e f g ; a b d c  a b c d k ; e f g j ; h i ; l m ; n \underrightarrow{p′} n ; l m ; h i j k ; e f g ; a b c d

This result was obtained by the following steps; for convenience we use \overline{x} for the square marked x at the image side of the display of p, and similarly \underline{x} for the square marked x at the domain side of p, which is p^{−1}(\overline{x}). We start with putting s_{0} = \overline{d}, and comparing it with p(λ_{(0)}), which together form the chain \overline{a} <_{↙} \overline{b} <_{↙} \overline{c} <_{↙} \overline{d} <_{↙} \overline{g} <_{↙} \overline{k}. So s_{1} = \overline{g}, the successor of \overline{d}, and x_{0} = \underline{g}. Then s_{1} is compared with p(λ_{(1)}), giving \overline{e} <_{↙} \overline{f} <_{↙} \overline{g} <_{↙} \overline{i} <_{↙} \overline{j}, so x_{1} = \underline{i} and s_{2} = \overline{i}. Similarly from \overline{h} <_{↙} \overline{i} <_{↙} \overline{m} we get x_{2} = \underline{m} and s_{3} = \overline{m}, and since \overline{l} <_{↙} \overline{m} the procedure then stops with x_{3} = x = \underline{l}^{→}. Setting p′(x_{i}) = s_{i} for i = 0, 1, 2, 3, we get for p′ the picture displayed on the right.

3.4 Naturality of the full Robinson-Schensted correspondence

3.4. Naturality of the full Robinson-Schensted correspondence. Proof of theorem 3.2.1. We shall now define the generalised Robinson-Schensted correspondence RS_{χ,ψ} of theorem 3.2.1. We do so by defining RS_{χ,ψ}^{α} for any chosen bijective poset morphism α: (χ, ≤_{↙}) → ([n], ≤) such that it satisfies the requirements of the theorem for this α and all β, and then prove that RS_{χ,ψ}^{α} is independent of α. The construction is a direct translation of the ordinary Robinson-Schensted algorithm, using the procedures of lemma 3.3.2 for insertion and extraction. So let χ, ψ and n be as in the theorem, and let f: χ → ψ be a bijection such that α ∘ f^{−1} is a skew tableau, i.e., a poset morphism (ψ, ≤_{↖}) → ([n], ≤) (eventually we shall restrict f to being a picture). For i = 0, 1, …, n we successively compute pictures p_{i}: λ^{(i)} → ψ^{(i)}, and at the same time define individual images of a map q: χ → N × N; here λ^{(i)} are Young diagrams, and ψ^{(i)} = f(α^{−1}([i])), which is an order ideal of (ψ, ≤_{↖}) since [i] is an order ideal of ([n], ≤)). Start with p_{0}: ∅ → ∅, and after p_{i} is determined, apply the insertion procedure of lemma 3.3.2 to (p_{i}, f(α^{−1}(i))), resulting in a pair (x, p′); set λ^{(i+1)} = λ^{(i)} ∪ {x}, p_{i+1} = p′, and q(α^{−1}(i)) = x. When p_{n} is eventually determined, put λ = λ^{(n)}, and RS_{χ,ψ}^{α}(f) = (p_{n}, q), where q the now completely defined bijection χ → λ, for which α ∘ q^{−1} ∈ T_{λ}. Reversing the steps, and using the extraction procedure of lemma 3.3.2, define an inverse algorithm RS_{χ,ψ}^{α}^{−1}, that can be applied to any pair (p, q) of a picture p: λ → ψ and a bijection q: χ → λ with α ∘ q^{−1} ∈ T_{λ}, for some λ ∈ P, and that yields a bijection f: χ → ψ for which α ∘ f^{−1} is a skew tableau.

By construction we have if RS_{χ,ψ}^{α}(f) = (p, q) that RS_{n}(β ∘ f ∘ α^{−1}) = (β ∘ p, α ∘ q^{−1}) for all β; clearly p and q are independent of β. On the other hand by the well known fact that RS_{n}(w) = (P, Q) implies RS_{n}(w^{−1}) = (Q, P), we have RS_{n}(α ∘ f^{−1} ∘ β^{−1}) = (α ∘ q^{−1}, β ∘ p). If we now assume that f is a picture, then RS_{ψ,χ}^{β}(f^{−1}) = (q^{−1}, p^{−1}), implying that q^{−1} (and hence q) is a picture, and also that p and q are independent of α. Conversely, if q instead of f is assumed to be picture, then from RS_{ψ,χ}^{β}^{−1}(q^{−1}, p^{−1}) = f^{−1} it follows that β ∘ f is a skew tableau; together with the original assumption that α ∘ f^{−1} is a skew tableau, this implies by proposition 2.5.1 that f is a picture. This completes the proof of theorem 3.2.1. Remark. The subscripts χ, ψ attached to the operator RS and its inverse are used only to distinguish it from RS_{n}, and to serve as a reminder of the domain and image of the picture involved; in applications of these operators these subscripts may be suppressed, although we shall not do so.

As an illustration of the algorithm, we shall apply it to the picture that we have seen before:

\begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} → e c ; f g b ; d ; a .

We choose α: χ → [7] corresponding to ‘≤_{r}’, for which the squares of χ in increasing order carry the labels f, g, d, e, a, b, c (the only other legitimate choice would be to interchange e and a). We show here the final steps of the algorithm (the first few steps are less illustrative): the pictures p_{4}, …, p_{7} are successively

d g e ; f → e ; f g ; d ,  a g e ; d ; f → e ; f g ; d ; a ,  a g b ; d e ; f → e ; f g b ; d ; a ,  a g b c ; d e ; f → e c ; f g b ; d ; a .

The other picture computed is

q = \begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} → f g e c ; d b ; a  where the corresponding Young tableau α ∘ q^{−1} is  0 1 3 6 2 5 4

displaying the order in which the images were determined. If we had used the other choice for α, and hence the insertion order f, g, d, a, e, b, c, the intermediate picture p_{4} would be different (and we would have λ^{(4)} = (2, 1, 1) instead of λ^{(4)} = (3, 1)); the entries 3 and 4 would be interchanged in α∘q^{−1}, but the picture q would be unchanged. Note that the point-image pairs of q are determined one by one, but the intermediate

4 The Schützenberger correspondence

partial maps are not always pictures: after p_{5} is computed the pairs of q labelled a, d, e, f, g are determined, but the corresponding subset of the domain χ is not a skew diagram.

An interesting special case of this construction is when χ and ψ are horizontal strips, i.e., the picture f corresponds to a generalised permutation of [Knu1]. Then there is only one possible choice for the morphisms α and β, so that the precise steps taken by the algorithm are completely determined. Instead of using β and α to make p and q into standard Young tableaux, one can also represent them as semistandard tableaux by using negated row encoding; the insertion and extraction procedures used for p, and the definition of the other picture q^{−1}, then become identical to those in [Knu1]. The dual correspondence described there, which operates on zero-one matrices instead of generalised permutations, can also be obtained as a special case, by taking for χ a vertical strip and for ψ a horizontal strip, and using column encoding for p so that it is a transposed semistandard tableau (or “dual tableau” in the terminology of [Knu1]), while for q one keeps negated row encoding. Therefore, the Robinson-Schensted algorithm for pictures can in fact be seen as a common generalisation of both variants of of Knuth’s generalised Robinson-Schensted algorithm.

Unlike the ordinary Robinson-Schensted algorithm, the Robinson-Schensted algorithm for pictures can be applied to each of the components of the pair it returns. Such iteration does not produce any interesting new pictures, however.

3.4.1. Proposition. For p ∈ Pic(λ, ψ) and q ∈ Pic(χ, λ) with λ ∈ P and χ, ψ ∈ S, one has

RS_{λ,ψ}(p) = (p, 1_{λ})  (1)
RS_{χ,λ}(q) = (1_{λ}, q)  (2)

Proof. The first case can be verified directly from the definition of RS_{λ,ψ}^{α}, with (for simplicity) α corresponding to ‘≤_{c}’ or ‘≤_{r}’; each insertion step only involves moves in a single column of λ. The verification essentially comes down to the well known fact that for any Young tableau P, if we apply the ordinary Robinson-Schensted algorithm to the permutation obtained by reading the entries in increasing order for ‘≤_{c}’ or ‘≤_{r}’, then the left tableau obtained will be P itself; indeed, we see that this is true for any order compatible with ‘≤_{↙}’. The second case follows by symmetry.

§4. The Schützenberger correspondence.

4.1. The Robinson-Schensted correspondence in relation to symmetries. As was mentioned before, the set Pic(χ, ψ) is in bijection with each of Pic(−χ, −ψ), Pic(χ^{t}, −ψ^{t}), and Pic(−χ^{t}, ψ^{t}), by composing a picture with the indicated reflections in domain and image; we shall denote the counterparts of a picture f so obtained by −f, f^{t}, and −f^{t} (so we indicate the symmetry applied to the domain, rather than that applied to the image). An obvious question is what happens to the pair of pictures computed by the Robinson-Schensted algorithm when we apply these symmetries to f; the answer must be non-trivial, since the class of pictures allowed for p and q is not fixed by these symmetries.

The answer will involve the Schützenberger correspondence, an algorithmically defined shape preserving transformation of Young tableaux; we shall denote it by S_{n}: T_{n} → T_{n}, where n ∈ N and T_{n} = ⋃_{λ∈P_{n}} T_{λ}. It was first defined in [Schü1] (where it is called I); see also [Knu2] (the operation P ↦ P^{S}) and [vLee3]. It has a definition and some properties of a type similar to those of the Robinson-Schensted algorithm, and there is a strong connection between the correspondences defined by the two algorithms, that we shall now formulate. Let ñ ∈ S_{n} be the unique permutation that is an anti-isomorphism of ([n], ≤) to itself, i.e., ñ: i ↦ n − 1 − i.

4.1.1. Theorem. [Knuth] For σ ∈ S_{n} and P, Q ∈ T_{n}, the following statements are equivalent:

\begin{aligned}RS_{n}(σ) & = (P, Q) \\ RS_{n}(σ ∘ ñ) & = (P^{t}, S_{n}(Q)^{t}) \\ RS_{n}(ñ ∘ σ) & = (S_{n}(P)^{t}, Q^{t}) \\ RS_{n}(ñ ∘ σ ∘ ñ) & = (S_{n}(P), S_{n}(Q)) \end{aligned}

In its full form the theorem first appears in [Knu2, Theorem D] (see also [Schü2, 4.3], and [vLee3, theorem 4.1.1]); important partial results already appear in [Sche] and [Schü1]. We also have the identities S_{n}(P^{t}) = S_{n}(P)^{t} and S_{n}(S_{n}(P)) = P, that are in fact implied by this theorem.

4.2 The Schützenberger correspondence for pictures

Viewing permutations as special cases of pictures, this theorem precisely describes the effects of the symmetries mentioned above on the tableaux associated to permutations under the Robinson-Schensted correspondence: if f is a picture corresponding of a permutation σ ∈ S_{n}, then f^{t} corresponds to σ ∘ ñ (the reverse of σ), −f^{t} to ñ ∘ σ (σ with ñ applied to its entries), and −f to ñ ∘ σ ∘ ñ.

4.2. The Schützenberger correspondence for pictures. These statements can be generalised to arbitrary pictures, using the Schützenberger correspondence for pictures that is described in [Zel1]; it is based on the corresponding algorithm for tableaux in much the same way as the Robinson-Schensted correspondence for pictures is. We shall call this operation S_{ψ} for ψ ∈ S; it bijectively maps Pic(λ, ψ) to Pic(λ, −ψ) for all λ ∈ P_{|ψ|}. The negation of the image diagram is quite natural in view of the definition of S_{n} and theorem 4.1.1 (in fact it would have some advantages to also define S_{n} such that the entries of S_{n}(P) are the negatives of those of P, as is done in [vLee3]). Like before, we first define an operation S_{ψ}^{β} using a bijective poset morphism β: (ψ, ≤_{↙}) → ([n], ≤), and then show that it sends pictures to pictures and the outcome does not depend on β. For β corresponding to ‘≤_{c}’, the definition will match the one in [Zel1]. We shall need poset morphisms from skew diagrams to [n] corresponding to β, but defined on ψ^{t}, −ψ, and −ψ^{t}; these will be called β^{t}, −β and −β^{t} respectively, and are defined by β^{t}(s) = ñ(β(s^{t})), −β(s) = ñ(β(−s)), and −β^{t}(s) = β(−s^{t}) (the composition with ñ in the first two cases is needed to to obtain a morphism). We define S_{ψ}^{β} by S_{ψ}^{β}(p) = (−β)^{−1} ∘ S_{n}(β ∘ p) so that (−β) ∘ S_{ψ}^{β}(p) = S_{n}(β ∘ p); in other words, S_{ψ}^{β} is defined in such a way that under composition with β and −β to transform pictures into tableaux, it reduces to the ordinary Schützenberger correspondence.

4.2.1. Theorem. There is a bijection S_{ψ}: ∐_{λ∈P} Pic(λ, ψ) → ∐_{λ∈P} Pic(λ, −ψ) for any ψ ∈ S, such that if n = |ψ| then for any bijective poset morphism β: (ψ, ≤_{↙}) → ([n], ≤) one has (−β) ∘ S_{ψ}(p) = S_{n}(β ∘ p) for all p ∈ Pic(λ, ψ), λ ∈ P. Moreover, if S′_{χ}: ∐_{λ∈P} Pic(χ, λ) → ∐_{λ∈P} Pic(−χ, λ) is correspondingly defined by S′_{χ}(q) = S_{χ}(q^{−1})^{−1}, then the following statements are equivalent:

RS_{χ,ψ}(f) = (p, q),  (3)
RS_{χ^{t},−ψ^{t}}(f^{t}) = (p^{t}, S′_{−χ^{t}}(−q^{t})),  (4)
RS_{−χ^{t},ψ^{t}}(−f^{t}) = (S_{−ψ^{t}}(p^{t}), −q^{t}),  (5)
RS_{−χ,−ψ}(−f) = (S_{ψ}(p), S′_{χ}(q)).  (6)

Furthermore, S_{−ψ^{t}}(p^{t}) = S_{ψ}(p)^{t} and S_{−ψ}(S_{ψ}(p)) = p for all p ∈ Pic(λ, ψ).

This theorem follows in a straightforward way from theorems 3.2.1 and 4.1.1. Nevertheless the naturality statement and the incorporation of equations (4) and (5) appear to be new; the equivalence of (3) and (6) is stated in [Zel1, proposition 9]. Proof. Let f ∈ Pic(χ, ψ) and RS_{χ,ψ}(f) = (p, q). Choose morphisms α, β as in theorem 3.2.1, and put σ = β ∘ f ∘ α^{−1} ∈ S_{n}, then ñ ∘ σ ∘ ñ = (−β) ∘ (−f) ∘ (−α)^{−1}. Applying RS_{n} to this permutation, we get by theorem 4.1.1 that RS_{n}((−β) ∘ (−f) ∘ (−α)) = (S_{n}(β ∘ p), S_{n}(α ∘ q^{−1})) = ((−β) ∘ S_{ψ}^{β}(p), (−α) ∘ S_{χ}^{α}(q^{−1})). It then follows from theorem 3.2.1 that we must have RS_{−χ,−ψ}(−f) = (S_{ψ}^{β}(p), S_{χ}^{α}(q^{−1})^{−1}); therefore, this is a pair of pictures that does not depend on α or β, which establishes the initial statements about S_{ψ} and the equivalence of (3) and (6). The other equivalences follow by reasoning similarly for the permutations (−β^{t}) ∘ f^{t} ∘ (α^{t})^{−1} and (β^{t}) ∘ (−f^{t}) ∘ (−α^{t})^{−1}. The remaining claims can be proved similarly, but also follow from the stated equivalences.

Note that the naturality is essential in obtaining the equivalence of (3) with (4) or (5): if we would only use operations of type S_{ψ}^{β} with β corresponding to ‘≤_{c}’, then it would for instance not be possible to relate S_{−ψ^{t}}(p^{t}) to S_{n}((−β^{t}) ∘ p^{t}), since −β^{t} is not of the indicated type.

4.3. Transposing domain and image simultaneously. The Robinson-Schensted and Schützenberger correspondences for pictures, in combination with the symmetries of pictures, provide several equivalent ways to define the bijection between Pic(χ, ψ) and Pic(χ^{t}, ψ^{t}) that was announced earlier.

4.3 Transposing domain and image simultaneously

4.3.1. Theorem. There exists a bijective map f ↦ f^{T} from Pic(χ, ψ) to Pic(χ^{t}, ψ^{t}) for any χ, ψ ∈ S with the following properties. For a picture f: χ → ψ with RS_{χ,ψ}(f) = (p, q), one has

RS_{χ^{t},ψ^{t}}(f^{T}) = (S_{−ψ^{t}}(p^{t}), S′_{−χ^{t}}(−q^{t})),  (7)
RS_{χ,−ψ}((f^{T})^{t}) = (S_{ψ}(p), q),  (8)
RS_{−χ,ψ}(−(f^{T})^{t}) = (p, S′_{χ}(q)),  (9)
RS_{−χ^{t},−ψ^{t}}(−(f^{T})) = (p^{t}, −q^{t}).  (10)

For λ ∈ P and any p ∈ Pic(λ, ψ), q ∈ Pic(χ, λ) one has moreover

p^{T} = S_{−ψ^{t}}(p^{t})  and  q^{T} = S′_{−χ^{t}}(−q^{t}),  (11)

so that (7) can be restated as

RS_{χ^{t},ψ^{t}}(f^{T}) = (p^{T} , q^{T}).  (12)

Finally one has f^{T T} = f, and further commutation relations

(f^{−1})^{T} = (f^{T})^{−1}, (−f)^{T} = −(f^{T}), (f^{t})^{T} = (f^{T})^{t}, and S_{ψ}(p)^{T} = S_{ψ^{t}}(p^{T}), S′_{χ}(q)^{T} = S′_{χ^{t}}(q^{T}).

Proof. Each of the equations (7)–(10) determines a unique value for f^{T}, and by theorem 4.2.1 these are all equal. Applying (7) with p or q for f, and using proposition 3.4.1 one obtains (11). The remaining identities follow by direct computation, using the identities already established.

If the domain or image of a picture f is a Young diagram, then (11) shows that f^{T} can be computed without using the Robinson-Schensted algorithm. Such pictures correspond to Littlewood-Richardson fillings, and for those a corresponding operation has been described elsewhere, see for instance [HaSu]. On the other hand (10) shows that f^{T} can always be computed without using the Schützenberger algorithm, so (11) also implies that S_{ψ} can be expressed in terms of RS_{χ,ψ}; with 1′_{λ} denoting the unique picture −λ → λ, we have

S_{ψ}(p) = −RS_{−λ,ψ}^{−1}(p, 1′_{λ}),  (13)

and by interchanging p and S_{ψ}(p) this implies that S_{ψ}(p) is also the first component of RS_{−λ,−ψ}(−p).

As an illustration of the relation between f and f^{T} for general pictures, we consider again the picture for which we demonstrated the Robinson-Schensted algorithm. We had

f = \begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} → e c ; f g b ; d ; a , p = a g b c ; d e ; f → e c ; f g b ; d ; a , q = \begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} → f g e c ; d b ; a ;

using (11) and (12) we get

p^{T} = c b a ; e d ; g ; f → f d a ; g ; e b ; c , q^{T} = f ; a d g ; b e ; c → c e g ; b d ; a ; f , f^{T} = t ; u v w ; x y ; z → z y w ; x ; u v ; t .

Note that in computing p^{T} and q^{T} by the Schützenberger algorithm we have chosen the identifying labels to match those of p and q on the image respectively on the domain. For f^{T} however the correspondence with the individual point-image pairs of f could not be maintained in any meaningful way, so we switched to a different set of labels.

4.4 Lack of naturality of the deflation procedure

4.4. Lack of naturality of the deflation procedure. So far we have used theorem 4.1.1 rather than the definition of S_{n}(P), but it is interesting to see whether the computation of S_{ψ}(p) can be described directly in terms of pictures, as was the case for RS_{χ,ψ}(f). The computation of S_{n}(P) consists of a repeated application of a “deflation” procedure Δ to P, which removes an entry, and rearranges the remaining entries into a smaller Young tableau; the tableau S_{n}(P) records the sequence of shapes of P, Δ(P), Δ^{2}(P), …, Δ^{n}(P). For ψ ∈ S and a bijective poset morphism β: (ψ, ≤_{↙}) → ([n], ≤), one can define an operation Δ_{β} such that for maps p: λ → ψ for which β ∘p is a Young tableau one has β ∘ Δ_{β}(p) = Δ(β ∘ p); then the tableau (−β) ∘ S_{ψ}^{β}(p) = S_{n}(β ∘ p) will record the sequence of shapes of p, Δ_{β}(p), Δ_{β}^{2}(p), …, Δ_{β}^{n}(p). Since S_{ψ}^{β} does not depend on β one might think that the same is true for Δ_{β}. However, this is not the case: the very fact that S_{n}(β ∘ p) = (−β) ∘ S_{ψ}(p) shows that S_{n}(β ∘ p) varies with β, so the sequence of shapes Δ_{β}^{i}(p) must vary as well.

So unlike the Schensted insertion and extraction procedures, Δ cannot be defined naturally for pictures. In fact, Δ_{β} does not even preserve the picture conditions. An application of Δ starts with removing the entry at the origin, creating an empty square, and then as long as possible slides entries leftwards or upwards into the empty square; whenever two entries could move into the empty square, the smaller one takes precedence, to keep the rows and columns increasing. In the computation of Δ_{β}(p), this comparison takes place between entries of β ∘ p. If the p-images of the squares in question are comparable by ‘≤_{↙}’ then this will determine the comparison in β ∘p, independently of β. If they are incomparable however, then β breaks the tie, and the entries compared will end up either in the same row or column; but this means that the picture condition is destroyed, since for a picture the images of squares in one row or column must be comparable by ‘≤_{↙}’. Since repeated application of Δ removes the entries from the tableau in increasing order, a comparison between any pair of entries is established at some point during the process, so that unless ψ is totally ordered by ‘≤_{↙}’, some Δ_{β}^{i}(p) will not be a picture. In fact the picture conditions will be violated in another way as well: the image shapes of Δ_{β}^{i}(p) will not all be skew diagrams.

Let us give a concrete example. Consider the following picture:

p: \begin{matrix}a & b & c \\ d & e \\ f & g \end{matrix} → \begin{matrix}f & g & c \\ d & e \\ a & b \end{matrix} ,  for which  S_{ψ}(p) = \begin{matrix}c & g & f \\ e & d \\ b & a \end{matrix} → \begin{aligned}& b & a \\ & e & d \\ c & g & f \end{aligned} .

For convenience we let each of a, …, g denote the square in the image of p with that label; this allows us to view the picture as a Young tableau filled with symbols instead of numbers. A choice of β defines an ordering of the symbols; although there are several possibilities we will restrict ourselves to those for which a < d < b < e, f < g < c. Depending on whether or not e < f we get the following two sequences for Δ_{β}^{i}(p).

\begin{matrix}e < f: \\ f < e: \end{matrix}  \begin{matrix}a & b & c \\ d & e \\ f & g \end{matrix} ; \begin{matrix}a & b & c \\ d & e \\ f & g \end{matrix}  d b c ; e g ; f ; d b c ; f e ; g  b g c ; e ; f ; b e c ; f ; g  e g c ; f ; f e c ; g  f g c ; e c ; g  g c ; g c  c ; c

We see that although a difference is introduced at the first step, the shapes remain the same until the first of {e, f} is removed, and the tableaux become equal again after both are removed. This remarkable fact is no coincidence, since the naturality of S_{ψ} implies that the square that is freed in the step that an entry x is removed, is the one that maps to −x under S_{ψ}(p), which is independent of the ordering used.

An extreme case is p = 1_{λ} where λ is a rectangular diagram: then every Young tableau P of shape λ can be written as P = β ∘ p for some β, and any chain of diagrams can occur as shapes of Δ_{β}^{i}(p); in this case each two of β, P, and S_{n}(P) are linked by a simple transformation. A related fact is that for p ∈ Pic(λ, ψ) with λ rectangular, S_{ψ}(p) equals −p, up to a translation of the domain; this follows from (13) and (1), but also from the general way that the Schützenberger correspondence can be expressed in terms of glissement, a construction that we shall consider next.

5 Glissement

§5. Glissement. In the previous two sections the Robinson-Schensted and Schützenberger correspondences were considered as they are defined by their deterministic algorithms. Schützenberger has shown in [Schü2] that these correspondences can also be defined by a rewrite system for skew tableaux, where the basic rewrite step is called glissement. We shall now develop a similar theory for pictures; the constructions and results of §3 and §4 are not used, but they do provide motivation.

5.1. Definition of domain-glissements and image-glissements of pictures. Let us recall from [Schü2] how a glissement of a skew tableau φ is formed. An inner cocorner of the shape of φ is appointed as initial position of an “empty square”, then (as in the deflation procedure) entries are repeatedly slid leftwards or upwards into the empty square, the smaller entry taking precedence if there are two possibilities. When no more moves are possible, the new positions of the entries define a new skew tableau φ′, that we shall call the inward glissement of φ into s. Given the final position s′ of the empty square (an outer cocorner of the shape of φ′) the moves can be traced back in a similar fashion, recovering φ; we call φ an outward glissement of φ′ into s′.

In order to define a similar operation for a picture f: χ → ψ, one may take a bijective poset morphism β: (ψ, ≤_{↙}) → ([n], ≤) and call f′ an inward glissement of f if β ∘ f′ is an inward glissement of β ∘ f. It is however by no means obvious that such f′ will be a picture. A necessary condition for this is that the images under f′ of any pair of squares in the same row or column are comparable by ‘≤_{↙}’. In particular any pair s, t ∈ ψ for which the entries β(s) and β(t) of β ∘ f were compared in forming the glissement must be comparable by ‘≤_{↙}’. But then the resulting picture f′ will not depend on β; in other words, the definition can only work if it is natural. This turns out to be the case, which is surprising in view of the negative results about the deflation procedure.

5.1.1. Theorem. Let f: χ → ψ be a picture, and s an inner (respectively outer) cocorner of χ. There exists a unique picture f′: χ′ → ψ such that for any bijective poset morphism β: (ψ, ≤_{↙}) → ([n], ≤) the skew tableau β ∘ f′ is the inward (respectively outward) glissement of β ∘ f into s.

The picture f′ will be called the inward (respectively outward) domain-glissement of f into s. Another form of glissement can be derived by the symmetry f ↔ f^{−1}: we shall call (f′)^{−1} the inward (outward) image-glissement of f^{−1} into s. Here is an example of these operations: the left picture is an inward domainglissement of the middle one, and the right picture is an outward image-glissement of the middle one.

a b c ; d g e ; f → e c ; f g b ; d ; a  ⟵^{DG}  \begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} → e c ; f g b ; d ; a  ⟶^{IG}  \begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} → e c ; g b ; f d ; a

The comparisons made are \overline{d} <_{↙} \overline{f} and \overline{g} <_{↙} \overline{e} for the domain-glissement and \underline{g} <_{↙} \underline{d} for the imageglissement, where overlines (underlines) indicate labelled squares in the image (domain) of the middle picture.

Replacing a picture by a glissement of into a square constitutes one rewrite step. More generally, we shall call f′ a glissement of f if there is a sequence of pictures f = f_{0}, f_{1}, …, f_{l} = f′ where each f_{i+1} is a (domain or image) glissement of f_{i} into some square; if in addition any of the qualifications ‘domain’, ‘image’, ‘inward’, or ‘outward’ is used, then that qualification must apply to all these glissements into a square.

To prove theorem 5.1.1, we only need to consider the inward case, by the symmetry f ↔ −f. We start with showing the naturality; like for the Schensted insertion procedure, the results of all comparisons made are independent of β.

5.1.2. Lemma. Let f and β be as in theorem 5.1.1. If, during the computation of the inward glissement of β ∘ f into s, the entries β(f(x)) and β(f(y)) of two squares x, y ∈ χ are compared with each other, then f(x) and f(y) are comparable by ‘≤_{↙}’.

5.2 Results adapted from the theory of ordinary glissements

Proof. Assume the contrary, and let (i, j) be the first square (i.e., minimal for ‘≤_{↖}’) for which the entries of squares x = (i + 1, j) and y = (i, j + 1) of χ are being compared, but f(x) and f(y) are incomparable for ‘≤_{↙}’. Then f(x) lies above and to the left of f(y), i.e., f(x) = (k, l) and f(y) = (k′, l′) with k < k′ and l < l′. Let z be the square (k′, l) which lies in the column of f(x) and the row of f(y); we have f(x) <_{↖} z <_{↖} f(y) and hence z ∈ ψ. Since f is a picture we have x <_{↙} f^{−1}(z) <_{↙} y and f^{−1}(z) ≠ (i + 1, j + 1), so necessarily f^{−1}(z) = (i, j) = x^{↑} = y^{←}. This excludes the possibility that the entries of x and y are compared at the first step of computing the glissement, so this comparison takes place after the entry β(z) was moved out of the square (i, j), leaving it empty. By possibly replacing f by f^{t} we may assume that the move of β(z) was a horizontal one into (i, j − 1). Then at that move, β(z) was compared against the entry β(f(a)) of the square a = (i + 1, j − 1) = x^{←}, and apparently found to be smaller. Since this comparison was made before that of the entries of x and y we must in fact have z <_{↙} f(a). But this contradicts the fact that f(a) lies to the left of the column of f(x), thus proving the lemma.

The reasoning can be illustrated as follows; \overline{x} abbreviates f(x), and \underline{z} abbreviates f^{−1}(z).

\begin{matrix}←\underline{z} & y \\ a & x \end{matrix}  ⟶  \overline{x} ; z  \overline{y}

Proof of theorem 5.1.1. By the lemma, a bijection f′ is constructed independently of β; it suffices to show that it is a picture. We shall establish the conditions of proposition 2.5.1; condition (i) will hold because β ∘ f′ is a skew tableau for some (indeed any) β. Assume we have a pair x′, y′ ∈ χ′ that violates condition 2.5.1(ii) for f′, i.e., for which f′(x′) <_{↖} f′(y′) while y′ <_{↙} x′. Now consider the squares x, y ∈ χ for which f(x) = f′(x′) and f(y) = f′(y′); since f is a picture and f(x) <_{↖} f(y) we have x <_{↙} y. But from the definition of glissement x and x′ can be at most one place apart, and similarly for y and y′; the only ways that we can have x <_{↙} y and y′ <_{↙} x′ is when x = y^{←} while x′ = y^{′↑}, or y = x^{↑} and y′ = x^{′←}. The two cases are illustrated below, with arrows pointing from x to x′ and from y to y′.

a ; ^{^{↑} x←y}  ←y ; ^{a ^{↑}x}

In the former case the image of x must have been compared against that of the square a = y^{↑}, and by the lemma we must have f(x) <_{↙} f(a), but this is in contradiction with the fact that f(x) <_{↖} f(y) and f(a) lies below the row of f(y). In the latter case the image of y has similarly been found to be less than that of the square a = x^{←}, but f(x) <_{↖} f(y) <_{↙} f(a) contradicts the fact that f(a) lies in a column to the left of f(x). Note. Since glissement of pictures deals with a modification of bijections, we have to be a bit more careful than usual about the meaning of our (informal) language. If a skew tableau φ′ is the glissement of another tableau φ, saying that the entry φ(s) is moved in forming the glissement has a clear meaning, despite the fact that φ(s) really is an immutable number: it means that the square s′ with φ′(s′) = φ(s) differs from s (strictly speaking we should say that the original of φ(s) is changed in the glissement). We shall similarly say that in passing from a picture f: χ → ψ to a domain-glissement f′, the image f(s) of s ∈ χ moves, if f(s) = f′(s′) for some s′ ≠ s; of course f(s) ∈ ψ itself remains the same square. For reasons of symmetry we shall also say that a square s ∈ χ moves in forming an image-glissement f′′ of f, if f(s) ≠ f′′(s) (it may help to think of f as represented by ψ, with each square “filled” with its inverse image). This terminology should not obscure the fact that we are dealing with bijections, and that individual point-image pairs have no separate identity (as might be suggested by our practice of assigning labels to such pairs in illustrations): given just two pictures f, f′, there is no unique way to view certain point-image pairs of f′ as copies of particular such pairs of f that have been “moved around”.

The following obvious consequence of the theorem is singled out because of its usefulness.

5.1.3. Corollary. If the computation of a domain-glissement of f involves successive moves of images f(s) and f(t), one of which is a horizontal move and the other a vertical one, then f(s) and f(t) are incomparable by ‘≤_{↖}’; in particular they do not lie in the same row or column.

5.2. Results adapted from the theory of ordinary glissements. The direct relationship expressed by theorem 5.1.1 between glissements of pictures and of skew tableaux allows results derived in [Schü2] for skew tableaux to be applied to pictures; in fact they can be applied separately for domain-glissement and image-glissement, which means that the theory of glissements of pictures has an even richer structure than that of ordinary glissements. In this subsection we collect the most fundamental properties, restating them for pictures; in most cases we do so for domain-glissements only, but of course similar statements hold for image-glissements as well. These properties make clear how well the facts obtained for the Robinson-Schensted and Schützenberger correspondences for pictures fit in with the theory of glissements. Although reference to the theory of ordinary glissements is the most convenient way to obtain these results for pictures, we shall see that in most cases there are proofs for the picture case that are simpler than those for tableaux. References to statements in [vLee3] have been included because the proofs there differ from those of equivalent statements in [Schü2].

5.2.1. Proposition. For any picture f and i, j ∈ N, the picture obtained from f by a translation of its domain over (i, j) is an outward domain-glissement of f.

Proof. The sequence of glissements is easily constructed; see [vLee3, §5] for a proof in the tableau case.

The following theorem is the most fundamental one of the theory: it states that for pictures whose domain is contained in N × N, inward domain-glissements form a rewrite system with unique normal forms.

5.2.2. Theorem. [Schützenberger] For each picture f: χ → ψ there is a unique picture p: λ → ψ with λ ∈ P that is a domain-glissement of f.

Proof. This follows, using theorem 5.1.1, from [Schü2, 3.3], or from [vLee3, theorem 5.4].

The next two theorems connect glissement with the Robinson-Schensted and Schützenberger correspondences.

5.2.3. Theorem. [Schützenberger] For any picture f: χ → ψ and let p be the unique domain-glissement of f whose domain is a Young diagram, and let q similarly be the unique image-glissement of f whose image is a Young diagram, then (p, q) = RS_{χ,ψ}(f) (in particular the Young diagrams are the same in both cases).

Proof. Using theorems 3.2.1 and 5.1.1, the statement about p follows from the proof of [Schü2, 4.1] (where it is shown that the Young tableau of [Schü2, 3.3] can be found by a computation equivalent to the Schensted insertion procedure), or from [vLee3, proposition 5.5]. The statement about q follows from this using RS_{ψ,χ}(f^{−1}) = (q^{−1}, p^{−1}).

Note that proposition 3.4.1 follows from this theorem. The theorem also implies that if f: χ → ψ and f′: χ′ → ψ′ are pictures, with RS_{χ,ψ}(f) = (p, q) and RS_{χ′,ψ′}(f′) = (p′, q′), then f′ is a domain-glissement of f if and only if p = p′ and f′ is an image-glissement of f if and only if q = q′. As an example, for

f = \begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} → e c ; f g b ; d ; a , where p = a g b c ; d e ; f → e c ; f g b ; d ; a , q = \begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} → f g e c ; d b ; a

satisfy RS_{χ,ψ}(f) = (p, q), p and q can be obtained by glissement (we show only the part that changes):

\begin{aligned}& a & b & c \\ & d & e \\ f & g \end{aligned} ▷ a b c ; d g e ; f ▷ a g b c ; d e ; f  and  e c ; f g b ; d ; a ▷ e g c ; f b ; d ; a ▷ f e g c ; d b ; a .

5.2.4. Theorem. [Schützenberger] For any picture p: λ → ψ with λ ∈ P, the picture S_{ψ}(p) is the unique domain-glissement of −p whose domain is a Young diagram.

Proof. This follows, using theorem 5.1.1, from [Schü2] (where following 3.6 the Schützenberger algorithm is presented as a method for computing the Young tableau φ^{J} that corresponds to the picture described in our theorem) or from [vLee3, proposition 5.6]. Alternatively it follows from (13) and theorem 5.2.3.

For instance, for the picture p of the example above, we may compute from

−p = f ; e d ; c b g a → a ; d ; b g f ; c e  that  S_{ψ}(p) = c e g f ; b d ; a → a ; d ; b g f ; c e

5.3 Commutation of domain-glissement and image-glissement

by a sequence of glissements

f ; e d ; c b g a ▷ f ; e g d ; c b a ▷ \begin{aligned}& & g & f \\ & e & d \\ c & b & a \end{aligned} ▷ \begin{aligned}& e & g & f \\ & b & d \\ c & a \end{aligned} ▷ e g f ; c b d ; a ▷ c e g f ; b d ; a .

We see that glissements provide a way to compute the Robinson-Schensted and Schützenberger correspondences without choosing any total ordering compatible with ‘≤_{↙}’; they also make theorem 4.2.1 obvious.

5.2.5. Theorem. Let λ, μ, ν ∈ P with μ, ν ⊆ λ and |μ| + |ν| = |λ|. For any picture p: ν → ψ, the number of pictures f: λ \ μ → ψ for which p is a domain-glissement of f, is equal to the Littlewood-Richardson coefficient c_{μ,ν}^{λ}.

The corresponding statement for tableaux, with instead of p a Young tableau P of shape ν, is given in [Schü2, (3.7)] (stating the independence of the choice of P) together with [Schü2, (4.7)] (equating the number with c_{μ,ν}^{λ} for a particular P). This result can be transferred to the picture case: if f: λ \ μ → ψ is a bijection for which β ∘ f is a skew tableau of which the Young tableau β ∘ p is a glissement, then by theorem 5.1.1, f is a picture and p is a domain-glissement of f; the converse is obvious. However, for the picture case there is in fact a much simpler proof. Proof. By theorem 5.2.3, the map q ↦ RS_{λ\μ,ψ}^{−1}(p, q) defines a bijection from Pic(λ \ μ, ν) to the indicated set of pictures f.

5.3. Commutation of domain-glissement and image-glissement. A natural question to ask is whether domain-glissement and image-glissement commute. It turns out that they do, but for reasons that are far from trivial. In fact, from a technical point of view this is our most significant new result. It does not appear to follow easily from any of the facts accumulated above; instead, we shall give a direct proof based directly on the definition of glissements of pictures.

5.3.1. Theorem. The operations of domain-glissement and image-glissement commute, in the following sense. Let f: χ → ψ be a picture u and v cocorners of χ and ψ respectively, and let f′ be the domainglissement into u of f and f′′ the image-glissement into v of f. Then the domain-glissement into u of f′′ equals the image-glissement into v of f′.

As an illustration consider the example in 5.1, where a one-step domain-glissement and image-glissement of the same picture were computed. If to each of the results we apply the glissement at the other side, we obtain

a b c ; d g e ; f → e c ; f b ; d g ; a  respectively  a b c ; f d e ; g → e c ; g b ; f d ; a .

These in fact represent the same picture, although the labels are permuted. Proof. The most obvious way in which the glissements can commute is when the sequence of squares whose entries move in forming the domain-glissement of f is the same as for the domain-glissement of f′′, and similarly for the image-glissements of f and f′ (then performing the glissements on labelled pictures, as in our examples, one gets the same result without a permutation of the labels). When this is not the case, then for at least one comparison performed to compute a glissement, the ordering with respect to ‘≤_{↙}’ of the images of the squares involved is interchanged by the glissement at the other side. By replacing f by f^{−1} if necessary, we may assume that one of the comparisons for the domain-glissement is affected by the image-glissement, and moreover, by replacing f by f^{t}, −f^{t}, or −f if necessary, that both glissements are inward. Let p, q ∈ χ be squares whose images are compared in the computation of both domain-glissements, and whose images are interchanged by the image-glissement: f(p) <_{↙} f(q) and f′′(q) <_{↙} f′′(p). Since a single glissement does not move images by more than one square, both p and q must have moved in the image-glissement, their images switching from horizontally adjacent to vertically adjacent or vice versa. The set { x ∈ χ | f(x) ≠ f′′(x) } forms a chain in χ for ‘≤_{↙}’, so there is at most one such pair (p, q).

We have either f(p)^{→} = f(q) and p^{↑} = q^{←}, or f(p)^{↑} = f(q) and q^{↑} = p^{←}; we shall now show however that the latter does not occur.

5.3.2. Lemma. The following cannot occur in the situation of theorem 5.3.1: there are p, q ∈ χ such that q^{↑} = p^{←} occurs as position of the empty square in the computation of the inward domain-glissement f′ of f, and f(p)^{↑} = f(q) while f′′(q) = f(q)^{←}.

Proof. Suppose the situation does occur, and choose a leftmost occurrence of p (and q). Since f′′(q) lies in the skew diagram {v} ∪ ψ, convexity dictates that f′′(q)^{↓} = f(p)^{←} ∈ ψ, say f′′(q)^{↓} = f(r) for some r ∈ χ. We have q <_{↙} r <_{↙} p and r ≠ q^{→}, so r = q^{↑} = p^{←}. Then the image f(r) moves in the computation of f′, which move is followed by a horizontal move of f(p) (since f(p) <_{↙} f(q)); therefore by corollary 5.1.3, the move of f(r) was also a horizontal one. Hence putting s = q^{←} we have s ∈ χ and f(r) <_{↙} f(s) <_{↙} f(q), and therefore f(s) = f(r)^{↑} = f′′(q). Now s is moved in the computation of f′′, followed by a horizontal move of q; by corollary 5.1.3, we see that f′′(s) = f(s)^{←}. But then we have the situation of the lemma for (r, s) in place of (p, q), contradicting the choice of p.

\begin{aligned}& r & p \\ s & q \end{aligned}  \underrightarrow{f}  \begin{matrix}\overline{s} & \overline{q} \\ \overline{r} & \overline{p} \end{matrix}

Continuing the proof of theorem 5.3.1, we must now have p^{↑} = q^{←}, and f(p) = f(q)^{←} = f′′(q) = f′′(p)^{↓}. This case cannot be dismissed, as can be seen from the example above, or from the unique f with χ = ψ = . More generally, for any rectangular λ ∈ P, the unique picture f with χ = ψ = λ \ {(0, 0)}, and p = (1, 0), q = (0, 1) provides an example; in this case the first glissement (whether in domain or image) involves moves along the left and bottom edges of the rectangle, while the second glissement involves moves along the top and right edges, showing that there can be an arbitrarily large divergence of the paths of the glissements. In these particular cases the commutation of the glissements follows trivially from proposition 2.6.3. Although in the general case this argument cannot be used, we shall show that essentially we always have one of these configurations, possibly embedded into a larger picture. Consequently, the remainder of the proof has the nature of a “strait jacket proof”: one has at the outset a precise model of the situation at hand (and the conclusion holds there); all effort is directed towards eliminating any possibility of a variation from this model. The lack of surprising new facts often makes such proofs a bit technical and uninspiring; our proof is no exception.

After possibly applying a translation to the domain of f we may assume that p = (1, 0) and q = (0, 1). Since f(p) <_{↙} f(q), the image f(p) moves upwards in computing f′, i.e., f′(p^{↑}) = f(p). Now let k ≥ 1 be the length of the sequence of consecutive upward moves starting with this move of f(p), i.e., the largest value such that (i, 0) ∈ χ and f′((i, 0)^{↑}) = f(i, 0) for 1 ≤ i ≤ k. For convenience put p_{i} = (i, 0) and q_{i} = (i, 1) for i = 0, …, k, so p = p_{1} and q = q_{0}. By convexity of {v} ∪ ψ we have f′′(p)^{→} = f(q)^{↑} ∈ ψ; this square is f(x) for some x ∈ χ with p <_{↙} x <_{↙} q, which can only be x = q_{1}; we have f′′(q_{1}) = f(q_{1}). We shall now prove successively for i = 2, …, k that f′′(p_{i}) = f(p_{i})^{↑}, that q_{i} ∈ χ and that f(q_{i}) = f′′(q_{i}) = f′′(p_{i})^{→}. These facts have been established for i = 1, assume by induction that they hold for i − 1. Since i ≤ k we have f′(p_{i}^{↑}) = f(p_{i}), so we must have f(p_{i−1}) <_{↙} f(p_{i}) <_{↙} f(q_{i−1}); this leaves f(p_{i}) = f(p_{i−1})^{↑} = f′′(p_{i−1}) as only possibility. Therefore p_{i} moves in the computation of f′′, followed by an upward move of p_{i−1}; by corollary 5.1.3, the move of p_{i} is upwards as well: f′′(p_{i}) = f(p_{i})^{↑}. By convexity f′′(p_{i})^{→} = f(q_{i−1})^{↑} ∈ ψ, which can only be the image of q_{i}, so q_{i} ∈ χ and f(q_{i}) = f′′(q_{i}) = f′′(p_{i})^{→}, completing the induction. By assumption p_{k} is the last square of the sequence whose image moves upwards in the computation of f′, and q_{k} ∈ χ, so f(q_{k}) is moved leftwards into p_{k}, i.e., f′(p_{k}) = f(q_{k}).

We illustrate the parts of f and f′′ determined so far. Note that variables are not labels, but denote the square that contains them; the image of a square under f respectively f′′ is denoted by an overline.

q ; p q_{1} ; p_{2} q_{2} ; p_{k} q_{k}  \underrightarrow{f}  \overline{q_{k}} ; \overline{p_{k}} ; \overline{q_{2}} ; \overline{p_{2}} \overline{q_{1}} ; \overline{p} \overline{q}  q ; p q_{1} ; p_{2} q_{2} ; p_{k} q_{k}  \underrightarrow{f′′}  \overline{p_{k}} \overline{q_{k}} ; \overline{p_{2}} \overline{q_{2}} ; \overline{p} \overline{q_{1}} ; \overline{q}

Let f′′′ be the domain-glissement into u of f′′; since f′′(q) <_{↙} f′′(p), the image f′′(q) moves left in the computation of f′′′. Let l ≥ 1 be the length of the sequence of consecutive leftward moves starting with this move in that computation, i.e., the largest value such that (0, i) ∈ χ and f′′′((0, i)^{←}) = f′′(0, i) for 1 ≤ i ≤ l. Put r_{i} = (0, i) and s_{i} = (1, i) for i = 0, …, l, so p = s_{0}, q = r_{1}, and q_{1} = s_{1}. We shall prove for i = 2, …, l that f′′(r_{i}) = f(r_{i})^{←}, that s_{i} ∈ χ and f(s_{i}) = f′′(s_{i}) = f(r_{i})^{↑}. These facts are known for i = 1, assume that they hold for i − 1. Since i ≤ l we have f′′′(r\overleftarrow{i}) = f′′(r_{i}), so f′′(r_{i−1}) <_{↙} f′′(r_{i}) <_{↙} f′′(s_{i−1}), and consequently f′′(r_{i}) = f′′(r_{i−1})^{→} = f′′(s_{i−1})^{↓} = f(r_{i−1}). Therefore, the leftward move of r_{i−1} in the computation of f′′ is followed by a move of r_{i}; by corollary 5.1.3, that move is also leftward: f′′(r_{i}) = f(r_{i})^{←}. By convexity f(r_{i})^{↑} = f(s_{i−1})^{→} ∈ ψ; this can only be f(s_{i}), so s_{i} ∈ χ and f(s_{i}) = f′′(s_{i}) = f(r_{i})^{↑}, completing the induction step. In computing f′′′ the leftward move of f′′(r_{l}) is not followed by another leftward move, and s_{l} ∈ χ, so f(s_{l}) = f′′(s_{l}) is moved upwards: f′′′(r_{l}) = f(s_{l}). The information obtained so far can be summarised as follows.

\begin{aligned}& q & r_{2} & r_{3} & r_{l} \\ p & q_{1} & s_{2} & s_{3} & s_{l} \\ p_{2} & q_{2} \\ p_{k} & q_{k} \end{aligned}  \underrightarrow{f} \overline{q_{k}} ; \overline{p_{k}} ; \overline{q_{2}} ; \overline{p_{2}} \overline{q_{1}} \overline{s_{2}} \overline{s_{3}}  \overline{s_{l}} ; \overline{p} \overline{q} \overline{r_{2}} \overline{r_{3}}  \overline{r_{l}}  \begin{aligned}& q & r_{2} & r_{3} & r_{l} \\ p & q_{1} & s_{2} & s_{3} & s_{l} \\ p_{2} & q_{2} \\ p_{k} & q_{k} \end{aligned}  \underrightarrow{f′′}  \begin{matrix}\overline{p_{k}} & \overline{q_{k}} \\ \overline{p_{2}} & \overline{q_{2}} \\ \overline{p} & \overline{q_{1}} & \overline{s_{2}} & \overline{s_{3}} & & \overline{s_{l}} \\ \overline{q} & \overline{r_{2}} & \overline{r_{3}} & & \overline{r_{l}} \end{matrix}

We now proceed to show that the restriction f|_{A} to the most relevant part of the domain of f, namely to A = { p ∈ Z × Z | (0, 0) <_{↖} p ≤_{↖} (k, l) }, is completely determined. There is a unique picture 1_{A}: A → A, which is given explicitly by 1_{A}(i, 0) = (k + 1 − i, 0) for 1 ≤ i ≤ k and 1_{A}(i, j) = (k − i, j) for 0 ≤ i ≤ k and 1 ≤ j ≤ l. For simplicity we translate the image of f so that f(p_{k}) = (1, 0); we shall then prove that f|_{A} = 1_{A}, or equivalently f^{−1}|_{A} = 1_{A}. The images computed so far establish f^{−1}(y) = 1_{A}(y) for those y = (i, j) ∈ A with j ≤ 1 or i ≥ k − 1. For the remaining values y ∈ A the identity f^{−1}(y) = 1_{A}(y) follows once we know f^{−1}(y^{←}) = 1_{A}(y^{←}) and f^{−1}(y^{↓}) = 1_{A}(y^{↓}); then f^{−1}|_{A} = 1_{A} follows by an easy induction.

We shall indicate the remainder of the proof of theorem 5.3.1 by a somewhat less formal sketch. We show that inside A the moves for each of the glissements coincide with those for the corresponding inward glissements into the origin applied to 1_{A}; in particular the sequence of moves passes through the square (k, l) in each case. Then for points in χ \ A the moves for the domain-glissement are unaffected by the imageglissement, and vice versa for points in ψ \ A. Therefore the general case reduces to the special case f = 1_{A}, u = v = (0, 0), where the theorem holds by proposition 2.6.3.

So the final point to prove is that the sequences of moves for f|_{A} do not deviate from the corresponding sequences for 1_{A}. The only way in which they could do so is by leaving the region A prematurely rather than via the square (k, l). Now if we can show that the sequence changes from upward moves to leftward moves at the square (k, 0) (for the glissement applied first), respectively from leftward moves to upward moves at the square (0, l) (for the second glissement), then corollary 5.1.3 ensures that it goes straight on from there to the square (k, l). The change from upward to leftward moves at (k, 0) was shown explicitly both for the computation of f′ and of f′′, as was the change from leftward to upward moves in the computation of f′′′ as domain-glissement of f′′; it is however still conceivable that sequence of leftward moves in computing the image-glissement into v of f′ goes on beyond (0, l). But the configuration that we assumed to exist for f also occurs for f^{−1}, with (f(p_{k}), f(q_{k})) taking the place of (p, q); for that case f′ and f′′ are interchanged. From this we may conclude that the mentioned sequence of leftward moves for the image-glissement into v of f′ is eventually followed by an upward move, say into into (0, l′). Since f|_{A} = 1_{A}, we have l′ ≥ l, but by symmetry we then also get l ≥ l′; this completes the proof of theorem 5.3.1.

5.3.3. Corollary. Let a picture f: χ → ψ and an image-glissement f′ of f be given, and a cocorner u of χ. Then the domain-glissement of f′ into u is an image-glissement of the domain-glissement of f into u; in particular, these pictures have the same domain.

Proof. Apply theorem 5.3.1 along a sequence of one-step image-glissements between f and f′.

5.3.4. Corollary. Let pictures f, f′ be image-glissements of each other. Then for any sequence of onestep domain-glissements that can be applied to f, it is possible to apply domain-glissements to f′ into the same sequence of squares, and the resulting pictures have the same domain.

The conclusion of this corollary does not refer to image-glissements, and therefore describes a relation that is also meaningful for skew tableaux, with domain-glissements replaced by ordinary glissements. This

5.4 Basic theory of glissements revisited

relation is studied in [Haim] and called “dual equivalence”; the name indicates that the relation is dual to that of glissement. Let us extend this concept to pictures by calling pictures f, f′ dual equivalent if the conclusion of corollary 5.3.4 holds. Here the duality is realised by the symmetry f ↔ f^{−1}, since for pictures the relation of dual equivalence coincides with that of image-glissement:

5.3.5. Proposition. If pictures f, f′ are dual equivalent, then they are image-glissements of each other.

Proof. In the special case that the domains of f and f′ are both the same λ ∈ P, then this certainly holds, since all such pictures are image-glissements of 1_{λ}. But by definition dual equivalence is preserved under applying the same sequence of domain-glissements to both pictures, and so is the relation of imageglissement; thus the general case is reduced to this special case.

5.4. Basic theory of glissements revisited. In this subsection we use theorem 5.3.1 to independently prove the basic facts about glissements mentioned in 5.2, that were originally derived in [Schü2]; we state some new facts as well. Like in [Schü2], we view theorems 5.2.3 and 5.2.4 as definitions of RS_{χ,ψ} and S_{ψ} respectively, leaving the equivalence with the traditional definitions as a separate matter. The fundamental statements are theorem 5.2.2, and the bijectivity of the correspondence between f and (p, q) in theorem 5.2.3. We combine these into a single theorem.

5.4.1. Theorem. Let χ, ψ ∈ S with χ, ψ ⊆ N × N. For each picture f: χ → ψ, there are unique pictures p: λ → ψ and q: χ → λ′ with λ, λ′ ∈ P, such that p is an inward domain-glissement of f and q is an inward image-glissement of f; moreover one has λ = λ′. Conversely, for any λ ∈ P and pictures p: λ → ψ and q: χ → λ, there is a unique picture f: χ → ψ that is both an outward domain-glissement of p and an outward image-glissement of q.

We included the conditions χ, ψ ⊆ N×N only to stress that there is no need to mix inward and outward glissements in this case. If one prefers however, those conditions and the qualifications ‘inward’ and ‘outward’ may be dropped; with the same changes, the proof remains valid. Proof. First, let f be given. Choose sequences (which obviously exist) of one-step inward domainglissements transforming f into some p ∈ Pic(λ, ψ) and of one-step inward image-glissements transforming f into some q ∈ Pic(χ, λ′), with λ, λ′ ∈ P. Denote by g_{p} and g_{q} the sequences of squares into which these glissements take place, and by g_{p}^{−1} and g_{q}^{−1} sequences of squares where these one-step glissements end, in reverse order (so that f can be reconstructed from p by outward domain-glissements into the squares of g_{p}^{−1}, or from q by outward image-glissements into the squares of g_{q}^{−1}). By corollary 5.3.4, one may apply to q inward domain-glissements into the squares of g_{p}, resulting in a picture λ → λ′. By proposition 2.6.3 we must have λ = λ′, and the picture is 1_{λ}. We can reconstruct q from 1_{λ} by by outward domain-glissements into the squares of g_{p}^{−1}, which shows that q does not depend on g_{q}; similarly, p is independent of g_{p}. For the converse, let p: λ → ψ and q: χ → λ be given. Then the sequences g_{p} and g_{p}^{−1} can be found by transforming q into 1_{λ} by domain-glissements, and as mentioned, this allows f to be reconstructed from p.

Our proof of the second part may be contrasted with that of [Schü2, théorème 4.3], where the bijectivity of the Robinson-Schensted correspondence defined using glissements is established by showing its equivalence with the traditional definition.

5.4.2. Corollary. Let f: χ → ψ be a picture, and RS_{χ,ψ}(f) = (p, q). If f′ is the domain-glissement of f into a square u and q′ the domain-glissement of q into u, then RS_{χ′,ψ}(f′) = (p, q′); similarly, if f′′ is the image-glissement of f into v and p′ the image-glissement of p into v, then RS_{χ,ψ′}(f′′) = (p′, q).

Using theorems 5.2.3 and 5.2.4 as definitions of RS_{χ,ψ} and S_{ψ}, the fact that S_{ψ} does not alter the domain of a picture is not immediately obvious; however, if p ∈ Pic(λ, ψ), then S_{ψ}(p) is a domain-glissement λ′ → −ψ of −p with λ′ ∈ P, and by theorem 5.4.1 there is also an image-glissement −λ → λ′ of −p, forcing λ′ = λ. As remarked earlier, one can now easily derive theorem 4.2.1, and theorem 4.3.1 also follows. In fact it can be extended with new commutation relations.

5.4.3. Theorem. Let f, f′ be pictures. If f′ is the domain (respectively image) glissement of f into s, then f^{′T} is the domain (image) glissement of f^{T} into s^{t}.

Proof. By corollary 5.4.2 and symmetry, it will be sufficient to show this for image-glissements of pictures p: λ → ψ with λ ∈ P. For these we have p^{T} = S_{−ψ^{t}}(p^{t}), which by definition is the unique domainglissement λ^{t} → ψ^{t} of −p^{t}. If p′ is the image-glissement of p into s, then −p^{′t} is the image-glissement of −p^{t} 5.5 Some concluding remarks

into s^{t}, by symmetry of image-glissement with respect to f ↔ −f^{t}. By theorem 5.3.1 the image-glissement of p^{T} into s^{t} is a domain-glissement of −p^{′t}; since its domain is a Young diagram, it is equal to p^{′T}.

What remains to do in this approach the theory is to establish a connection between the definitions of the Robinson-Schensted and Schützenberger correspondences by means of glissements and the traditional algorithms. For the Robinson-Schensted algorithm one can show, like in [Schü2], that the Schensted insertion procedure can be emulated using domain-glissements (proposition 5.2.1 ensures enough space to manoeuvre). To obtain the picture p of theorem 5.2.3, the squares of the domain of f are first pulled apart, and then in increasing order for ‘≤_{r}’ succesively incorporated into a “Young tableau”; careful analysis shows that the changes are governed by the rules for the insertion procedure. After each simulated insertion step, the Young diagram μ containing the “Young tableau” under construction is an order ideal for ‘≤_{↙}’ of the domain of the current picture f′, and f′(μ) coincides with the image under f of an order ideal I of (χ, ≤_{r}); for the picture q of theorem 5.2.3, it can be deduced from theorem 5.4.1 that q(I) = μ. From this we conclude that (p, q) = RS_{χ,ψ}^{α}(f), where α corresponds to ‘≤_{r}’.

For the Schützenberger correspondence we argue as follows. Let p: λ → ψ be a picture; we may assume without loss of generality that ψ = {s} ⊎ ψ′ where s is a single square, since this can be realised by imageglissements that do not alter the ordering by ‘≤_{r}’ of any of the images, and therefore by theorem 5.1.1 do not affect the moves of any domain-glissement applied to the picture. Then the restriction p′: λ \ {(0, 0)} → ψ′ of p is again a picture; let p′′ : λ′ → ψ be the domain-glissement of p′ into (0, 0). Each domain-glissement of −p gives by restriction of the image to −ψ′ a domain-glissement of −p′, and hence also of −p′′; in particular S_{ψ}(p′′) a restriction of S_{ψ}(p). Clearly, S_{ψ}(p) maps the square in λ \ λ′ to −s, and by recursively applying the same construction to p′′ one can determine S_{ψ}(p′′). From this we conclude that S_{ψ}(p) = S_{ψ}^{β}(p), where β corresponds to ‘≤_{r}’.

5.5. Some concluding remarks.

The theory of glissements of pictures forms a link between Schützenberger’s theory of ordinary glissements and Zelevinsky’s definition of the Robinson-Schensted and Schützenberger correspondences for pictures. Doing so, it provides better insight in both these theories, simplified proofs, and new results. The availability of two forms of glissement, and their commutation, are important technical tools. Our methods and results have been entirely combinatorial, but the results suggest an intricate underlying algebraic structure; so far however an interpretation of pictures that explains their properties in detail has yet to be found.

In this context it is appropriate to mention the plactic monoid of [LaSch]. The theory of the plactic monoid is about words rather than pictures, yet much of it has significance for pictures as well. The ordered alphabet A can be identified with a set of numbers, and words with negated row encodings of pictures, read off in increasing order with respect to ‘≤_{r}’. The relation of plactic equivalence translates into that of domain-glissement, and plactic action (relèvement plaxique) of the symmetric group S(A) on the set of words A^{∗} is realised by image-glissements. Then theorem 5.3.1 implies that the plactic action respects plactic equivalence [LaSch, 4.5 (5)]. This interpretation of pictures is not faithful however: glissements that involve only horizontal moves will have no effect on the word associated to a picture. It seems worth while to further investigate this connection and similar ones, and try to find refinements that better reflect the properties of pictures and glissements.

References

References.

[Clau] M. Clausen, “Multivariate polynomials, standard tableaux, and representations of symmetric groups”, J. Symbolic Computation 11, (1991), 483–522.

[ClSt] M. Clausen and F. Stötzer, “Pictures and Standardtableaux”, Bayreuther Math. Schriften 16, (1984), 1–122.

[Fom1] S. V. Fomin, “Finite partially ordered sets and Young tableaux”, Soviet Math. Dokl. 19, (1978), 1510–1514.

[Fom2] S. V. Fomin, “Generalised Robinson-Schensted-Knuth correspondence”, Journal of Soviet Mathematics 41, (1988), 979–991. (Translation from ������� ������� ��������� ���� 155 (1986) 156–175; authorised translation available from the author).

[FoGr] S. Fomin and C. Greene, “A Littlewood-Richardson Miscellany”, Europ. J. of Combinatorics 14, (1993), 191–212.

[Gre1] C. Greene, “An extension of Schensted’s Theorem”, Advances in Mathematics 14, (1974), 254–265.

[Gre2] C. Greene, “Some partitions associated with a partially ordered set”, J. Combin. Theory, Ser. A 20, (1976), 69–79.

[Haim] M. D. Haiman, “Dual equivalence with applications, including a conjecture of Proctor”, Discrete Mathematics 99, (1992), 79–113.

[HaSu] P. Hanlon and S. Sundaram, “On a bijection between Littlewood-Richardson fillings of conjugate shape”, J. Combin. Theory, Ser. A 60, (1992), 1–18.

[JaPe] G. D. James and M. H. Peel, “Specht series for skew representations of symmetric groups”, Journal of Algebra 56, (1979), 343–364.

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

[Knu2] D. E. Knuth, The art of Computer programming, Vol. III Sorting and Searching, pp. 48–72, Addison-Wesley, 1975.

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

[vLee1] M. A. A. van Leeuwen, “An even more symmetric form of Zelevinsky’s pictures”, in Proceedings of 10. Kolloquium über Kombinatorik, Bielefeld, 1990.

[vLee2] M. A. A. van Leeuwen, The Robinson-Schensted and Schützenberger algorithms, Part I: New combinatorial proofs, CWI report AM-R9208, 44 pp, (1992). (Available via URL http://www.cwi.nl/cwi/publications/).

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

[Litt] D. E. Littlewood, The theory of group characters, 2^{nd} edition, Oxford University Press, 1950.

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

[Sag2] B. E. Sagan, “The ubiquitous Young tableau”, pp. 262–298 in Invariant theory and tableaux (D. Stanton, ed.), The IMA volumes in mathematics and its applications 19, Springer-Verlag, New York, 1990.

[Sche] C. Schensted, “Longest increasing and decreasing subsequences”, Canadian Journal of Math. 13, (1961), 179–191.

[Schü1] M. P. Schützenberger, “Quelques remarques sur une construction de Schensted”, Math. Scandinavica 12,

(1963), 117–128. [Schü2] M. P. Schützenberger, “La correspondance de Robinson”, pp. 59–113 in Combinatoire et Représentation du

Groupe Symétrique (D. Foata, ed.), Lecture Notes in Mathematics 579, 1976.

[Tho] G. P. Thomas, “On Schensted’s construction and the multiplication of Schur functions”, Advances in Mathematics 30, (1978), 8–32.

[Whi] D. White, “Some connections between the Littlewood-Richardson rule and the construction of Schensted”, J. Combin. Theory, Ser. A 30, (1981), 237–247.

[Zel1] A. V. Zelevinsky, “A Generalisation of the Littlewood-Richardson Rule and the Robinson-Schensted-Knuth Correspondence”, Journal of Algebra 69, (1981), 82–94.

[Zel2] A. V. Zelevinsky, Representations of finite classical groups, a Hopf algebra approach, Lecture Notes in Mathematics 869, Springer-Verlag, Berlin/New York, 1981.