Correspondencia Robinson-Schensted

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

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

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 $λ$ . ${\mathcal {P}}_{n}$

El algoritmo de Schensted

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

\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 tablas de Young de la misma forma:

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

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 .

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 \leftarrow x$ y un cuadrado $s$ por el cual ha crecido su forma. El valor $x$ aparece en la primera fila de $T \leftarrow 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]

Establezca $i = 1$ y $j$ en uno más que la longitud de la primera fila de $T.$
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).
Si el cuadrado $(i, j)$ está vacío en $T$ , termina después de sumar $x$ a $T$ en el cuadrado $(i, j)$ y establecer $s = (i, j)$ .
Intercambie los valores $x$ y $T i, j$ . (Esto inserta la $x$ antigua 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 en un cuadrado, es decir, $s$ .

Exactitud

El hecho de que $T \leftarrow 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$ .

Construyendo los cuadros

El algoritmo completo de Schensted aplicado a una permutación $σ$ procede de la siguiente manera.

Establezca tanto $P$ como $Q$ en la tabla vacía
Para $i$ creciente de $1$ a $n,$ calcule $P \leftarrow σ i$ y el cuadrado $s$ mediante el procedimiento de inserción; luego reemplace $P$ por $P \leftarrow σ i$ y agregue la entrada $i$ a la tabla $Q$ en el cuadrado $s$ .
Terminar, devolviendo el par $(P, Q)$ .

El algoritmo produce un par de tablas de Young estándar.

Invertibilidad de la construcción

Se puede ver que dado cualquier par $(P, Q)$ de tablas de Young estándar de la misma forma, hay 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.

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 tablas $(P, Q)$ a una permutación $σ$ , entonces asocia $(Q, P)$ a la permutación inversa $σ -1$ .

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)$ .

En el par de tablas $(P', Q')$ asociadas a la permutación inversa $(σ n, ..., σ 1)$ , la tabla $P'$ es la transpuesta de la tabla $P$ , y $Q'$ es una tabla determinada por $Q$ , independientemente de $P$ (es decir, la transpuesta de la tabla obtenida a partir 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 desprende 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 debajo de la fila de i$ } de $Q$ .
Identificar subsucesiones de $π$ con sus conjuntos de índices. Es un teorema de Greene que para cualquier $k \geq 1$ , el tamaño del conjunto más grande que puede escribirse como la unión de como máximo $k$ subsucesiones crecientes es $λ 1 + ... + λ k$ . En particular, $λ 1$ es igual a la longitud más grande de una subsucesión 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 $λ$ .

Aplicaciones

Aplicación al teorema de Erdős-Szekeres

La correspondencia de Robinson-Schensted se puede utilizar para dar una prueba simple del teorema de Erdős-Szekeres .

Véase también

Construcción geométrica de Viennot , que proporciona una interpretación diagramática de la correspondencia.
Monoide pláctico : el proceso de inserción se puede utilizar para definir un producto asociativo de tablas de Young con entradas entre 1 y $n$ , al que se denomina monoide pláctico de orden $n$ .

Notas

^ Adaptado de DE Knuth (1973), El arte de la programación informática , vol. 3, págs. 50-51

Referencias

Fulton, William (1997), Young Tableaux , Textos para estudiantes de la London Mathematical Society, vol. 35, Cambridge University Press , ISBN 978-0-521-56144-0, Sr. 1464693.
Knuth, Donald E. (1970), "Permutaciones, matrices y tablas de Young generalizadas", 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), El grupo simétrico , Textos de posgrado en matemáticas, vol. 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, vol. 62, Cambridge University Press , ISBN 978-0-521-56069-6, Sr. 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.

Lectura adicional

Green, James A. (2007). Representaciones polinomiales de GL _n . Lecture Notes in Mathematics. Vol. 830. Con un apéndice sobre la correspondencia de Schensted y los caminos 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", Enciclopedia de Matemáticas , EMS Press
Williams, L., Animación interactiva del algoritmo Robinson-Schensted