Monoide plástico

En matemáticas, el monoide pláctico es el monoide de todas las palabras del alfabeto de números enteros positivos módulo equivalencia de Knuth . Sus elementos pueden identificarse con tablas de Young semiestándar . Fue descubierto por Donald Knuth  (1970) (quien lo llamó álgebra de tablas ), utilizando una operación dada por Craige Schensted  (1961) en su estudio de la subsecuencia creciente más larga de una permutación.

Lascoux y Schützenberger (1981) la denominaron " monoïde plaxique ", y admitieron en su definición cualquier alfabeto totalmente ordenado. 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 unos sobre otros (en aparente analogía con las placas tectónicas), pero no libremente.

El monoide plástico sobre algún alfabeto totalmente ordenado (a menudo los números enteros positivos) es el monoide con la siguiente presentación :

• Los generadores son las letras del alfabeto.
• Las relaciones son las transformaciones elementales de Knuth yzx  ≡  yxz siempre que x  <  y  ≤  z y xzy  ≡  zxy siempre que x  ≤  y  <  z .

Dos palabras se denominan equivalentes de Knuth si representan el mismo elemento del monoide plásmico, o en otras palabras, si una puede obtenerse de la otra mediante una secuencia de transformaciones elementales de Knuth.

La equivalencia de Knuth conserva varias propiedades.

• Si una palabra es una palabra de red inversa , entonces también lo es cualquier palabra Knuth equivalente a ella.
• Si dos palabras son equivalentes en el sentido de Knuth, entonces también lo son las palabras obtenidas al eliminar sus elementos máximos más a la derecha, así como las palabras obtenidas al eliminar sus elementos mínimos más a la izquierda.
• La equivalencia de Knuth preserva la longitud de la subsecuencia no decreciente más larga y, de manera más general, preserva el máximo de la suma de las longitudes de k subsecuencias no decrecientes disjuntas para cualquier k fijo .

Cada palabra es equivalente de Knuth 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 puede leerse por filas o por columnas. De modo que los elementos del monoide pláctico pueden identificarse con los cuadros de Young semiestándar, que por lo tanto también forman un monoide.

Multiplicar la palabra de una tabla de Young semiestándar hacia la izquierda por un generador es equivalente a la inserción de Schensted en la tabla de Young. En orden de filas, la palabra de la tabla es equivalente a un producto de secuencias de generadores no decrecientes cada vez más largas. El nuevo generador puede insertarse en su lugar apropiado ya sea agregándolo si es más grande o, en caso contrario, aplicando repetidamente las relaciones plácticas para mover el elemento fuera de secuencia a la siguiente fila. En el último caso, el elemento fuera de orden reemplaza la entrada más a la izquierda que es más grande que él en cada fila y, luego, el elemento desplazado se inserta en la siguiente fila.

Dado que la inserción de Schensted preserva las tablas de Young, esto proporciona una prueba inductiva de que los elementos del monoide pláctico pueden escribirse en una forma estándar correspondiente a una tabla de Young, y la construcción define un producto natural de tablas semiestándar.

Dos cuadros de Young sesgados son equivalentes en Jeu de taquin si y solo si sus lecturas de palabras son equivalentes en Knuth, es decir, corresponden a elementos equivalentes del grupo pláctico. Esto da una definición alternativa del producto del grupo pláctico 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 utilizando diapositivas de Jeu de taquin para rectificarlo.

El anillo de tabla es el anillo monoide del monoide pláctico, por lo que tiene una base Z que consiste en elementos del monoide pláctico, con el mismo producto que en el monoide pláctico.

Existe un homomorfismo del anillo pláctico de un alfabeto al anillo de polinomios (con variables indexadas por el alfabeto) tomando cualquier tabla como producto de las variables de sus entradas, correspondiente a la abelianización del semigrupo pláctico.

La función generadora del monoide plástico sobre un alfabeto de tamaño n es

${\displaystyle \Gamma(t)={\frac {1}{(1-t)^{n}}}{\frac {1}{(1-t^{2})^{n(n-1)/2}}}\ }$

mostrando que hay crecimiento polinomial de dimensión . ${\displaystyle {\frac {n(n+1)}{2}}}$

• Monoide chino
• Correspondencia Robinson-Schensted
• Juego de taquin

• Duchamp, Gérard; Krob, Daniel (1994), "Monoides de crecimiento plástico", Palabras, lenguajes y combinatoria, II (Kyoto, 1992) , World Sci. Publ., River Edge, NJ, págs. 124–142, MR  1351284, Zbl  0875.68720
• Fulton, William (1997), Cuadros jóvenes , Textos para estudiantes de la London Mathematical Society, vol. 35, Cambridge University Press , ISBN 978-0-521-56144-0, MR  1464693, Zbl  0878.14034
• Knuth, Donald E. (1970), "Permutaciones, matrices y tablas de Young generalizadas", 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., "El monoide plástico", archivado desde el original el 18 de julio de 2011 {{citation}}: Falta o está vacío |title=( ayuda )
• Littelmann, Peter (1996), "Un álgebra plástica para álgebras de Lie semisimples", 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, vol. 109, Roma: CNR, págs. 129-156, SEÑOR  0646486
• Lothaire, M. (2011), Combinatoria algebraica sobre palabras , Enciclopedia de matemáticas y sus aplicaciones, vol. 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, Zbl1221.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, S2CID  247197258
• Schützenberger, Marcel-Paul (1997), "Pour le monoïde plaxique", Mathématiques, Informatique et Sciences Humaines (140): 5–10, doi : 10.4000/msh.2764 , ISSN  0995-2314, SEÑOR  1627563

• Green, James A. (2007), Representaciones polinomiales de GL _n , Lecture Notes in Mathematics, vol. 830, con un apéndice sobre la correspondencia de Schensted y los caminos de Littelmann de K. Erdmann, JA Green y M. Schocker (2.ª edición corregida y aumentada), Berlín: Springer-Verlag , ISBN 978-3-540-46944-5, Zbl  1108.20044