En el campo matemático de la combinatoria , el juego de taquin es una construcción debida a Marcel-Paul Schützenberger (1977) que define una relación de equivalencia en el conjunto de cuadros estándar sesgados de Young . Un tobogán 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 cuadros son equivalentes a un juego de taquin si uno puede transformarse en el otro mediante una secuencia de tales diapositivas.
"Jeu de taquin" (literalmente "juego de burlas") es el nombre francés del rompecabezas de quince.
Dado un cuadro de Young estándar sesgado T de forma sesgada , seleccione una celda vacía adyacente c que se pueda agregar al diagrama sesgado ; lo que esto significa es que c debe compartir al menos un borde con alguna celda en T y también debe ser un diagrama sesgado. 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 para empezar que c se encuentra en la parte superior izquierda. Deslice el número de su celda vecina a c ; Si c tiene vecinos a su derecha y debajo, entonces elija el menor de estos dos números, favoreciendo el de abajo. (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 ningún vecino a su derecha o debajo, entonces la diapositiva está completa. De lo contrario, deslice un número en esa celda siguiendo la misma regla que antes y continúe de esta manera hasta completar la diapositiva. Después de esta transformación, el cuadro resultante (con la celda ahora vacía eliminada) sigue siendo un cuadro estándar de Young 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, se deslizan números en una celda vacía desde el vecino a su izquierda o arriba, eligiendo el número mayor siempre que haya una opción. Los dos tipos de diapositivas son inversas mutuas: una diapositiva de un tipo se puede deshacer usando una diapositiva del otro tipo.
Los dos portaobjetos descritos anteriormente se denominan portaobjetos dentro de la celda c . El primer tipo de deslizamiento (cuando c se encuentra en la parte superior izquierda de T ) se dice que 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 utiliza en la literatura inglesa.
Las diapositivas del Jeu-de-taquin cambian no sólo el orden relativo de las entradas de un cuadro, sino también su forma. En la definición dada anteriormente, el resultado de una diapositiva de jeu-de-taquin se presenta como un diagrama sesgado junto con un cuadro estándar sesgado que lo tiene como forma. A menudo, es mejor trabajar con formas sesgadas que con diagramas sesgados. (Recuerde que cada forma sesgada da lugar a un diagrama sesgado , pero esto no es una correspondencia inyectiva porque, por ejemplo, las distintas formas sesgadas producen el mismo diagrama sesgado). Por esta razón, es útil modificar la definición anterior de jeu-de-taquin se desliza de tal manera que, cuando se le da una forma sesgada junto con un cuadro estándar sesgado y una celda agregable como entrada, produce una forma sesgada bien definida junto con un cuadro estándar sesgado en su salida. Esto se hace de la siguiente manera: un deslizamiento hacia adentro de un cuadro sesgado T con forma sesgada hacia una celda c se define como arriba cuando c es una esquina de (es decir, cuando es un diagrama de Young), y la forma sesgada resultante se establece en ser donde d es la celda vacía al final del procedimiento de deslizamiento. Un deslizamiento hacia afuera de un cuadro sesgado T de forma sesgada hacia una celda c se define como arriba cuando c es una coesquina de (es decir, cuando es un diagrama de Young), y la forma sesgada resultante se establece donde d es el vacío celda al final del procedimiento de deslizamiento.
Las diapositivas de 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 diapositiva hacia adentro, para que se pueda generalizar, es una regla sobre cómo proceder cuando la celda (temporalmente) vacía tiene vecinos debajo 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 hacia la celda vacía. Se necesita un cambio similar en la definición de tobogán exterior (donde hay que elegir el vecino de arriba). Estos cambios pueden parecer arbitrarios, pero en realidad toman las "únicas opciones razonables", es decir, las únicas opciones que mantienen las columnas del cuadro (sin tener en cuenta la celda vacía) estrictamente en aumento (en lugar de aumentar sólo débilmente).
Dado un cuadro estándar sesgado o semiestándar sesgado T , se pueden aplicar iterativamente deslizamientos hacia adentro a T hasta que el cuadro adquiera una forma recta (lo que significa que no son posibles más deslizamientos hacia adentro). Por lo general, esto 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 rectificación de T .
Se dice que dos cuadros semiestándar sesgados T y S son equivalentes a 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 equivalentes en jeu-de-taquin si y sólo si tienen la misma rectificación.
Hay varias maneras de asociar una palabra (en el sentido de combinatoria, es decir, una secuencia finita de elementos de un alfabeto, en este caso el conjunto de números enteros positivos) a cada cuadro de Young. Elegimos el que aparentemente es más popular: asociamos a cada cuadro de Young T la palabra obtenida concatenando las filas de T desde la fila inferior a la 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 de modo que la fila más larga de un cuadro de forma recta aparezca en la parte superior). como la palabra de lectura , o brevemente como la palabra , de T.
Entonces se puede demostrar que dos cuadros semiestándar sesgados T y S son equivalentes en jeu-de-taquin si y sólo si las palabras de lectura de T y S son equivalentes de Knuth . Como consecuencia, la rectificación de un cuadro semiestándar sesgado T también se puede obtener como el cuadro de inserción de la palabra de lectura de T bajo la correspondencia Robinson-Schensted .
Jeu de taquin se puede utilizar para definir una operación en cuadros 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. Se comienza vaciando el cuadrado en la esquina superior izquierda, convirtiendo el cuadro en un cuadro sesgado con un cuadrado menos. Ahora aplica un juego de taquin deslizante para convertir ese cuadro sesgado en uno recto, lo que liberará un cuadrado en el borde exterior. Luego rellene este cuadrado con el negativo del valor que se eliminó originalmente en la esquina superior izquierda; este valor negado se considera parte de un nuevo cuadro en lugar del cuadro original, y su posición no cambiará en la secuela. Ahora, mientras al cuadro original le queden algunas entradas, repita la operación de eliminar la entrada x de la esquina superior izquierda, realizando un juego de taquin deslizando lo que queda del cuadro original y colocando el valor − x en el plaza así liberada. 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.
Jeu de taquin está estrechamente relacionado con temas como la correspondencia Robinson-Schensted-Knuth , la regla de Littlewood-Richardson y la equivalencia de Knuth .
