En matemáticas , la correspondencia de Robinson-Schensted es una correspondencia biyectiva entre permutaciones y pares de cuadros de Young estándar de la misma forma. Tiene varias descripciones, todas de naturaleza algorítmica, tiene muchas propiedades notables y tiene aplicaciones en combinatoria y otras áreas como la teoría de la representación . La correspondencia ha sido generalizada de numerosas formas, en particular por Knuth a lo que se conoce como correspondencia Robinson-Schensted-Knuth , y una mayor generalización a las imágenes de Zelevinsky .
La descripción más simple de la correspondencia es utilizar el algoritmo de Schensted (Schensted 1961 ), un procedimiento que construye un cuadro insertando sucesivamente los valores de la permutación de acuerdo con una regla específica, mientras que el otro cuadro registra la evolución de la forma durante la construcción. La correspondencia había sido descrita, de una forma bastante diferente, mucho antes por Robinson ( Robinson 1938 ), en un intento de probar la regla de Littlewood-Richardson . La correspondencia se conoce a menudo como el algoritmo de Robinson-Schensted , aunque el procedimiento utilizado por Robinson es radicalmente diferente del algoritmo de Schensted, y se olvida casi por completo. 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 :
dónde 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
El algoritmo de Schensted comienza con la permutación σ escrita en notación de dos líneas
donde σ i = σ ( i ) , y procede construyendo secuencialmente una secuencia de pares ordenados (intermedios) de cuadros de Young de la misma forma:
donde P 0 = Q 0 son cuadros vacíos. Los cuadros de salida son P = P n y Q = Q n . Una vez P i -1 se construye, una formas de P i por la inserción de σ i en P i -1 , y luego Q i añadiendo una entrada i a Q i -1 en la plaza añadido a la forma por la inserción (de modo que P i y Q i tienen formas iguales para todo i ). Debido al papel más pasivo de los cuadros Q i , el último Q n , que es parte del resultado y del que se pueden leer fácilmente los Q i anteriores , se denomina cuadro de registro ; por el contrario, los cuadros P i se denominan cuadros 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 "cuadros estándar incompletos": al igual que los cuadros estándar, tienen entradas distintas, formando filas y columnas crecientes, pero algunos valores (aún por insertar) pueden estar ausentes como entradas. El procedimiento toma como argumentos un cuadro T y un valor x no presente como entrada de T ; produce como salida un nuevo cuadro denominado T ← x y un cuadrado s por el cual su forma ha crecido. El valor x aparece en la primera fila de T ← x , ya sea después de haber sido añadido al final (Si no hay entradas más grandes que x estaban presentes), o de otro modo la sustitución de la primera entrada y > x en la primera fila de T . En el primer caso, s es el cuadrado donde se suma x y se completa la inserción; en el ú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 aplique el primer caso (lo que ciertamente sucede si se alcanza una fila vacía de T ).
Más formalmente, el siguiente pseudocódigo describe la fila-inserción de un nuevo valor de x en T . [1]
- Puse i = 1 y j a uno más que la longitud de la primera fila de T .
- Mientras que 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 sin ninguna entrada).
- Si el cuadrado ( i , j ) está vacío en T , termine después de sumar x a T en el cuadrado ( i , j ) y establecer s = ( i , j ) .
- Intercambia los valores x y T i, j . (Esto inserta la antigua x en la fila i y guarda el valor que reemplaza para insertarlo en la siguiente fila).
- Aumente i en 1 y vuelva al paso 2.
La forma de T crece exactamente un cuadrado, a saber, s .
Exactitud
El hecho de que T ← x tenga filas y columnas crecientes, si lo mismo ocurre con T , no es obvio a partir de este procedimiento (las entradas en la misma columna nunca se comparan). Sin embargo, puede verse de la siguiente manera. En todo momento, excepto inmediatamente después del paso 4, el cuadrado ( i , j ) está vacío en T o tiene un valor mayor que x ; paso 5 re-establece esta propiedad porque ( i , j ) ahora es el cuadrado inmediatamente por debajo de la que contenía originalmente x en T . Por tanto, el efecto del reemplazo en el paso 4 sobre el valor T i, j es hacerlo más pequeño; en particular, no puede llegar a ser más grande que sus vecinos inferiores o de derecha. Por otro lado, el nuevo valor tampoco es menor que su vecino de la izquierda (si está presente), como lo garantiza la comparación que acaba de terminar el paso 2. Finalmente, para ver que el nuevo valor es mayor que su vecino superior T i −1, j si está presente, observe que T i −1, j se cumple después del paso 5, y que al disminuir j en el paso 2 solo disminuye el valor correspondiente T i - 1, j .
Construyendo los cuadros
El algoritmo de Schensted completo aplicado a una permutación σ procede de la siguiente manera.
- Establecer tanto P como Q en el cuadro vacío
- Para i creciente desde 1 a n compute P ← sigma i y el cuadrado s por el procedimiento de inserción; luego reemplace P por P ← σ i y agregue la entrada i al cuadro Q en el cuadrado s .
- Terminar, devolviendo el par ( P , Q ) .
El algoritmo produce un par de cuadros de Young estándar.
Invertibilidad de la construcción
Se puede ver que dado cualquier par ( P , Q ) de cuadros de Young estándar de la misma forma, existe un procedimiento inverso que produce una permutación que dará lugar a ( P , Q ) por el algoritmo de Schensted. Básicamente consiste en rastrear los pasos del algoritmo hacia atrás, cada vez usando una entrada de Q para encontrar el cuadrado donde debe comenzar la inserción inversa, moviendo la entrada correspondiente de P a la fila anterior y continuando hacia arriba a través de las filas hasta una entrada de se reemplaza la primera fila, que es el valor insertado en el paso correspondiente del algoritmo de construcción. Estos dos algoritmos inversos definen una correspondencia biyectiva entre permutaciones de n en un lado y pares de cuadros de Young estándar de igual forma y que contienen n cuadrados en el otro lado.
Propiedades
Una de las propiedades más fundamentales, pero no evidente a partir de la construcción algorítmica, es la simetría:
- Si la correspondencia de Robinson-Schensted asocia cuadros ( P , Q ) a una permutación σ , entonces asocia ( Q , P ) a la permutación inversa σ −1 .
Esto se puede probar, por ejemplo, apelando a la construcción geométrica de Viennot .
Otras propiedades, todas asumiendo que la correspondencia asocia cuadros ( P , Q ) a la permutación σ = ( σ 1 , ..., σ n ) .
- En el par de cuadros ( P ′, Q ′) asociados a la permutación inversa ( σ n , ..., σ 1 ) , el cuadro P ′ es la transposición del cuadro P , y Q ′ es un cuadro determinado por Q , independientemente de P (es decir, la transposición del cuadro obtenido de Q por la involución de Schützenberger ).
- La longitud de la subsecuencia creciente más larga de σ 1 , ..., σ n es igual a la longitud de la primera fila de P (y de Q ).
- La longitud de la subsecuencia decreciente más larga de σ 1 , ..., σ n es igual a la longitud de la primera columna de P (y de Q ), como se deduce de las dos propiedades anteriores.
- El conjunto de descenso { i : σ i > σ i +1 } de σ es igual al conjunto de descenso { i : i 1 está en una fila estrictamente por debajo de la fila de i } de Q .
- Identifica subsecuencias de π con sus conjuntos de índices. Es un teorema de Greene que para cualquier k ≥ 1 , el tamaño del conjunto más grande que se puede escribir como la unión de como máximo k subsecuencias crecientes es λ 1 + ... + λ k . En particular, λ 1 es igual a la mayor longitud de una subsecuencia creciente de π .
- Si σ es una involución , entonces el número de puntos fijos de σ es igual al número de columnas de longitud impar en λ .
Ver también
- Construcción geométrica de Viennot , que proporciona una interpretación esquemática de la correspondencia.
- Monoide Plactic : el proceso de inserción se puede utilizar para definir un producto asociativo de cuadros de Young con entradas entre 1 y n , que se conoce como el monoide Plactic de orden n .
Notas
- ^ Adaptado de DE Knuth (1973), The Art of Computer Programming , 3 , págs. 50-51
Referencias
- Fulton, William (1997), Young Tableaux , London Mathematical Society Student Texts, 35 , Cambridge University Press , ISBN 978-0-521-56144-0, Señor 1464693.
- Knuth, Donald E. (1970), "Permutaciones, matrices y cuadros de Young generalizados" , Pacific Journal of Mathematics , 34 : 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), The Symmetric Group , Textos de posgrado en matemáticas, 203 , Nueva York: Springer-Verlag, ISBN 0-387-95067-2.
- Schensted, C. (1961), "Las 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, 62 , Cambridge University Press , ISBN 978-0-521-56069-6, MR 1676282.
- Zelevinsky, AV (1981), "Una generalización de la regla Littlewood-Richardson y la correspondencia Robinson-Schensted-Knuth", Journal of Algebra , 69 (1): 82-94, doi : 10.1016 / 0021-8693 (81) 90128 -9 , MR 0613858.
Otras lecturas
- Green, James A. (2007). Representaciones polinomiales de GL n . Apuntes de clase en matemáticas. 830 . Con un apéndice sobre correspondencia de Schensted y rutas de Littelmann por K. Erdmann, JA Green y M. Schocker (2ª edición corregida y aumentada). Berlín: Springer-Verlag . ISBN 3-540-46944-3. Zbl 1108.20044 .
enlaces externos
- van Leeuwen, MAA (2001) [1994], "Correspondencia Robinson-Schensted" , Encyclopedia of Mathematics , EMS Press