Plaktický monoid - Plactic monoid

V matematice je plaktický monoid je monoidní všech slov v abecedě kladných celých čísel modulo Knuthova rovnocennost. Jeho prvky lze identifikovat pomocí polostandardních Young tabel. Objevil jej Donald Knuth  (1970 ) (kdo to nazval tableau algebra), pomocí operace dané Craige Schensted  (1961 ) ve své studii o nejdelší rostoucí posloupnost permutace.

Byl pojmenován „monoïde plaxique"od Lascoux & Schützenberger (1981), který v definici povolil jakoukoli úplně seřazenou abecedu. Etymologie slova „plaxique„je nejasný; může odkazovat na tektonika desek ("tectonique des plaques" ve francouzštině), jako elementární vztahy, které generují rovnocennost umožňují podmíněné komutace symbolů generátoru: mohou někdy klouzat přes sebe (ve zjevné analogii k tektonickým deskám), ale ne volně.

Definice

Plaktický monoid nad nějakou zcela uspořádanou abecedou (často kladná celá čísla) je monoid s následujícím prezentace:

• Generátory jsou písmena abecedy
• Vztahy jsou základní Knuthovy transformace yzx ≡ yxz kdykoli X < y ≤ z a xzy ≡ zxy kdykoli X ≤ y < z.

Knuthova rovnocennost

Nazývají se dvě slova Knuthův ekvivalent pokud představují stejný prvek plaktického monoidu, nebo jinými slovy, pokud lze jeden získat od druhého sekvencí elementárních Knuthových transformací.

Knuthova rovnocennost zachovává několik vlastností.

• Pokud je slovo a obrácené mřížkové slovo, pak je každé slovo Knuth ekvivalentní tomuto.
• Pokud jsou dvě slova Knuthovým ekvivalentem, pak jsou to také slova získaná odstraněním maximálních prvků zcela vpravo, stejně jako slova získaná odstraněním minimálních prvků zcela vlevo.
• Knuthova rovnocennost zachovává délku nejdelší neklesající subsekvence a obecněji zachovává maximum součtu délek k disjunktní neklesající subsekvence pro všechny pevné k.

Každé slovo je Knuth ekvivalentní slovu jedinečného polostandardní Young tablo (to znamená, že každý řádek neklesá a každý sloupec se přísně zvyšuje). Takže prvky plaktického monoidu lze identifikovat pomocí polostandardních Young tabel, které proto také tvoří monoid.

Tableau ring

The tablo prsten je monoidní prsten plaktického monoidu, takže má a Z-základ sestávající z prvků plaktického monoidu, se stejným produktem jako v plaktickém monoidu.

Existuje homomorfismus od plaktického prstence na abecedě po prsten polynomů (s proměnnými indexovanými podle abecedy), který vezme jakékoli tablo k součinu proměnných jeho položek.

Růst

The generující funkce plaktického monoida na abecedě velikosti n je

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

což ukazuje, že existuje polynomiální růst dimenze ${displaystyle {frac {n (n + 1)} {2}}}$.

Viz také

• Čínský monoid

Reference

• Duchamp, Gérard; Krob, Daniel (1994), „Monoidní růst podobný plaktu“, Slova, jazyky a kombinatorika, II (Kyoto, 1992), World Sci. Publ., River Edge, NJ, s. 124–142, PAN  1351284, Zbl  0875.68720
• Fulton, William (1997), Mladé obrazy, London Mathematical Society Student Texts, 35, Cambridge University Press, ISBN  978-0-521-56144-0, PAN  1464693, Zbl  0878.14034
• Knuth, Donald E. (1970), „Permutace, matice a generalizované Youngovy obrazy“, Pacific Journal of Mathematics, 34 (3): 709–727, doi:10,2140 / pjm.1970.34.709, ISSN  0030-8730, PAN  0272654
• Lascoux, Alain; Leclerc, B .; Thibon, J-Y., „Plaktický monoid“, archivovány z originál dne 18.7.2011 Chybějící nebo prázdný | název = (Pomoc)
• Littelmann, Peter (1996), „Plaktická algebra pro polojednoduché Lieovy algebry“, Pokroky v matematice, 124 (2): 312–331, doi:10.1006 / aima.1996.0085, ISSN  0001-8708, PAN  1424313
• Lascoux, Alain; Schützenberger, Marcel-P. (1981), „Le monoïde plaxique“ (PDF), Nekomutativní struktury v algebře a geometrické kombinatorice (Neapol, 1978), Quaderni de La Ricerca Scientifica, 109, Řím: CNR, s. 129–156, PAN  0646486
• Lothaire, M. (2011), Algebraická kombinatorika slovEncyklopedie matematiky a její aplikace 90„S předmluvou Jean Berstel a Dominique Perrin (dotisk edice vázané knihy z roku 2002), Cambridge University Press, ISBN  978-0-521-18071-9, Zbl  1221.68183
• Schensted, C. (1961), „Nejdelší rostoucí a klesající subsekvence“, Kanadský žurnál matematiky, 13: 179–191, doi:10.4153 / CJM-1961-015-3, ISSN  0008-414X, PAN  0121305
• Schützenberger, Marcel-Paul (1997), „Pour le monoïde plaxique“, Mathématiques, Informatique et Sciences Humaines (140): 5–10, ISSN  0995-2314, PAN  1627563

Další čtení

• Zelená, James A. (2007), Polynomiální reprezentace GL_nPřednášky z matematiky, 830„S dodatkem o Schenstedově korespondenci a Littelmannově cestě K. Erdmanna, J. A. Greena a M. Schockera (2. opravené a rozšířené vydání), Berlín: Springer-Verlag, ISBN  978-3-540-46944-5, Zbl  1108.20044