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 µ. 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 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
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
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].
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. 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
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 = 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. 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).
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 = 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.
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 α and β 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 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, α = 35143, β = 32454. We call (α , β ) as to be the RSK product of α and β, denoted by (α , β ) =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 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 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
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,). 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
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.