Correspondencia Robinson-Schensted

En matemáticas , la correspondencia Robinson-Schensted es una correspondencia biyectiva entre permutaciones y pares de cuadros estándar de Young de la misma forma. Tiene varias descripciones, todas ellas 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 maneras, en particular por Knuth a lo que se conoce como correspondencia Robinson-Schensted-Knuth , y una generalización adicional a imágenes de Zelevinsky .

La descripción más sencilla 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 según 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 a menudo se denomina 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 juego de taquin .

El carácter biyectivo 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 cuadros estándar de Young de forma $λ$ . ${\mathcal {P}}_{n}$

El algoritmo de Schensted

El algoritmo de Schensted parte de 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 {pmatriz}}

donde $σ i = σ (i)$ , y procede construyendo secuencialmente una secuencia de pares ordenados (intermedios) de cuadros 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 cuadros vacíos. Los cuadros 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 $agregando$ una entrada $i$ a $Q$ $i$ $-1$ en el cuadrado agregado a la forma mediante 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 $Qi$ , el último $Qn$ $,$ que forma parte de la salida y del cual se pueden leer fácilmente los $Qi$ $anteriores , se denomina cuadro$ $de$ registro ; por el contrario $,$ los cuadros $Pi$ 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 filas (para distinguirlo de una variante del procedimiento llamado inserción de columnas). 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 resultado un nuevo cuadro denominado $T \leftarrow x$ y un cuadrado $s$ en el que su forma ha crecido. 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$ ) o reemplazando 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 aplica 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 inserción de filas 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 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)$ .
Intercambie los valores $x$ y $Ti, 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 regrese 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 ni siquiera se comparan). Sin embargo, se puede ver 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.$ Así, el efecto de la sustitución en el paso 4 sobre el valor $Ti, j$ es hacerlo más pequeño; en particular, no puede llegar a ser mayor que sus vecinos de derecha 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 terminar el paso 2. Finalmente $,$ para ver que el nuevo valor es mayor que su vecino superior $Ti -1, j$ si está presente, observe que $Ti -1, j$ se cumple después del paso 5, y que disminuir $j$ en el paso 2 solo disminuye el valor correspondiente $Ti - 1, j$ .

Construyendo los cuadros

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

Establezca tanto $P$ como $Q$ en el cuadro vacío
Para $i$ aumentando de $1$ an $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$ 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 observar que dado cualquier par $(P, Q)$ de cuadros estándar de Young de la misma forma, existe un procedimiento inverso que produce una permutación que dará lugar a $(P, Q)$ mediante el algoritmo de Schensted. Básicamente consiste en rastrear los pasos del algoritmo hacia atrás, usando cada vez 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 estándar de Young de igual forma y que contienen $n$ cuadrados en el otro lado.

Propiedades

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

Si la correspondencia Robinson-Schensted asocia cuadros $(P, Q)$ a una permutación $σ$ , entonces asocia $(Q, P)$ a la permutación inversa $σ -1$ .

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

Propiedades adicionales, 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 invertida $(σ n, ..., σ 1)$ , el cuadro $P'$ es la transpuesta del cuadro $P$ , y $Q'$ es un cuadro determinado por $Q$ , independientemente de $P$ (es decir, la transpuesta 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 desprende de las dos propiedades anteriores.
El conjunto descendente ${i : σ i > σ i +1$ } de $σ$ es igual al conjunto descendente ${i : i +1 está en una fila estrictamente debajo de la fila de i$ } de $Q$ .
Identificar subsecuencias 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$ subsecuencias crecientes es $λ 1 + ... + λ k$ . En particular, $λ 1$ es igual a la longitud más grande 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 $λ$ .

Aplicaciones

Aplicación al teorema de Erdős-Szekeres

La correspondencia Robinson-Schensted se puede utilizar para dar una demostración sencilla del teorema de Erdős-Szekeres .

Ver también

La construcción geométrica de Viennot , que proporciona una interpretación esquemática de la correspondencia.
Monoide plástico : 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 monoide plástico 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 estudiantiles de la London Mathematical Society, vol. 35, Prensa de la Universidad de Cambridge , 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, 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, Estudios de Cambridge en Matemáticas Avanzadas, vol. 62, Prensa de la Universidad de Cambridge , ISBN 978-0-521-56069-6, señor 1676282.
Zelevinsky, AV (1981), "Una generalización de la regla de Littlewood-Richardson y la correspondencia Robinson-Schensted-Knuth", Journal of Algebra , 69 (1): 82–94, doi : 10.1016/0021-8693(81)90128 -9 , señor 0613858.

Otras lecturas

Verde, James A. (2007). Representaciones polinómicas de GL _n . Apuntes de conferencias de matemáticas. vol. 830. Con un apéndice sobre la correspondencia de Schensted y los caminos de Littelmann por K. Erdmann, JA Green y M. Schocker (segunda 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.