Jeu de taquin

Inom det matematiska området kombinatorik är jeu de taquin en konstruktion som beror på Marcel-Paul Schützenberger ( 1977 ) som definierar en ekvivalensrelation på uppsättningen av snedställda standard Young- tablåer . En jeu de taquin-rutschbana är en förvandling där siffrorna i en tablå flyttas runt på ett sätt som liknar hur bitarna i femtonpusslet rör sig. Två tablåer motsvarar jeu de taquin om den ena kan omvandlas till den andra via en sekvens av sådana bilder.

"Jeu de taquin" (bokstavligen "retsspel") är det franska namnet på femtonpusslet .

Definition av en jeu de taquin-rutschbana

Exempel på en Jeu de taquin-rutschbana

Givet en sned standard Ung tablå T av skev form $\lambda /\mu$ , välj en intilliggande tom cell c som kan läggas till skevningsdiagrammet $\lambda \setminus \mu$ ; vad detta betyder är att c måste dela minst en kant med någon cell i T , och $\{c\}\cup \lambda \setminus \mu$ måste också vara ett skevt diagram. Det finns två sorters glid, beroende på om c ligger uppe till vänster om T eller till nedre höger. Antag till att börja med att c ligger uppe till vänster. Skjut numret från dess närliggande cell till c ; om c har grannar både till höger och nedanför, välj det minsta av dessa två tal. (Denna regel är utformad så att tablåegenskapen att ha ökande rader och kolumner kommer att bevaras.) Om cellen som just har tömts inte har någon granne till höger eller nedanför, är bilden klar. Annars, skjut in ett nummer i den cellen enligt samma regel som tidigare, och fortsätt på detta sätt tills bilden är klar. Efter denna transformation är den resulterande tablån (med den nu tomma cellen borttagen) fortfarande en sned (eller möjligen rak) standard Young-tablå.

Den andra typen av rutschkana, när c ligger nere till höger om T , går precis i motsatt riktning. I det här fallet skjuter man in siffror i en tom cell från grannen till vänster eller ovanför den, och väljer det större numret närhelst det finns ett val. De två typerna av rutschbanor är ömsesidiga inverser – en rutschbana av det ena slaget kan ångras med en rutschkana av det andra slaget.

De två objektglasen som beskrivs ovan kallas objektglas in i cellen c . Den första typen av rutschkana (när c ligger uppe till vänster om T ) sägs vara en inåtgående rutschkana ; den andra typen kallas en utåtgående glidning .

Ordet "slide" är synonymt med det franska ordet "glissement", som ibland också används i engelsk litteratur.

Finesser

Jeu-de-taquin diabilder ändrar inte bara den relativa ordningen för posterna i en tablå, utan också dess form. I definitionen som ges ovan ges resultatet av en jeu-de-taquin-bild som ett skevt diagram tillsammans med en sned standardtabell som har den som form. Ofta är det bättre att arbeta med skeva former snarare än skeva diagram. (Kom ihåg att varje skevningsform $\lambda /\mu$ ger upphov till ett skevt diagram ${\displaystyle \lambda \setminus \mu } ,$ men detta är inte en injektiv överensstämmelse eftersom t.ex. distinkta sneda former $(2,1)/(2)$ och $(1,1)/(1)$ ger samma skevningsdiagram.) Av denna anledning är det användbart att modifiera ovanstående definition av en jeu-de-taquin-rutschbana på ett sådant sätt att, när den ges en sned form tillsammans med en sned standardtabell och en tilläggbar cell som indata, det ger en väldefinierad sned form tillsammans med en sned standardtabell vid dess utgång. Detta görs på följande sätt: En inåtgående glidning av en skev tablå T med sned form $\lambda /\mu$ in i en cell c definieras som ovan när c är ett hörn av $\mu$ (det vill säga när $\mu \setminus \left\{c\right\}$ är ett Young-diagram), och den resulterande skevningsformen är satt till $(\lambda \setminus \left\{d\right\})/(\mu \setminus \left\{c\right\})$ där d är den tomma cellen vid slutet av glidproceduren. En utåtgående glidning av en skev tablå T med sned form $\lambda /\mu$ in i en cell c definieras som ovan när c är ett medhörn av $\lambda$ (det vill säga när $\lambda \cup \left\{c\right\}$ är ett Young-diagram), och den resulterande snedformen är satt till ${\displaystyle (\lambda \cup \left\{c\right\})/(\mu \cup \left\{d\right\})} där d är den tomma cellen i slutet$ av skjutproceduren .

Generalisering för att skeva halvstandardtablåer

Jeu de taquin-bilder generaliserar för att skeva halvstandardiserade (i motsats till snedställda standard) tablåer och behåller de flesta av sina egenskaper i den generaliteten. Den enda ändring som måste göras i definitionen av en inåtgående bild för att den ska kunna generaliseras, är en regel om hur man ska gå tillväga när den (tillfälligt) tomma cellen har grannar under och till höger, och dessa grannar är fyllda med lika många. I den här situationen måste grannen nedanför (inte den till höger) skjutas in i den tomma cellen. En liknande förändring behövs i definitionen av en utåtgående rutschbana (där man måste välja grannen ovan). Dessa förändringar kan tyckas godtyckliga, men de gör faktiskt de "enda rimliga valen" – vilket betyder de enda valen som håller kolumnerna i tablåen (bortsett från den tomma cellen) strikt ökande (i motsats till att bara svagt öka).

Rättelse

Med tanke på en sned standard eller sned semistandard tablå T , kan man iterativt applicera inåtgående diabilder på T tills tablån blir rak form (vilket betyder att inga fler inåtgående diabilder är möjliga). Detta kan i allmänhet göras på många olika sätt (man kan fritt välja in i vilken cell man ska glida först), men den resulterande tablån med rak form är känd för att vara densamma för alla möjliga val. Denna tablå kallas rättelse av T .

Jeu-de-taquin likvärdighet

Två sneda halvstandardtablåer T och S sägs vara jeu-de-taquin-ekvivalenter om den ena kan omvandla den ena till den andra med hjälp av en sekvens (eventuellt tomma) av diabilder (både inåt- och utåtgående diabilder är tillåtna). På motsvarande sätt är två skeva halvstandardtablåer T och S jeu-de-taquin ekvivalenta om och bara om de har samma rättelse.

Läsa ord och Knuth-ekvivalens

Det finns olika sätt att associera ett ord (i betydelsen kombinatorik, dvs. en ändlig sekvens av element i ett alfabet – här uppsättningen av positiva heltal) till varje Young-tablå. Vi väljer den som uppenbarligen är mest populär: Vi associerar till varje Ung tablå T ordet som erhålls genom att sammanfoga raderna med T från den nedre raden till den översta raden. (Varje rad av T ses som ett ord helt enkelt genom att läsa dess poster från vänster till höger, och vi ritar Unga tablåer i engelsk notation så att den längsta raden i en tablå med rak form visas överst.) Detta ord kommer att refereras till. till som läsord , eller kortfattat som ord , av T .

Det kan då visas att två skeva semistandardtablåer T och S är jeu-de-taquin-ekvivalenter om och endast om läsorden för T och S är Knuth-ekvivalenta . Som en konsekvens kan korrigeringen av en sned semistandardtableau T också erhållas som insättningstableau för läsordet av T under Robinson-Schensted-korrespondensen .

Schützenberger-involutionen

Jeu de taquin kan användas för att definiera en operation på standard Young-tablåer av vilken form som helst, vilket visar sig vara en involution , även om detta inte framgår av definitionen. Man börjar med att tömma kvadraten i det övre vänstra hörnet, förvandla tablån till en sned tablå med en ruta mindre. Applicera nu en jeu de taquin-rutschbana för att förvandla den sneda tablån till en rak, vilket kommer att frigöra en ruta på den yttre kanten. Fyll sedan denna ruta med negativt av värdet som ursprungligen togs bort i det övre vänstra hörnet; detta negerade värde anses vara en del av en ny tablå snarare än av den ursprungliga tablån, och dess position kommer inte att ändras i uppföljaren. Så länge den ursprungliga tablån har några poster kvar, upprepa operationen med att ta bort posten x i det övre vänstra hörnet, utför en jeu de taquin-bild på det som är kvar av den ursprungliga tablån och placera värdet − x i kvadrat så frigjort. När alla poster i den ursprungliga tablån har hanterats arrangeras deras negerade värden på ett sådant sätt att rader och kolumner ökar. Slutligen kan man lägga till en lämplig konstant till alla poster för att få en Ung tablå med positiva poster.

Ansökningar

Jeu de taquin är nära kopplat till sådana ämnen som Robinson-Schensted-Knuth-korrespondensen , Littlewood -Richardson-regeln och Knuth-ekvivalensen .

Désarménien, J. (2001) [1994], "Jeu de taquin" , Encyclopedia of Mathematics , EMS Press
Sagan, Bruce E. (2001), The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , Graduate Texts in Mathematics 203 (2nd ed.), New York: Springer, ISBN 0-387-95067-2
Fulton, William (1997), Young Tableaux , London Mathematical Society Student Texts 35 (1:a upplagan), Melbourne: Cambridge University Press, ISBN 0-521-56144-2
Haiman, MD (1992). "Dubbel likvärdighet med applikationer, inklusive en gissning om Proctor" . Diskret matematik . 99 : 79–113. doi : 10.1016/0012-365X(92)90368-P .
Schützenberger, Marcel-Paul (1977), "La correspondance de Robinson", i Foata, Dominique (red.), Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976) , Föreläsning Notes in Math., vol. 579, Berlin: Springer, s. 59–113 , doi : 10.1007/BFb0090012 , ISBN 978-3-540-08143-2

Stanley, Richard P. (1999), Enumerative Combinatorics , Cambridge Studies in Advanced Mathematics 62, vol. 2, Cambridge University Press, ISBN 0-521-56069-1