En matemáticas, el monoide plástico es el monoide de todas las palabras del alfabeto de enteros positivos módulo de equivalencia de Knuth . Sus elementos se pueden identificar con cuadros de Young semiestándar . Fue descubierto por Donald Knuth ( 1970 ) (quien lo llamó álgebra del cuadro ), usando una operación dada por Craige Schensted ( 1961 ) en su estudio de la subsecuencia creciente más larga de una permutación.
Fue nombrado " monoïde plaxique " por Lascoux & Schützenberger (1981) , quienes permitieron cualquier alfabeto totalmente ordenado en la definición. La etimología de la palabra " plaxique " no está clara; puede referirse a la tectónica de placas ("tectonique des plaques" en francés), ya que las relaciones elementales que generan la equivalencia permiten la conmutación condicional de los símbolos generadores: a veces pueden deslizarse entre sí (en aparente analogía con las placas tectónicas), pero no libremente.
Definición
El monoide plástico sobre algún alfabeto totalmente ordenado (a menudo los enteros positivos) es el monoide con la siguiente presentación :
- Los generadores son las letras del alfabeto.
- Las relaciones son la elemental Knuth transformaciones YZX ≡ yxz siempre que x < y ≤ z y xzy ≡ ZXY siempre que x ≤ y < z .
Equivalencia de Knuth
Dos palabras se denominan equivalentes de Knuth si representan el mismo elemento del monoide plástico o, en otras palabras, si una puede obtenerse de la otra mediante una secuencia de transformaciones elementales de Knuth.
Varias propiedades se conservan mediante la equivalencia de Knuth.
- Si una palabra es una palabra reticular inversa , entonces también lo es cualquier palabra que Knuth le corresponda.
- Si dos palabras son equivalentes de Knuth, entonces también lo son las palabras obtenidas al eliminar sus elementos máximos más a la derecha, al igual que las palabras obtenidas al eliminar sus elementos mínimos más a la izquierda.
- La equivalencia de Knuth conserva la longitud de la subsecuencia no decreciente más larga y, de manera más general, conserva el máximo de la suma de las longitudes de k subsecuencias no decrecientes disjuntas para cualquier k fija .
Correspondencia con cuadros jóvenes semiestándar
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/4/44/Young-Schensted.png/180px-Young-Schensted.png)
• Usando las relaciones plásticas, (1257) * 4 = 5 * (1247)
• (38) * 5 = 8 * ( 35), por lo que (5) reemplaza (8) en la segunda fila
• (8) crea la tercera fila
• El producto tiene entonces la forma de cuadro (8) (35) (1247)
Cada palabra es Knuth equivalente a la palabra de un cuadro de Young semiestándar único (esto significa que cada fila no es decreciente y cada columna es estrictamente creciente) sobre el mismo alfabeto ordenado, donde el cuadro se puede leer por filas o por columnas. Por lo tanto, los elementos del monoide plástico se pueden identificar con los cuadros de Young semiestándar, que por lo tanto también forman un monoide.
Multiplicar la palabra de un cuadro de Young semiestándar a la izquierda con un generador es equivalente a la inserción de Schensted en el cuadro de Young. En orden de filas, la palabra del cuadro es equivalente a un producto de secuencias de generadores cada vez más largas y no decrecientes. El nuevo generador puede insertarse en su lugar apropiado, ya sea agregándolo si es más grande, y de lo contrario, aplicando repetidamente las relaciones plásticas para mover el elemento fuera de secuencia a la siguiente fila. En el último caso, el elemento desordenado reemplaza la entrada más a la izquierda más grande que ella en cada fila, y el elemento desplazado se inserta en la siguiente fila.
Dado que la inserción de Schensted conserva los cuadros de Young, esto proporciona una prueba inductiva de que los elementos del monoide plástico se pueden escribir en una forma estándar correspondiente a un cuadro de Young, y la construcción define un producto natural de cuadros semiestándar.
Jeu de Taquin
Dos Young Tableaux sesgados son equivalentes a Jeu de taquin si y solo si sus lecturas de palabras son equivalentes a Knuth, es decir, corresponden a elementos equivalentes del grupo plástico. Esto proporciona una definición alternativa del producto del grupo plástico directamente en términos de cuadros de Young. Se pueden multiplicar dos cuadros dibujándolos alrededor de un rectángulo vacío para formar un cuadro sesgado y usando diapositivas Jeu de taquin para rectificarlo.
Anillo de cuadro
El anillo del cuadro es el anillo monoide del monoide plástico, por lo que tiene una base Z que consta de elementos del monoide plástico, con el mismo producto que en el monoide plástico.
Hay un homomorfismo desde el anillo plástico de un alfabeto hasta el anillo de polinomios (con variables indexadas por el alfabeto) que lleva cualquier cuadro al producto de las variables de sus entradas.
Crecimiento
La función generadora del monoide plástico en un alfabeto de tamaño n es
mostrando que hay un crecimiento polinomial de dimensión .
Ver también
Referencias
- Duchamp, Gérard; Krob, Daniel (1994), "Monoides semejantes al crecimiento plástico" , Palabras, lenguajes y combinatoria, II (Kyoto, 1992) , World Sci. Publ., River Edge, Nueva Jersey, págs. 124-142, MR 1351284 , Zbl 0875.68720
- Fulton, William (1997), Young tableaux , London Mathematical Society Student Texts, 35 , Cambridge University Press , ISBN 978-0-521-56144-0, MR 1464693 , Zbl 0.878,14034
- Knuth, Donald E. (1970), "Permutaciones, matrices y cuadros de Young generalizados" , Pacific Journal of Mathematics , 34 (3): 709–727, doi : 10.2140 / pjm.1970.34.709 , ISSN 0030-8730 , MR 0272654
- Lascoux, Alain; Leclerc, B .; Thibon, JY., "The Plactic Monoid" , archivado desde el original el 18 de julio de 2011 Falta o vacío
|title=
( ayuda ) - Littelmann, Peter (1996), "Un álgebra plástica para álgebras de Lie semisimple" , Advances in Mathematics , 124 (2): 312–331, doi : 10.1006 / aima.1996.0085 , ISSN 0001-8708 , MR 1424313
- Lascoux, Alain; Schützenberger, Marcel-P. (1981), "Le monoïde plaxique" (PDF) , Estructuras no conmutativas en álgebra y combinatoria geométrica (Nápoles, 1978) , Quaderni de La Ricerca Scientifica, 109 , Roma: CNR, págs. 129-156, MR 0646486
- Lothaire, M. (2011), Combinatoria algebraica en palabras , Enciclopedia de las matemáticas y sus aplicaciones, 90 , Con prefacio de Jean Berstel y Dominique Perrin (Reimpresión de la edición de tapa dura de 2002), Cambridge University Press, ISBN 978-0-521-18071-9, Zbl 1221.68183
- Schensted, C. (1961), "Las subsecuencias crecientes y decrecientes más largas" , Canadian Journal of Mathematics , 13 : 179-191, doi : 10.4153 / CJM-1961-015-3 , ISSN 0008-414X , MR 0121305
- Schützenberger, Marcel-Paul (1997), "Pour le monoïde plaxique" , Mathématiques, Informatique et Sciences Humaines (140): 5–10, ISSN 0995-2314 , MR 1627563
Otras lecturas
- Green, James A. (2007), Representaciones polinómicas de GL n , Lecture Notes in Mathematics, 830 , Con un apéndice sobre correspondencia de Schensted y trayectorias de Littelmann por K. Erdmann, JA Green y M. Schocker (segunda edición corregida y aumentada). , Berlín: Springer-Verlag , ISBN 978-3-540-46944-5, Zbl 1108.20044