En matemáticas, la construcción geométrica de Viennot (que lleva el nombre de Xavier Gérard Viennot) ofrece una interpretación esquemática de la correspondencia Robinson-Schensted en términos de líneas de sombra . Tiene una generalización a la correspondencia Robinson-Schensted-Knuth , que se conoce como construcción matriz-bola .
Comenzando con una permutación , escrita en notación de dos líneas , digamos:
se puede aplicar la correspondencia de Robinson-Schensted a esta permutación, obteniendo dos cuadros estándar de Young de la misma forma, P y Q. P se obtiene realizando una secuencia de inserciones y Q es el cuadro de registro, que indica en qué orden se llenaron las casillas.
La construcción de Viennot comienza trazando los puntos en el plano e imaginando que hay una luz que brilla desde el origen, proyectando sombras hacia arriba y hacia la derecha. Esto permite considerar los puntos que no están sombreados por ningún otro punto; el límite de sus sombras forma entonces la primera línea de sombra. Eliminando estos puntos y repitiendo el procedimiento, se obtienen todas las líneas de sombra para esta permutación. La idea de Viennot es entonces que estas líneas de sombra leen las primeras filas de P y Q (de hecho, incluso más que eso; estas líneas de sombra forman una "línea de tiempo", que indica qué elementos formaron las primeras filas de P y Q después de las sucesivas inserciones). ). Luego se puede repetir la construcción, utilizando como nuevos puntos las esquinas anteriores sin etiquetar , lo que permite leer las otras filas de P y Q.
Por ejemplo, considere la permutación
Entonces la construcción de Viennot es la siguiente:
Se puede utilizar la construcción geométrica de Viennot para demostrar que si corresponde al par de cuadros P , Q bajo la correspondencia Robinson-Schensted, entonces corresponde al par conmutado Q , P. De hecho, tomar a refleja la construcción de Viennot en el eje -, y esto precisamente cambia los roles de P y Q.
