Plaktik monoid - Plactic monoid
Matematikte, plactic monoid olan monoid pozitif sayının alfabesinde tüm kelimelerin modulo Knuth denklik . Öğeleri yarı standart Young tableaux ile tanımlanabilir . Bir permütasyonun en uzun artan ardışıklığı üzerine yaptığı çalışmada Craige Schensted ( 1961 ) tarafından verilen bir işlem kullanılarak Donald Knuth ( 1970 ) (buna tablo cebiri adını verdi) tarafından keşfedildi .
Tanımda herhangi bir tamamen sıralı alfabeye izin veren Lascoux & Schützenberger (1981) tarafından " monoïde plaxique " olarak adlandırıldı . " Plaksique " kelimesinin etimolojisi belirsizdir; Eşdeğerliği oluşturan temel ilişkiler , jeneratör sembollerinin koşullu komütasyonuna izin verdiğinden, plaka tektoniğine atıfta bulunabilir (Fransızca'da "tectonique des plaks") : bazen birbirleri üzerinde kayabilirler (tektonik plakalara açık bir benzerlikle), ancak serbestçe değil.
Tanım
Tamamen sıralı bir alfabe (genellikle pozitif tamsayılar) üzerindeki plactic monoid, aşağıdaki sunuma sahip monoiddir :
- Jeneratörler alfabenin harfleridir.
- İlişkiler temel Knuth dönüşümler YZX ≡ yxz her x < y ≤ z ve xzy ≡ ZXY her x ≤ y < z .
Knuth denkliği
İki kelime , plactic monoidin aynı elementini temsil ediyorsa veya başka bir deyişle, bir dizi temel Knuth dönüşümleri ile diğerinden elde edilebiliyorsa, Knuth eşdeğeri olarak adlandırılır .
Bazı özellikler Knuth denkliği ile korunur.
- Bir kelime bir ters kafes kelimesiyse , o zaman herhangi bir kelime Knuth ona eşdeğerdir.
- Eğer iki kelime Knuth eşdeğeriyse, o zaman en sağdaki en büyük elemanları kaldırılarak elde edilen kelimeler ve en soldaki minimal elemanları kaldırılarak elde edilen kelimeler de öyledir.
- Knuth denkliği, en uzun azalan olmayan alt dizinin uzunluğunu korur ve daha genel olarak , herhangi bir sabit k için k ayrık azalmayan alt dizinin uzunluklarının toplamının maksimumunu korur .
Semistandard Young Tableaux ile Yazışma
Her kelime, tablonun satırlar veya sütunlar tarafından okunabileceği aynı sıralı alfabe üzerinde benzersiz bir yarı standart Young tablosunun (bu, her satırın azalmadığı ve her sütunun kesinlikle arttığı anlamına gelir) kelimesine Knuth eşdeğeridir . Böylece, plactic monoidin elemanları, aynı zamanda bir monoid oluşturan yarı standart Young tableaux ile tanımlanabilir.
Yarı standart bir Young tablosunun kelimesini bir jeneratör ile sola çarpmak , Young tablosuna Schensted eklenmesine eşdeğerdir . Satır sırasına göre, tablonun kelimesi, giderek daha uzun azalmayan jeneratör dizilerinin bir ürününe eşdeğerdir. Yeni üreteç, ya daha büyükse onu ekleyerek ya da sıra dışı elemanı bir sonraki satıra taşımak için plastik bağıntıları tekrar tekrar uygulayarak uygun yerine yerleştirilebilir. İkinci durumda, sıra dışı öğe, her satırda kendisinden daha büyük olan en soldaki girişi değiştirir ve yeri değiştirilen öğe daha sonra bir sonraki satıra eklenir.
Yana Schensted ekleme Genç tableaux korur, bu plactic Monoid elemanları Genç Tabloda tekabül eden bir standart biçiminde yazılmış edilebilir bir endüktif bir kanıt sağlar, ve inşaat semistandard tableaux doğal ürün tanımlar.
Jeu de Taquin
İki çarpık Young Tableaux, yalnızca kelime okumaları Knuth eşdeğeriyse, yani plactic grubunun eşdeğer öğelerine karşılık geliyorsa Jeu de taquin eşdeğeridir. Bu, plastik grup ürününün alternatif bir tanımını doğrudan Young tabloları cinsinden verir. İki tablo, çarpık bir tablo oluşturmak için boş bir dikdörtgenin etrafına çizilerek ve düzeltmek için Jeu de taquin slaytları kullanılarak çarpılabilir.
tablo yüzük
Tablo halkası , plastik monoidin monoid halkasıdır , bu nedenle, plastik monoiddeki ile aynı ürünle, plastik monoidin elemanlarından oluşan bir Z- tabanına sahiptir .
Bir alfabedeki plastik halkadan polinomlar halkasına (alfabe tarafından indekslenen değişkenlerle) herhangi bir tabloyu , plastik yarıgrubun abelianizasyonuna karşılık gelen, girdilerinin değişkenlerinin ürününe alan bir homomorfizma vardır .
Büyüme
Üreten fonksiyon boyutu bir alfabe ile plactic Monoid arasında n olduğu
boyutun polinom büyümesinin olduğunu gösterir .
Ayrıca bakınız
Referanslar
- Duchamp, Gerard; Krob, Daniel (1994), "Plaktik-büyüme benzeri monoidler" , Sözcükler, diller ve kombinatorik, II (Kyoto, 1992) , World Sci. Yayın, River Edge, NJ, s. 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 0878.14034
- Knuth, Donald E. (1970), "Permutations, matrixs and generalized Young tableaux" , 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 Monooid" , 2011-07-18 tarihinde orijinalinden arşivlendi Eksik veya boş
|title=
( yardım ) - Littelmann, Peter (1996), " Yarıbasit Lie cebirleri için bir plastik cebir" , Matematikte Gelişmeler , 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) , Cebir ve geometrik kombinatorikte değişmeyen yapılar (Naples, 1978) , Quaderni de La Ricerca Scientifica, 109 , Roma: CNR, s. 129–156, MR 0646486
- Lothaire, M. (2011), Cebirsel kombinatorikler , Matematik Ansiklopedisi ve Uygulamaları, 90 , Jean Berstel ve Dominique Perrin'in önsözüyle (2002 ciltli baskısının yeniden basımı), Cambridge University Press, ISBN 978-0-521-18071-9, Zbl 1221.68183
- Schensted, C. (1961), "En uzun artan ve azalan alt diziler " , 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
daha fazla okuma
- Green, James A. (2007), GL n'nin Polinom temsilleri, Matematikte Ders Notları, 830 , Schensted yazışmaları ve Littelmann yolları üzerine bir ek ile K. Erdmann, JA Green ve M. Schocker (2. düzeltilmiş ve artırılmış ed.) , Berlin: Springer-Verlag , ISBN 978-3-540-46944-5, Zbl 1108.20044