Correspondencia Robinson-Schensted

En matemáticas , la correspondencia de Robinson-Schensted es una correspondencia biyectiva entre permutaciones y pares de diagramas de Young estándar de la misma forma. Posee diversas descripciones, todas de naturaleza algorítmica, numerosas propiedades notables y aplicaciones en combinatoria y otras áreas como la teoría de la representación . Esta correspondencia ha sido generalizada de diversas maneras, en particular por Knuth, dando lugar a la conocida como correspondencia de Robinson-Schensted-Knuth , y posteriormente por Zelevinsky , quien la generalizó a imágenes .

La descripción más sencilla de la correspondencia es mediante el algoritmo de Schensted (Schensted 1961 ) , un procedimiento que construye un tablero insertando sucesivamente los valores de la permutación según una regla específica, mientras que el otro tablero registra la evolución de la forma durante la construcción. La correspondencia había sido descrita, de forma bastante diferente, mucho antes por Robinson ( Robinson 1938 ) , en un intento de demostrar la regla de Littlewood-Richardson . A menudo se hace referencia a la correspondencia como el algoritmo de Robinson-Schensted , aunque el procedimiento utilizado por Robinson es radicalmente diferente del algoritmo de Schensted y está casi completamente olvidado. Otros métodos para definir la correspondencia incluyen un algoritmo no determinista en términos de jeu de taquin .  

La naturaleza biyectiva de la correspondencia la relaciona con la identidad enumerativa.

${\displaystyle \sum _{\lambda \in {\mathcal {P}}_{n}}(t_{\lambda })^{2}=n!}$

dónde${\displaystyle {\mathcal {P}}_{n}}$denota el conjunto de particiones de n (o de diagramas de Young con n cuadrados), y t _λ denota el número de cuadros de Young estándar de forma λ .

El algoritmo de Schensted parte de la permutación σ escrita en notación de dos líneas.

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}&\sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}}$

donde σ _i = σ ( i ) , y procede construyendo secuencialmente una secuencia de pares ordenados (intermedios) de cuadros de Young de la misma forma:

${\displaystyle (P_{0},Q_{0}),(P_{1},Q_{1}),\ldots ,(P_{n},Q_{n}),}$

donde P ₀ = Q ₀ son tableaux vacíos. Los tableaux de salida son P = P _n y Q = Q _n . Una vez construido P _{i −1} , se forma P _i insertando σ _i en P _{i −1} , y luego Q _i añadiendo una entrada i a Q _{i −1} en el cuadrado añadido a la forma por la inserción (de modo que P _i y Q _i tengan formas iguales para todos los i ). Debido al papel más pasivo de los tableaux Q _i , el último Q _n , que es parte de la salida y del que se leen fácilmente los Q _i anteriores, se llama tableaux de registro ; por el contrario, los tableaux P _i se llaman tableaux de inserción .

Inserción

El procedimiento básico utilizado para insertar cada σ _i se llama inserción de Schensted o inserción de fila (para distinguirlo de un procedimiento variante llamado inserción de columna). Su forma más simple se define en términos de "tableaux estándar incompletos": al igual que los tableaux estándar, tienen entradas distintas, formando filas y columnas crecientes, pero algunos valores (que aún deben insertarse) pueden estar ausentes como entradas. El procedimiento toma como argumentos un tableau T y un valor x que no está presente como entrada de T ; produce como salida un nuevo tableau denotado T ← x y un cuadrado s en el cual su forma ha crecido. El valor x aparece en la primera fila de T ← x , ya sea habiéndose agregado al final (si no había entradas mayores que x ), o bien reemplazando la primera entrada y > x en la primera fila de T. En el primer caso, s es el cuadrado donde se agrega x , y la inserción se completa; En este último caso, la entrada reemplazada y se inserta de manera similar en la segunda fila de T , y así sucesivamente, hasta que en algún paso se aplica el primer caso (lo que ciertamente sucede si se llega a una fila vacía de T ).

^De manera más formal, el siguiente pseudocódigo describe la inserción de una nueva fila de un valor x en T. ^{[ 1} ]

1. Establezca i = 1 y j en uno más que la longitud de la primera fila de T.
2. Mientras j > 1 y x < T _{i , j −1} , disminuya j en 1. (Ahora ( i , j ) es el primer cuadrado en la fila i con una entrada mayor que x en T , o ninguna entrada en absoluto).
3. Si el cuadrado ( i , j ) está vacío en T , finalice después de agregar x a T en el cuadrado ( i , j ) y establecer s = ( i , j ) .
4. Swap the values x and T_{i, j}. (This inserts the old x into row i, and saves the value it replaces for insertion into the next row.)
5. Increase i by 1 and return to step 2.

The shape of T grows by exactly one square, namely s.

Correctness

The fact that T ← x has increasing rows and columns, if the same holds for T, is not obvious from this procedure (entries in the same column are never even compared). It can however be seen as follows. At all times except immediately after step 4, the square (i, j) is either empty in T or holds a value greater than x; step 5 re-establishes this property because (i, j) now is the square immediately below the one that originally contained x in T. Thus the effect of the replacement in step 4 on the value T_{i, j} is to make it smaller; in particular it cannot become greater than its right or lower neighbours. On the other hand the new value is not less than its left neighbour (if present) either, as is ensured by the comparison that just made step 2 terminate. Finally to see that the new value is larger than its upper neighbour T_{i−1, j} if present, observe that T_{i−1, j} holds after step 5, and that decreasing j in step 2 only decreases the corresponding value T_{i−1, j}.

Una de las propiedades más fundamentales, pero que no resulta evidente a partir de la construcción algorítmica, es la simetría:

• Si la correspondencia de Robinson-Schensted asocia los cuadros ( P , Q ) a una permutación σ , entonces asocia ( Q , P ) a la permutación inversa σ ⁻¹ .

Esto se puede demostrar, por ejemplo, recurriendo a la construcción geométrica de Viennot .

Otras propiedades, todas asumiendo que la correspondencia asocia los tableaux ( P , Q ) a la permutación σ = ( σ ₁ , ..., σ _n ) .

• En el par de tableaux ( P ′, Q ′) asociados a la permutación invertida ( σ _n , ..., σ ₁ ) , el tableau P ′ es la transpuesta del tableau P , y Q ′ es un tableau determinado por Q , independientemente de P (es decir, la transpuesta del tableau obtenido a partir de Q mediante la involución de Schützenberger ).
• La longitud de la subsecuencia creciente más larga de σ ₁ , ..., σ _n es igual a la longitud de la primera fila de P (y de Q ).
• The length of the longest decreasing subsequence of σ₁, ..., σ_n is equal to the length of the first column of P (and of Q), as follows from the previous two properties.
• The descent set {i : σ_i > σ_i+1} of σ equals the descent set {i : i+1 is in a row strictly below the row of i} of Q.
• Identify subsequences of π with their sets of indices. It is a theorem of Greene that for any k ≥ 1, the size of the largest set that can be written as the union of at most k increasing subsequences is λ₁ + ... + λ_k. In particular, λ₁ equals the largest length of an increasing subsequence of π.
• If σ is an involution, then the number of fixed points of σ equals the number of columns of odd length in λ.

• Viennot's geometric construction, which provides a diagrammatic interpretation of the correspondence.
• Plactic monoid: the insertion process can be used to define an associative product of Young tableaux with entries between 1 and n, which is referred to as the Plactic monoid of order n.

• Fulton, William (1997), Young Tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, ISBN 978-0-521-56144-0, MR 1464693.
• Knuth, Donald E. (1970), "Permutations, matrices, and generalized Young tableaux", Pacific Journal of Mathematics, 34 (3): 709–727, doi:10.2140/pjm.1970.34.709, MR 0272654
• Robinson, G. de B. (1938), "Sobre las representaciones del grupo simétrico", American Journal of Mathematics , 60 (3): 745– 760, doi : 10.2307/2371609 , JSTOR 2371609 , Zbl 0019.25102  .
• Sagan, BE (2001), El grupo simétrico , Textos de posgrado en matemáticas, vol.  203, Nueva York: Springer-Verlag, ISBN 0-387-95067-2.
• Schensted, C. (1961), "Subsecuencias crecientes y decrecientes más largas", Canadian Journal of Mathematics , 13 : 179–191 , doi : 10.4153/CJM-1961-015-3 , MR 0121305 .
• Stanley, Richard P. (1999), Combinatoria enumerativa, vol. 2 , Cambridge Studies in Advanced Mathematics, vol.  62, Cambridge University Press , ISBN 978-0-521-56069-6, MR 1676282 .
• Zelevinsky, AV (1981), "Una generalización de la regla de Littlewood-Richardson y la correspondencia de Robinson-Schensted-Knuth", Journal of Algebra , 69 (1): 82–94 , doi : 10.1016/0021-8693(81)90128-9 , MR 0613858 .

• Green, James A. (2007). Representaciones polinomiales de GL _n . Lecture Notes in Mathematics. Vol.  830. Con un apéndice sobre correspondencia de Schensted y caminos de Littelmann por K. Erdmann, JA Green y M. Schocker (2.ª  ed. corregida y ampliada). Berlín: Springer-Verlag . ISBN 978-3-540-46944-5. Zbl 1108.20044 . 

• van Leeuwen, MAA (2001) [1994], "Correspondencia Robinson-Schensted" , Enciclopedia de Matemáticas , EMS Press
• Williams, L., Animación interactiva del algoritmo de Robinson-Schensted