=Paper=
{{Paper
|id=Vol-2113/paper22
|storemode=property
|title=Growth diagrams and edge local rules
|pdfUrl=https://ceur-ws.org/Vol-2113/paper22.pdf
|volume=Vol-2113
|authors=Xavier Viennot
|dblpUrl=https://dblp.org/rec/conf/gascom/Viennot18
}}
==Growth diagrams and edge local rules==
https://ceur-ws.org/Vol-2113/paper22.pdf
Growth diagrams and edge local rules
Xavier Viennot
LaBRI, CNRS, Université de Bordeaux and IMSc Chennai, India, www.viennot.org
viennot@xavierviennot.org
Abstract
Fomin growth diagrams for the Robinson-Schensted correspondence
and for the jeu de taquin are some rules allowing the construction of
the 4th Ferrers diagram once 3 Ferrers diagrams around an elementary
cell are known.We propose here to replace these rules by some local
rules on edges instead of local rules on vertices.
1 Growth diagrams
We recall the classical Fomin’s ‘local rules’ or ‘growth diagrams’, which in particular can describe the Robinson-
Schensted correspondence. We follow the notations of the paper [Kra06]. We start from a Ferrers diagram F
(also called Ferrers board) where some cell are filled with a (black) point, with the condition that there is at
most one point in each row and column. Each ‘vertex’ of the Ferrers board (see an example on Figure 2) is
going to be labeled by a Ferrers diagram (or partition of integers) with the initial condition that the labels of
the South-West border of F (i.e. the vertex of the West and South border are labeled with an empty diagram).
Then, the vertices of the diagram F are labeled recursively, applying the six following possible ‘local rules’ on
each cell of F .
If ρ, µ, ν, are known Ferrers diagrams, attached to the South-West vertices of a cell of F displayed as in Figure
1, then the Ferrers diagram λ (North-East corner) is defined by the following ”local rules”, with the notation:
Notation. µ + (i) is the Ferrers diagram obtained from µ by adding (if possible) a cell at the i-th row of µ.
Growth diagrams local rules
(i) ρ = µ = ν and the cell is empty, then λ = ρ,
(ii) ρ = µ 6= ν , thenλ = ν,
(iii) ρ = ν 6= µ , then λ = µ,
(iv) ρ, µ, ν, are pairwise different, then λ = µ ∪ ν,
(v) ρ 6= µ = ν , then λ = µ + (i + 1), given that µ = ν and ρ differs in the i-th row,
[in fact, in the repetition of the local rules, we will have µ = ν = ρ + (i)]
(vi) ρ = µ = ν and there is a point in the cell, then λ = µ + (1).
Copyright © by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org
202
Figure 1: The six growth diagrams local rules.
We can visualized these local rules on Figure 1. Growth diagrams were introduced by Fomin in [Fom88], and
described for example in [BF01, Sec 3], [Kra06], [vLee96, 05], [Rob91, Ch2], [Sag01, Sec 5.2], [Sta99, Sec 7.13].
In the case F is a square Ferrers diagram with n rows and columns and there is one and only one point in each
row and column, we get back the classical Robinson-Schensted correspondence between permutations and pairs
of (standard) Young tableaux. We will denote by G(n + 1) = [1, n + 1]X[1, n + 1] (see Figure 2) the ‘grid’ formed
by the edges of the cells of the square Ferrers diagram F .
For example, starting from a permutation (here σ = 42153), we associate the graphic representation of σ, i.e.
the set of points (i, σ(i)) for i = 1, ..., n on the grid [1, n]X[1, n]. In fact, these points are located at the center
of the elementary cells of the grid G(n + 1) = [1, n + 1]X[1, n + 1], filling the cells of the Ferrers diagram F with
some (black) points (see Figure 2). Starting with empty diagrams on the first row and first column of the grid
G(n + 1), by recursive applications of the 6 local rules, we get a labeling of each vertex of the grid G(n + 1)
with some Ferrers diagrams. On the last row and column of the grid G(n + 1), we get two maximal chains of
Ferrers diagrams (in the poset formed by the Young lattice) which incode two (standard) Young tableaux P and
Q (see the example on Figure 2). It is well known that the pair (P, Q) is exactly the pair of Young tableaux
associated to the permutation σ by the Robinson-Shensted correspondence. The tableau P (resp. Q) associated
to the maximal chain of diagrams located on the East (resp North) border of F is the so-called insertion (resp.
recording) tableau of the permutation σ.
For simplicity, we will restrict our examples to the case where the Ferrers diagram F is the square grid G(n) =
[1, n]X[1, n]. Everything in this paper could be easily extended to any Ferrers diagram F with an arbitrary
placement of points (with at most one point in each row and column, also called rook placement). In the case of
an arbitrary Ferrers diagram F , but with the condition that there are exactly one point in each row and column,
then the Robinson-Schensted correspondence becomes the correspondence between such rook placements and the
so-called oscillating tableaux. (see for example [Vie18, Ch1e, p 90-123].
2 Edge local rules
Now we define the edge local rules for the Ferrers diagram F (see Figure 4 with F = G(n)). The cells of the grid
has two possible types: a (black) point in the cell or empty cell. The edges of each cell c of the grid are labeled
by non-negative integers. We denote by W (c), E(c), S(c),and N (c) the label of the respective West, East, South
and North edges of the cell c.
Edge local rules
(i) If W (c) = i, S(c) = j, with i 6= j, then E(c) = i and N (c) = j,
203
Figure 2: Growth diagrams algorithm for the permutation σ = 42153 with the pair (P, Q) associated to σ by
the Robinson-Schensted correspondence.
(ii) If W (c) = S(c) = i > 0, then E(c) = N (c) = i + 1,
(iii) If W (c) = S(c) = 0, then E(c) = N (c) = 0 if the cell is empty, else (the cell has a black point) E(c) =
N (c) = 1.
Figure 3: Edge local rules.
Starting with Ferrers diagram F , with some cells filled with a (black) point, with at most one point in each row
and each column (or rook placement), one can label the whole set of edges of the diagram F . The final labeling
does not depend on which order are applied the local rules to the different cells of F .
An example is displayed on Figure 4 in the case of a square Ferrers diagram F = G(n) filled with the points of
the graphical representation of the permutation σ = 42153 (the dot lines means label i = 0).
Proposition 2.1. The two processes ‘growth diagrams’ and ‘edge local rules’ are equivalent.
By equivalent we mean the following. For a Ferrers diagram F , with some cells filled with points, we label the
vertices (resp. the edges) of the grid underlying F according to the two algorithms described above with their
initial conditions. If an horizontal (resp. vertical) edge is labeled i ≥ 0, connecting two vertices labeled with
some Ferrers diagram ν and λ (resp. µ and λ), as in Figures 1 or 5, then ν = λ (resp µ = λ) if i = 0; and
λ = ν + (i) (resp. λ = µ + (i)) if i > 0.
One possible proof is via the shadow lines of the geometric construction of RS (see Figure 6) given by the author
in [Vi75] (extended to a Ferrers diagram F and rook placement instead of the grid G(n + 1) and a permutation).
The label i given to an edge corresponds exactly to the color of the shadow line associated to σ (or the rook
placement) (0 for no lines crossing the edge, 1 for black lines, 2 for red lines, 3 for blue lines, etc ...). The four
possible cases of the edge local rules become six possible cases. The six cases of the growth diagrams correspond
204
Figure 4: The edge local rules algorithm with the permutation σ = 42153.
to the six possibilities for a cell being crossed by shadow lines: no lines is crossing, only one line (horizontal or
vertical) is crossing, two lines are crossing with labels i 6= j or with label i = j (becoming after the crossing
i + 1), and the last case where there is a point in the cell (which is the starting of shadow lines labeled 1). This
six cases are displayed on Figure 5, to be compared with the six local rules for growth diagrams displayed on
Figure 1.
Figure 5: Correspondence shadow lines, edge local rules and growth diagrams local rules.
An example of the correspondence between growth diagrams, edge local rules and shadow lines is displayed on
Figure 6 in the case of a square Ferrers diagram F and a rook placement which is a permutation (the dot lines
means label i = 0). In the case of a permutation σ, we get two words u(σ) and v(σ) by reading the labels of
the East border from bottom to top (resp. North border reading from left to right). (see Figure 4 or 6). These
words u = 12132 and v = 12312 are the so-called Yamanouchi coding of the Young tableaux P and Q. The
integer x will be placed in the i-th row in P if and only if the x-th letter of u is i.
Corollary 2.2. For a permutation σ, the two words u(σ) and v(σ) obtained by the edge local rule algorithm
205
are the Yamanouchi coding of the respective P and Q symbols of σ via the RS correspondence.
Figure 6: Shadow lines, edge local rules and growth diagrams for the permutation σ = 42153.
Remark about proposition 2.1 The label of an edge corresponds exactly to the operator µ + (i), operator
adding a cell to the Ferrers diagram µ at the i-th row. In Fomin approach [Fom94, 95], the growth diagrams
rules corresponds to a representation of the Weyl-Heisenberg algebra with two operators U and D, satisfying the
commutation relation U D = DU + Id, where U and D act on the vector space generated by Ferrers diagrams,
and U (F ) (F Ferrers diagram) (resp. D(F )) is the sum of all possible Ferrers diagrams obtained by adding
(resp. deleting) a cell to F . This is the approach considering the Young lattice as a differential poset. May be
Proposition2.1 is not really new and is probably implicit in Fomin’s approach.
The shadow lines approach gives an easy proof of the fact that Fomin local rules are equivalent to the RS
correspondence: for each vertex of the grid G(n + 1), one can associate directly a Ferrers diagram by counting
the number of shadow lines with label 1, 2, 3, .. in the South-West corner attached to this vertex (number of cells
on row i will be the number of shadow lines with label i). Then this set of Ferrers diagrams labeling the vertices
of the grid G(n + 1) is the same as the one obtained by Fomin growth diagrams local rules. (and the geometric
version of RS is easily seen to be equivalent to the Schensted’s bumping process).
3 The RSK bilateral edge local rules
We propose a symmetric version of the edge local rules. We label the edges of the grid formed by a Ferrers
diagram F by intergers, positive or negative, but 6= 0 with the following local rules. There is no more two
possible labels for the cell (‘empty’ of containing a point). The first two local rules above are the same, that is
we have only the right part of Figure 3.
Bilateral edge local rules
(i) If W (c) = i, S(c) = j, with i 6= j, then E(c) = i and N (c) = j,
(ii) If W (c) = S(c) = i, then E(c) = N (c) = i + 1, with the convention that (−1) + 1 = 1 (or symmetrically
1 − (1) = −1 )
In the case of F a square grid, starting with some labels on the first row and first column (giving two words
α and β, we can label the whole set of edges and thus get two words α0 and β 0 by reading the last row and
column of the grid. The algorithm is reversible. Starting form two words labeling the last row and column of the
206
grid, one can fill the whole edges of the grid and get two words reading the first row and column of the grid, by
reversing the local rules defined by (i) and (ii). An example is displayed on Figure 7 with α = 13132, β = 21342,
α0 = 35143, β 0 = 32454. We call (α0 , β 0 ) as to be the RSK product of α and β, denoted by (α0 , β 0 ) =RSK (α, β).
Figure 7: The RSK bilateral edge local rules, the RSK product (α0 , β 0 )=RSK(α, β).
Starting with the two Yamanouchi words u and v of Figure 4, coding the P and Q symbol of the permutation
σ = 42153, we get the positive labels of Figure 4. But we can continue the RSK bilateral edge rules going to the
South-West with negative labels and get the complete labeling of the grid with positive and negative integers, as
displayed on Figure 8. In fact, the part of this diagram with negative labels on the edges corresponds to applying
the edge local rules from North-East to South-West, i.e. applying this local rules for the complementary of the
mirror image of the permutation σ, and thus, from Schützenberger’s theorem about duality, we get the following
proposition.
Proposition 3.1. Starting with a labeling of the edges on the North and East border of the grid G(n + 1) such
that reading these labels gives two Yamanouchi words u and v coding two Young tableaux P and Q. Applying the
RSK bilateral edge local rules from North-East to South-West, we get a complete labeling of the grid G(n + 1).
The labels on the South and East border of the grid gives rise (deleting the negative sign) to two words u∗ and
v ∗ . These two words are Yamanouchi words and are the coding of two Young tableaux P ∗ and Q∗ which are
respectively the dual tableaux of P and Q (dual in the sense of Schützenberger [Sch72])
Thus, in the case of Yamanoucchi words, the RSK product corresponds to duality of Young tableaux.
Using this notion of RSK product it would be possible to define edge local rules for the extension due to D.
Knuth [Knu70] of the Robinson-Schensted correspondence to matrices with integers coefficients, i.e. the so- called
Robinson-Schensted-Knuth correspondence. For matrices with only entries 0 and 1 (corresponding to Ferrers
diagrams with cells empty or filled with a point, but with no condition on the number of points in each row
and column) there exist in fact four RSK correspondences, denoted RSK, dual RSK, RSK’ and dual RSK’ (see
[Kra06]). For each of these correspondences, it is possible to define some corresponding edge local rules using
the RSK product defined above. (see the course [Vi18, Ch1e, p 62-89])
4 Edge local rules for the jeu de taquin
Jeu de taquin has been invented by Schützenberger [Sch77]. Local rules for the jeu de taquin has been defined
by S. Fomin [Fom88, Fom99]. Again, as for growth diagrams local rules, some rules are defined for a cell where
207
Figure 8: The RSK bilateral edge local rules and Schützenberger duality of Young tableaux.
3 of the vertices are labeled by Ferrers diagrams. Here we give an equivalent algorithm, but working with labels
on the edges of the cell.
Fomin encoded the jeu de taquin by a rectangle where vertices are labeled by Ferrers diagrams. An example is
displayed on Figure 9 (left). Each column encode a skew Young tableau, as a maximal chain of Ferrers diagrams,
starting with the Ferrers diagram in the bottom row. The bottom row encode a Young tableau giving in which
order will be done the choices of the cell where the jeu de taquin will be performed. Starting form the leftmost
column, column by column, choices are given for starting the slidings; the result is given by the skew Young
tableau at the top of the rectangle. At the end, we get a Young tableau (displayed at the top of the last column)
which, as it is well known, does not depend of the choices given by the Young tableau encoded in the bottom
row (and displayed at South-East corner of the rectangle in figure 9). Fomin local rules, are the following (see
Figure 10 (left) for the positions of µ, ν, ρ, λ around a cell)
Fomin local rules for the jeu de taquin
(i) if µ is the only shape of its size that contains ν and is contained in ρ, then λ = µ,
(ii) otherwise there is a unique such shape different from µ and this is λ.
We label the lines parallel to the diagonal of the square lattice by integers, positive or negative according to the
contents (j − i) of the cells as shown on Figure 10 (right,down) and define the operator ∆i acting on Ferrers
diagrams by adding a cell (if possible) to a diagram on diagonal line labeled i.
We define the edge local rules for jeu de taquin with the two following reversible rules, see Figure 10 (right top).
Edge local rules for the jeu de taquin
(i) If W (c) = j, S(c) = i, with |i − j| ≥ 2, then E(c) = j and N (c) = i,
(ii) If W (c) = j, S(c) = i, with |i − j| ≤ 1, then E(c) = i and N (c) = j.
208
Figure 9: Coding of the jeu de taquin (left), the edge local rules for the jeu de taquin (right).
For a rectangle F , the initial conditions are the labeling of the West and South border with Ferrers diagrams
as in Figure 9: the blue Ferrers diagrams coding the skew tableau on the top of the first column and the
bottom row coding the Young tableau displayed on the right of this first row. Thus the sequence of blue Ferrers
diagrams, reading the bottom row from right to left, and then the first column form bottom to top, form a
maximal chain of Ferrers diagrams starting at the empty diagram. From this sequence, we can label the edges
of the first row and first column with some integers. An edge receives the label i if in the sequence of diagrams,
it corresponds to go from one diagram to the other by applying the operator ∆i .
Proposition 4.1. Fomin local rules with diagrams for the jeu de taquin and edge local rules for the jeu de taquin
are equivalent.
By equivalent we mean the following. For a rectangle F , we label the vertices (resp. the edges) of the grid
underlying F according to the two algorithms with the initial conditions described above. If an horizontal (resp.
vertical) edge is labeled i, connecting two vertices labeled with some Ferrers diagrams ρ and λ (resp. ν and λ),
as in the cell displayed here on Figure 10 (left), then ρ = ∆i (λ), (resp. λ = ∆i (ν)).
An example is displayed on Figure 9 (right).
By connecting the edges having the same labels by some color lines, each line of label i crossing perpendicular
all edges with label i, we get an analogue of the shadow lines of section 2 and Figure 6. We can formulate in
an equivalent way the edge local rules for jeu de taquin with a kind of pipe dream lines. Two lines with labels i
and j with |i − j| ≥ 2 will intersect, else they will ‘reflect’ as in a pipe dream. We can also apply this edge local
rules for constructing the dual of a Young tableau. (see [Vie18, Ch1d, p 106-12]).
Final remark The operators ∆i acting on Ferrers diagrams form a representation of the nil-Temperley-Lieb
algebra [Vie18, Ch1d, p 113-130].
Conclusion The subject of the (ordinary) RSK correspondence and Fomin growth diagrams is so classical and
209
Figure 10: The positions of µ, ν, ρ, λ for Fomin local rules for the jeu de taquin, the edge local rules for the jeu
de taquin (right top), the diagonal operators ∆i (right down).
Figure 11: Analogue of shadow lines for the jeu de taquin.
so well-known that it seems difficult to bring some new ideas or new results. Fomin local rules (for RS and for
the jeu de taquin) are some rules allowing the construction of the 4th Ferrers diagram once 3 Ferrers diagrams
around an elementary cell are known. These rules have been widely used many times in many papers. We
propose here to replace these rules by some local rules on edges instead of local rules on vertices, which seems
to be much less used in the literature (unless in the equivalent form with the shadow lines construction of RS,
see for example the nice paper of [JoV17 ]). Comparing Figure 1 and Figure 3 , looking at Figures 10 and 11
should convince the reader that much attention should be given to the edge local rules.
Acknowledgements
The author warmly thanks Amri Prasad and the Institue of Mathematical Sciences (IMSc, Chennai, India) for
the invitation to give the third part of the course ‘The Art of Bijective Combinatorics’ where the topics of this
paper was clarified and part of this material was discovered during the course. The author thanks the hospitality
of Amrita University Coimbatore where this paper was written.
210
References
[BF01] T. Britz, S. Fomin. Finite posets and Ferrers shapes. Advances in Mathematics, 158:86-127, 2001
[Fom88] S. Fomin. Generalised Robinson-Schensted-Knuth correspondence. Journal of Soviet Mathematics,
41:979-991, 1988 (Translation from Zapiski Nauchn Sem. LOMI 155 (1986) 156-175).
[Fom94] S. Fomin. Duality of graded graphs. Journal of Algebraic Combinatorics, 3:357-404,1994.
[Fom95] S. Fomin. Schensted algorithms for dual graded graphs. Jornal of Algebraic Combinatorics, 4:5-45,
1995.
[Fom99] S. Fomin. Knuth equivalence, jeu de taquin and the Littlewood-Richardson rule. Appendix 1 in the
book [Sta99].
[JoV17 ] M. Josuat-Vergès. Stammering tableaux. Discrete Mathematics and Theoretical Computer Science,
19(3):3, 2017.
[Knu70] D. Knuth. Permutations, matrices, and generalized Young tableaux. Pacific Journal of Mathematics,
34:709-727, 1970.
[Kra06] C. Krattenthaler. Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes.
Advances in Applied Mathematics, 37:404-431, 2006.
[vLee96] M. A. van Leeuwen. The Robinson-Schensted and Schützenberger algorithm, an Elementary approach.
Electronic Journal of Combininatorics, 3 Research paper 15, 32 pp, 1996.
[vLee05] M. A. van Leeuwen. Spin-preserving Knuth correspondences for ribbon tableaux. Electronic Journal
of Combinatorics, 12(1):Article R10, 65 pp, 2005.
[Rob91] T. W. Roby. Applications and extensions of Fomin’s generalization of the Robinson-Schensted corre-
spondence to differential posets. Ph. D. thesis, M.I.T., Cambridge, Massachusetts, 1991.
[Sag01] B .E. Sagan. The symmetric group, 2nd edition. Springer-Verlag, New York, 2001.
[Sch63] M. P. Schützenberger. Quelques remarques sur une construction de Schensted. Mathematica Scandi-
navica, 12:117-12, 1963.
[Sch72] M. P. Schützenberger. Promotion des morphismes d’ensembles ordonndotés. Discrete Mathematics,
2:73-94, 1992.
[Sch77] M. P. Schützenberger. La correspondance de Robinson, in Combinatoire et représentation du groupe
symétrique. D. Foata ed., Lecture Notes in Mathematics, 579:59-135, 1978.
[Sta99] R. Stanley. Enumerative Combinatorics, vol 2. Cambridge University Press, Cambridge, 1999.
[Vie18] X. Viennot. ‘The Art of Bijective Combinatorics’, part III, Chapter 1, RSK The Robinson-Schensted-
Knuth correspondence, course given at IMSc, Chennai, India, January-April 2018. slides and videos
available on the website: http://www.viennot.org/abjc3-ch1.html .
[Vie78] G. X. Viennot. Une forme géométrique de la correspondance de Robinson-Schensted, in Combinatoire
et représentation du groupe symétrique. D. Foata ed., Lecture Notes in Mathematics, 579:29-58, 1978.
211