En el campo matemático de la combinatoria , jeu de taquin es una construcción debida a Marcel-Paul Schützenberger (1977) que define una relación de equivalencia en el conjunto de tablas de Young estándar sesgadas . Un deslizamiento de jeu de taquin es una transformación en la que los números en una tabla se mueven de manera similar a cómo se mueven las piezas en el rompecabezas de quince . Dos tablas son jeu de taquin equivalentes si una puede transformarse en la otra mediante una secuencia de tales deslizamientos.
"Jeu de taquin" (literalmente "juego de burla") es el nombre en francés del rompecabezas del quince.
Dado un diagrama de Young estándar T de forma oblicua , elija una celda vacía adyacente c que pueda agregarse al diagrama de oblicuidad ; esto significa que c debe compartir al menos un borde con alguna celda en T y también debe ser un diagrama de oblicuidad. Hay dos tipos de deslizamiento, 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 parte superior izquierda. Deslice el número desde su celda vecina hacia c ; si c tiene vecinos tanto a su derecha como debajo, elija el más pequeño de estos dos números, favoreciendo al que está debajo. (Esta regla está diseñada para que se conserve la propiedad del diagrama de tener filas y columnas crecientes). Si la celda que acaba de vaciarse no tiene vecina a su derecha o debajo, entonces el deslizamiento está completo. De lo contrario, deslice un número hacia esa celda de acuerdo con la misma regla que antes y continúe de esta manera hasta que se complete el deslizamiento. Después de esta transformación, la tabla resultante (con la celda ahora vacía eliminada) sigue siendo una tabla de Young estándar sesgada (o posiblemente recta).
El otro tipo de deslizamiento, cuando c se encuentra en la esquina inferior derecha de T , simplemente va en la dirección opuesta. En este caso, se deslizan números a una celda vacía desde la celda vecina a su izquierda o superior, eligiendo el número más grande siempre que haya una opción. Los dos tipos de deslizamiento son inversos entre sí: un deslizamiento de un tipo se puede deshacer utilizando un deslizamiento del otro tipo.
Los dos deslizamientos descritos anteriormente se denominan deslizamientos hacia el interior de la celda c . El primer tipo de deslizamiento (cuando c se encuentra en la esquina superior izquierda de T ) se denomina deslizamiento hacia el interior ; el segundo tipo se denomina deslizamiento hacia el exterior .
La palabra "slide" es sinónimo de la palabra francesa "glissement", que ocasionalmente también se utiliza en la literatura inglesa.
Las diapositivas de Jeu-de-taquin cambian no solo el orden relativo de las entradas de una tabla, sino también su forma. En la definición dada anteriormente, el resultado de una diapositiva de jeu-de-taquin se da como un diagrama de sesgo junto con una tabla estándar de sesgo que lo tiene como forma. A menudo, es mejor trabajar con formas de sesgo en lugar de diagramas de sesgo. (Recuerde que cada forma de sesgo da lugar a un diagrama de sesgo , pero esta no es una correspondencia inyectiva porque, por ejemplo, las distintas formas de sesgo y producen el mismo diagrama de sesgo). Por esta razón, es útil modificar la definición anterior de una diapositiva de jeu-de-taquin de tal manera que, cuando se da una forma de sesgo junto con una tabla estándar de sesgo y una celda agregable como entrada, produce una forma de sesgo bien definida junto con una tabla estándar de sesgo en su salida. Esto se hace de la siguiente manera: un deslizamiento hacia adentro de una tabla oblicua T de forma oblicua en una celda c se define como se indicó anteriormente cuando c es una esquina de (es decir, cuando es un diagrama de Young), y la forma oblicua resultante se establece en donde d es la celda vacía al final del procedimiento de deslizamiento. Un deslizamiento hacia afuera de una tabla oblicua T de forma oblicua en una celda c se define como se indicó anteriormente cuando c es una esquina de (es decir, cuando es un diagrama de Young), y la forma oblicua resultante se establece en donde d es la celda vacía al final del procedimiento de deslizamiento.
Los deslizamientos de Jeu de taquin se generalizan a tablas semiestándar sesgadas (en oposición a tablas estándar sesgadas) y conservan la mayoría de sus propiedades en esa generalidad. El único cambio que debe realizarse en la definición de un deslizamiento hacia adentro, para que se generalice, es una regla sobre cómo proceder cuando la celda (temporalmente) vacía tiene vecinas debajo y a su derecha, y estas vecinas están llenas con cantidades iguales. En esta situación, la vecina de abajo (no la de la derecha) debe deslizarse hacia la celda vacía. Se necesita un cambio similar en la definición de un deslizamiento hacia afuera (donde uno debe elegir la vecina de arriba). Estos cambios pueden parecer arbitrarios, pero en realidad hacen que las "únicas opciones razonables", es decir, las únicas opciones que mantienen las columnas de la tabla (sin tener en cuenta la celda vacía) estrictamente crecientes (en oposición a solo un aumento débil).
Dada una tabla estándar oblicua o semiestándar T , se pueden aplicar iterativamente deslizamientos hacia adentro a T hasta que la tabla adquiera forma recta (lo que significa que no son posibles más deslizamientos hacia adentro). Esto generalmente se puede hacer de muchas maneras diferentes (se puede elegir libremente en qué celda deslizarse primero), pero se sabe que la tabla de forma recta resultante es la misma para todas las opciones posibles. Esta tabla se llama rectificación de T .
Se dice que dos tablas semiestándar oblicuas T y S son equivalentes en un juego de mesa si se puede transformar una de ellas en la otra utilizando una secuencia (posiblemente vacía) de diapositivas (se permiten diapositivas tanto internas como externas). De manera equivalente, dos tablas semiestándar oblicuas T y S son equivalentes en un juego de mesa si y solo si tienen la misma rectificación.
Existen varias maneras de asociar una palabra (en el sentido de la combinatoria, es decir, una secuencia finita de elementos de un alfabeto, en este caso el conjunto de números enteros positivos) a cada tabla de Young. Elegimos la que parece más popular: asociamos a cada tabla de Young T la palabra obtenida concatenando las filas de T desde la fila inferior hasta la fila superior. (Cada fila de T se ve como una palabra simplemente leyendo sus entradas de izquierda a derecha, y dibujamos tablas de Young en notación inglesa de modo que la fila más larga de una tabla de forma recta aparezca en la parte superior). Esta palabra se denominará la palabra de lectura , o brevemente, la palabra , de T .
Se puede demostrar entonces que dos tablas semiestándar oblicuas T y S son equivalentes en el juego de tablas si y solo si las palabras de lectura de T y S son equivalentes en el juego de tablas Knuth . En consecuencia, la rectificación de una tabla semiestándar oblicua T también se puede obtener como la tabla de inserción de la palabra de lectura de T según la correspondencia Robinson-Schensted .
Jeu de taquin se puede utilizar para definir una operación sobre tablas de Young estándar 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 la tabla en una tabla oblicua con un cuadrado menos. Ahora aplique un deslizamiento de jeu de taquin para convertir esa tabla oblicua en una recta, 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 una nueva tabla en lugar de la tabla original, y su posición no cambiará en la secuela. Ahora, mientras la tabla original tenga algunas entradas restantes, repita la operación de eliminar la entrada x de la esquina superior izquierda, realizando un deslizamiento de jeu de taquin en lo que queda de la tabla original y colocando el valor − x en el cuadrado así liberado. Cuando se han procesado todas las entradas de la tabla original, sus valores negados se organizan de forma que las filas y las columnas sean crecientes. Finalmente, se puede agregar una constante adecuada a todas las entradas para obtener una tabla de Young con entradas positivas.
El juego de mesa está estrechamente relacionado con temas como la correspondencia Robinson-Schensted-Knuth , la regla de Littlewood-Richardson y la equivalencia de Knuth .
