En matemáticas , la correspondencia de Robinson-Schensted es una correspondencia biyectiva entre permutaciones y pares de tablas 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 se ha generalizado de numerosas maneras, en particular por Knuth a lo que se conoce como la correspondencia de Robinson-Schensted-Knuth , y una generalización posterior a imágenes por Zelevinsky .
La descripción más simple de la correspondencia es mediante el algoritmo de Schensted (Schensted 1961), un procedimiento que construye una tabla insertando sucesivamente los valores de la permutación de acuerdo con una regla específica, mientras que la otra tabla 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 demostrar la regla de Littlewood-Richardson . La correspondencia a menudo se conoce como el algoritmo de Robinson-Schensted , aunque el procedimiento utilizado por Robinson es radicalmente diferente del algoritmo de Schensted y 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
donde denota el conjunto de particiones de n (o de diagramas de Young con n cuadrados), y t λ denota el número de tablas de Young estándar de forma λ .
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 tablas de Young de la misma forma:
donde P 0 = Q 0 son tablas vacías. Las tablas de salida son P = P n y Q = Q n . Una vez que se construye 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 tienen formas iguales para todos los i ). Debido al papel más pasivo de las tablas Q i , la última Q n , que es parte de la salida y de la que se leen fácilmente las Q i anteriores, se llama tabla de registro ; por el contrario, las tablas P i se llaman tablas de inserción .
El procedimiento básico utilizado para insertar cada σ i se denomina inserción de Schensted o inserción por filas (para distinguirlo de un procedimiento variante llamado inserción por columnas). Su forma más simple se define en términos de "tablas estándar incompletas": como las tablas estándar, tienen entradas distintas, que forman filas y columnas crecientes, pero algunos valores (aún por insertar) pueden estar ausentes como entradas. El procedimiento toma como argumentos una tabla T y un valor x no presente como entrada de T ; produce como salida una nueva tabla denotada T ← x y un cuadrado s por el cual ha crecido su forma. 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 presentes), o reemplazando de otro modo la primera entrada y > x en la primera fila de T . En el primer caso s es el cuadrado donde se agrega 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 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 fila de un nuevo valor x en T. [1]
La forma de T crece exactamente en un cuadrado, es decir, s .
El hecho de que T ← x tenga filas y columnas crecientes, si lo mismo se cumple para 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 ; el paso 5 restablece esta propiedad porque ( i , j ) ahora es el cuadrado inmediatamente debajo del que originalmente contenía x en T . Por lo 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 volverse mayor que sus vecinos derechos o inferiores. Por otro lado, el nuevo valor tampoco es menor que su vecino izquierdo (si está presente), como lo garantiza la comparación que acaba de hacer que el paso 2 termine. 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 mantiene después del paso 5, y que disminuir j en el paso 2 solo disminuye el valor correspondiente T i −1, j .
El algoritmo completo de Schensted aplicado a una permutación σ procede de la siguiente manera.
El algoritmo produce un par de tablas de Young estándar.
Se puede observar que dado cualquier par ( P , Q ) de tablas 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 utilizando 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 que se reemplaza una entrada de 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 tablas de Young estándar de igual forma y que contienen n cuadrados en el otro lado.
Una de las propiedades más fundamentales, pero no evidente a partir de la construcción algorítmica, es la simetría:
Esto puede demostrarse, por ejemplo, apelando a la construcción geométrica de Viennot .
Propiedades adicionales, todas asumiendo que la correspondencia asocia las tablas ( P , Q ) a la permutación σ = ( σ 1 , ..., σ n ) .
La correspondencia de Robinson-Schensted se puede utilizar para dar una prueba simple del teorema de Erdős-Szekeres .
