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.
Growth diagrams local rules (i) (ii) (iii) = = = 6= = 6= (v) 6= and the cell is empty, then
= , , then
= , , then
= , (iv) ; ; ; are pairwise di erent, then = [in fact, in the repetition of the local rules, we will have = = + (i)] (vi) = = and there is a point in the cell, then =
+ (1). = , then = + (i + 1), given that = and di ers in the i-th row,
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], lling the cells of the Ferrers diagram F with some (black) points (see Figure 2). Starting with empty diagrams on the rst row and rst 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
Now we de ne 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.
(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 > 0, then E(c) = N (c) = i + 1, = 42153 with the pair (P; Q) associated to by (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.
Starting with Ferrers diagram F , with some cells lled 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 nal labeling does not depend on which order are applied the local rules to the di erent cells of F .
An example is displayed on Figure 4 in the case of a square Ferrers diagram F = G(n) lled 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 lled 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 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. 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 are the Yamanouchi coding of the respective P and Q symbols of via the RS correspondence.
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 di erential 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
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 rst two local rules above are the same, that is we have only the right part of Figure 3.
(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 rst row and rst 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 grid, one can ll the whole edges of the grid and get two words reading the rst row and column of the grid, by reversing the local rules de ned 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 ( ; ).
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 Schutzenberger'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 Schutzenberger [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 de ne edge local rules for the extension due to D. Knuth [Knu70] of the Robinson-Schensted correspondence to matrices with integers coe cients, 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 lled 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 de ne some corresponding edge local rules using the RSK product de ned above. (see the course [Vi18, Ch1e, p 62-89]) 4
Jeu de taquin has been invented by Schutzenberger [Sch77]. Local rules for the jeu de taquin has been de ned by S. Fomin [Fom88, Fom99]. Again, as for growth diagrams local rules, some rules are de ned for a cell where 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 gure 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 di erent 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 de ne the operator i acting on Ferrers diagrams by adding a cell (if possible) to a diagram on diagonal line labeled i.
We de ne 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 ji (ii) If W (c) = j; S(c) = i, with ji jj jj 2, then E(c) = j and N (c) = i, 1, then E(c) = i and N (c) = j. 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 rst column and the bottom row coding the Young tableau displayed on the right of this rst row. Thus the sequence of blue Ferrers diagrams, reading the bottom row from right to left, and then the rst 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 rst row and rst 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( )).
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 ji jj 2 will intersect, else they will `re ect' 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 so well-known that it seems di cult 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.
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 clari ed and part of this material was discovered during the course. The author thanks the hospitality of Amrita University Coimbatore where this paper was written.