En el campo matemático de la combinatoria , jeu de taquin es una construcción de Marcel-Paul Schützenberger ( 1977 ) que define una relación de equivalencia en el conjunto de cuadros de Young estándar de sesgo . Una diapositiva de jeu de taquin es una transformación en la que los números de un cuadro se mueven de forma similar a como se mueven las piezas del rompecabezas de quince . Dos tableaux son jeu de taquin equivalentes si uno puede transformarse en el otro a través de una secuencia de tales diapositivas.
"Jeu de taquin" (literalmente "juego de bromas") es el nombre francés del rompecabezas de los quince .
Definición de un tobogán jeu de taquin
Dado un cuadro de Young estándar de sesgo T de forma sesgada, elija una celda vacía adyacente c que se pueda agregar al diagrama de sesgo; lo que esto significa es que c debe compartir al menos un borde con alguna celda en T , ytambién debe ser un diagrama de sesgo. Hay dos tipos de diapositivas, dependiendo de si c se encuentra en la parte superior izquierda de T o en la parte inferior derecha. Supongamos que, para empezar, c se encuentra en la esquina superior izquierda. Deslice el número de su celda vecina a c ; si c tiene vecinos tanto a su derecha como abajo, elija el más pequeño de estos dos números. (Esta regla está diseñada para preservar la propiedad del cuadro de tener filas y columnas crecientes). Si la celda que acaba de vaciarse no tiene un vecino a su derecha o abajo, entonces la diapositiva está completa. De lo contrario, deslice un número en esa celda de acuerdo con la misma regla que antes, y continúe de esta manera hasta que se complete la diapositiva. Después de esta transformación, el cuadro resultante (con la celda ahora vacía eliminada) sigue siendo un cuadro de Young estándar sesgado (o posiblemente recto).
El otro tipo de diapositiva, cuando c se encuentra en la parte inferior derecha de T , simplemente va en la dirección opuesta. En este caso, uno desliza números en una celda vacía desde el vecino a su izquierda o arriba, eligiendo el número más grande siempre que haya una opción. Los dos tipos de diapositivas son inversas mutuas: una diapositiva de un tipo se puede deshacer con una diapositiva del otro tipo.
Los dos portaobjetos descritos anteriormente se denominan portaobjetos en la celda c . Se dice que el primer tipo de deslizamiento (cuando c se encuentra en la parte superior izquierda de T ) es un deslizamiento hacia adentro ; el segundo tipo se conoce como deslizamiento hacia afuera .
La palabra "slide" es sinónimo de la palabra francesa "glissement", que ocasionalmente también se usa en la literatura inglesa.
Sutilezas
Las diapositivas de Jeu-de-taquin cambian no solo el orden relativo de las entradas de un cuadro, sino también su forma. En la definición dada arriba, el resultado de una diapositiva jeu-de-taquin se da como un diagrama de sesgo junto con un cuadro estándar de sesgo que lo tiene como forma. A menudo, es mejor trabajar con formas sesgadas en lugar de diagramas sesgados. (Recuerde que cada forma sesgada da lugar a un diagrama de sesgo , pero esto no es una correspondencia inyectiva porque, por ejemplo, las distintas formas sesgadas y producir el mismo diagrama de sesgo.) Por esta razón, es útil modificar la definición anterior de una diapositiva jeu-de-taquin de tal manera que, cuando se le da una forma sesgada junto con un cuadro estándar sesgado y una celda que se puede agregar como un entrada, produce una forma de sesgo bien definida junto con un cuadro estándar de sesgo en su salida. Esto se hace de la siguiente manera: Una diapositiva hacia adentro de un cuadro sesgado T de forma sesgadaen una celda c se define como arriba cuando c es una esquina de (Eso es cuando es un diagrama de Young), y la forma de sesgo resultante se establece para ser donde d es la celda vacía al final del procedimiento de deslizamiento. Una diapositiva hacia afuera de un cuadro sesgado T de forma sesgadaen una celda c se define como arriba cuando c es una esquina de (Eso es cuando es un diagrama de Young), y la forma de sesgo resultante se establece para ser donde d es la celda vacía al final del procedimiento de deslizamiento.
Generalización para sesgar cuadros semiestándar
Las diapositivas Jeu de taquin se generalizan para sesgar cuadros semiestándar (a diferencia de sesgar estándar) y conservan la mayoría de sus propiedades en esa generalidad. El único cambio que se debe hacer a la definición de una diapositiva hacia adentro, para que se generalice, es una regla sobre cómo proceder cuando la celda (temporalmente) vacía tiene vecinos abajo y a su derecha, y estos vecinos están llenos con números iguales. En esta situación, el vecino de abajo (no el de la derecha) debe deslizarse en la celda vacía. Se necesita un cambio similar en la definición de un deslizamiento hacia afuera (donde uno tiene que elegir el vecino de arriba). Estos cambios pueden parecer arbitrarios, pero en realidad hacen las "únicas elecciones razonables", es decir, las únicas opciones que mantienen las columnas del cuadro (sin tener en cuenta la celda vacía) estrictamente aumentando (en lugar de simplemente aumentar débilmente).
Rectificación
Dado un cuadro sesgado estándar o sesgado semiestándar T , se pueden aplicar repetidamente diapositivas hacia adentro a T hasta que el cuadro se convierta en una forma recta (lo que significa que no son posibles más diapositivas hacia adentro). Esto generalmente se puede hacer de muchas maneras diferentes (uno puede elegir libremente en qué celda deslizarse primero), pero se sabe que el cuadro de forma recta resultante es el mismo para todas las opciones posibles. Este cuadro se llama la rectificación de la T .
Equivalencia Jeu-de-taquin
Se dice que dos cuadros semiestándar sesgados T y S son equivalentes jeu-de-taquin si uno puede transformar uno de ellos en el otro usando una secuencia (posiblemente vacía) de diapositivas (se permiten diapositivas tanto hacia adentro como hacia afuera). De manera equivalente, dos cuadros semiestándar sesgados T y S son jeu-de-taquin equivalentes si y solo si tienen la misma rectificación.
Lectura de palabras y equivalencia de Knuth
Hay varias formas de asociar una palabra (en el sentido de combinatoria, es decir, una secuencia finita de elementos de un alfabeto, aquí el conjunto de enteros positivos) a cada cuadro de Young. Elegimos el aparentemente más popular: asociamos a cada cuadro de Young T la palabra obtenida al concatenar las filas de T de la fila inferior a la fila superior. (Cada fila de T se ve como una palabra simplemente leyendo sus entradas de izquierda a derecha, y dibujamos cuadros de Young en notación inglesa para que la fila más larga de un cuadro de forma recta aparezca en la parte superior). Esta palabra se denominará como la lectura de palabras , o brevemente como la palabra , del T .
Entonces se puede demostrar que dos cuadros semiestándar sesgados T y S son jeu-de-taquin equivalentes si y solo si las palabras de lectura de T y S son equivalentes en Knuth . Como consecuencia, la rectificación de un cuadro semiestándar T sesgado también se puede obtener como el cuadro de inserción de la palabra de lectura de T bajo la correspondencia Robinson-Schensted .
La involución de Schützenberger
Jeu de taquin se puede utilizar para definir una operación en tableaux estándar de Young de cualquier forma dada, que resulta ser una involución , aunque esto no es obvio a partir de la definición. Uno comienza vaciando el cuadrado en la esquina superior izquierda, convirtiendo el cuadro en un cuadro sesgado con un cuadro menos. Ahora aplique un tobogán jeu de taquin para convertir ese cuadro sesgado en uno recto, lo que liberará un cuadrado en el borde exterior. Luego llene este cuadrado con el valor negativo que se eliminó originalmente en la esquina superior izquierda; este valor negado se considera parte de un nuevo cuadro y no del cuadro original, y su posición no cambiará en la secuela. Ahora, siempre que al cuadro original le queden algunas entradas, repita la operación de eliminar la entrada x de la esquina superior izquierda, realizando un deslizamiento jeu de taquin en lo que queda del cuadro original y colocando el valor - x en el cuadrado tan liberado. Cuando se han manejado todas las entradas del cuadro original, sus valores negados se organizan de tal manera que las filas y columnas aumentan. Finalmente, se puede agregar una constante apropiada a todas las entradas para obtener un cuadro de Young con entradas positivas.
Aplicaciones
Jeu de taquin está estrechamente relacionado con temas como la correspondencia Robinson-Schensted-Knuth , la regla Littlewood-Richardson y la equivalencia Knuth .
Referencias
- Désarménien, J. (2001) [1994], "Jeu de taquin" , Enciclopedia de Matemáticas , EMS Press
- Sagan, Bruce E. (2001), The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , Textos de posgrado en matemáticas 203 (2a ed.), Nueva York: Springer, ISBN 0-387-95067-2
- Fulton, William (1997), Young Tableaux , London Mathematical Society Student Texts 35 (1a ed.), Melbourne: Cambridge University Press, ISBN 0-521-56144-2
- Haiman, MD (1992). "Doble equivalencia con aplicaciones, incluida una conjetura de Proctor". Matemáticas discretas . 99 : 79-113. doi : 10.1016 / 0012-365X (92) 90368-P .
- Schützenberger, Marcel-Paul (1977), "La correspondance de Robinson", en Foata, Dominique (ed.), Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Estrasburgo, Estrasburgo, 1976) , Conferencia Notes in Math., 579 , Berlín: Springer, págs. 59-113 , doi : 10.1007 / BFb0090012 , ISBN 978-3-540-08143-2
- Stanley, Richard P. (1999), Combinatoria enumerativa , Cambridge Studies in Advanced Mathematics 62, 2 , Cambridge University Press, ISBN 0-521-56069-1