Robinson–Schensted korrespondens

Inom matematik är Robinson -Schensted-korrespondensen en bijektiv överensstämmelse mellan permutationer och par av standard Young-tablåer av samma form. Den har olika beskrivningar, som alla är av algoritmisk natur, den har många anmärkningsvärda egenskaper och den har tillämpningar inom kombinatorik och andra områden som representationsteori . Korrespondensen har generaliserats på många sätt, särskilt av Knuth till vad som är känt som Robinson-Schensted-Knuth-korrespondensen , och en ytterligare generalisering till bilder av Zelevinsky .

Den enklaste beskrivningen av korrespondensen är att använda Schensted-algoritmen (Schensted 1961 ), en procedur som konstruerar en tablå genom att successivt infoga värdena för permutationen enligt en specifik regel, medan den andra tablån registrerar formens utveckling under konstruktionen. Korrespondensen hade beskrivits, i en ganska annorlunda form, mycket tidigare av Robinson ( Robinson 1938 ), i ett försök att bevisa Littlewood-Richardson-regeln . Korrespondensen kallas ofta för Robinson-Schensted-algoritmen , även om den procedur som används av Robinson är radikalt annorlunda än Schensted-algoritmen och nästan helt bortglömd. Andra metoder för att definiera korrespondensen inkluderar en icke-deterministisk algoritm i termer av jeu de taquin .

Korrespondensens bijektiva karaktär relaterar den till den uppräknade identiteten

\sum _{\lambda \in {\mathcal {P}}_{n}}(t_{\lambda })^{2}=n!

där ${\mathcal {P}}_{n}$ anger uppsättningen av partitioner av $n$ (eller av Young-diagram med $n$ kvadrater), och $t λ$ anger antalet standard Young-tablåer med formen $λ$ .

Schensted-algoritmen

Schensted-algoritmen utgår från permutationen $σ$ skriven i tvåradsnotation

\sigma ={\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}& \sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}

där $σ i = σ (i)$ , och fortsätter genom att konstruera sekventiellt en sekvens av (mellanliggande) ordnade par av unga tablåer med samma form:

(P_{0},Q_{0}),(P_{1},Q_{1}) ,\ldots ,(P_{n},Q_{n}),

där $0 P = Q 0$ är tomma tablåer. Utmatningstabellerna är $P = P n$ och $Q = Q n$ . När $P i -1 väl$ har konstruerats, bildar man $P i$ genom att infoga $σ i$ i $P i -1$ , och sedan $Q i$ genom att lägga till en post $i$ till $Q i -1$ i kvadraten som läggs till formen genom infogningen (så att $P i$ och $Q i$ har lika former för alla $i$ ). På grund av den mer passiva roll som tablåerna $Qi har$ , kallas den sista $Qn Qi$ , som är en del av utgången och från vilken den föregående $lätt kan$ avläsas, inspelningstabellen ; däremot $P kallas$ tablåerna i insättningstablåer .

Införande

Infogning av (4): • (4) ersätter (5) i första raden • (5) ersätter (8) i andra raden • (8) skapar den tredje raden

Den grundläggande proceduren som används för att infoga varje $σ i$ kallas Schensted-insättning eller radinsättning (för att skilja det från en variantprocedur som kallas kolumninsättning). Dess enklaste form definieras i termer av "ofullständiga standardtablåer": liksom standardtablåer har de distinkta poster som bildar ökande rader och kolumner, men vissa värden (som återstår att infoga) kan saknas som poster. Proceduren tar som argument en sådan tablå $T$ och ett värde $x$ som inte finns som inmatning av $T$ ; den producerar som utdata en ny tablå betecknad $T \leftarrow x$ och en kvadrat $s$ med vilken dess form har växt. Värdet $x$ visas i den första raden av $T \leftarrow x$ , antingen efter att ha lagts till i slutet (om inga poster större än $x$ fanns), eller på annat sätt ersätter den första posten $y > x$ i den första raden av $T$ . I det förra fallet $s$ kvadraten där $x$ läggs till och insättningen är klar; i det senare fallet infogas den ersatta posten $y$ på liknande sätt i den andra raden av $T$ , och så vidare, tills vid något steg det första fallet gäller (vilket säkert händer om en tom rad av $T$ nås).

Mer formellt beskriver följande pseudokod radinförandet av ett nytt värde $x$ i $T$ .

Sätt $i = 1$ och $j$ till en mer än längden på den första raden av $T$ .
Medan $j > 1$ och $x < T i, j -1$ , minska $j$ med 1. (Nu är $(i, j)$ den första kvadraten i rad $i$ med antingen en post som är större än $x$ i $T$ , eller ingen post alls.)
Om kvadraten $(i, j)$ är tom i $T ,$ $avsluta s = (i , j)$ efter att ha adderat $x$ till $T$ i kvadraten $(i, j)$ och satt .
Byt värdena $x$ och $Ti, j$ . (Detta infogar det gamla $x$ i rad $i$ och sparar värdet som det ersätter för att infogas i nästa rad.)
Öka $i$ med 1 och återgå till steg 2.

Formen på $T$ växer med exakt en kvadrat, nämligen $s$ .

Rätthet

Det faktum att $T \leftarrow x$ har ökande rader och kolumner, om detsamma gäller för $T$ , är inte uppenbart från denna procedur (poster i samma kolumn jämförs aldrig ens). Det kan dock ses på följande sätt. är kvadraten $(i, j) antingen tom i$ $T$ eller har ett värde större än $x$ ; steg 5 återupprättar denna egenskap eftersom $(i, j)$ nu är kvadraten omedelbart under den som ursprungligen innehöll $x$ i $T.$ Således är effekten av ersättningen i steg 4 på värdet $Ti, j$ att göra det mindre; i synnerhet kan den inte bli större än sina högra eller lägre grannar. Å andra sidan är det nya värdet inte mindre än dess vänstra granne (om det finns) heller, vilket säkerställs av jämförelsen som just gjorde att steg 2 avslutades. För att slutligen se att det nya värdet är större än dess övre granne $Ti -1, j$ om det finns, observera att $Ti -1, j$ gäller efter steg 5, och att minskning av $j$ $i$ steg 2 endast minskar motsvarande värde $Ti - 1, j$ .

Konstruera tablåerna

Den fullständiga Schensted-algoritmen som tillämpas på en permutation $σ$ fortsätter enligt följande.

Ställ in både $P$ och $Q$ till den tomma tablån
För $i$ ökande från $1$ till $n$ beräkna $P \leftarrow σ i$ och kvadraten $s$ genom infogningsproceduren; ersätt sedan $P$ med $P \leftarrow σ i$ och lägg till posten $i$ till tabellen $Q$ i kvadraten $s$ .
Avsluta, returnerar paret $(P, Q)$ .

Algoritmen producerar ett par standard Young-tablåer.

Konstruktionens inverterbarhet

Det kan ses att givet vilket par som helst $(P, Q)$ av standard Young-tablåer av samma form, finns det en omvänd procedur som producerar en permutation som kommer att ge upphov till ( $P, Q) av$ Schensted-algoritmen. Det består huvudsakligen av att spåra stegen i algoritmen bakåt, varje gång med hjälp av en inmatning av $Q$ för att hitta kvadraten där den omvända infogningen ska börja, flytta motsvarande inmatning av $P$ till föregående rad och fortsätta uppåt genom raderna tills en inmatning av P den första raden ersätts, vilket är det värde som infogas vid motsvarande steg i konstruktionsalgoritmen. Dessa två inversa algoritmer definierar en bijektiv överensstämmelse mellan permutationer av $n$ på ena sidan, och par av standard Young-tablåer med lika form och innehållande $n$ kvadrater på den andra sidan.

Egenskaper

En av de mest grundläggande egenskaperna, men inte uppenbar från den algoritmiska konstruktionen, är symmetri:

Om Robinson–Schensted-överensstämmelsen associerar tablåer $(P, Q)$ till en permutation $σ$ , då associerar den $(Q, P)$ till den inversa permutationen $σ -1$ .

Detta kan bevisas, till exempel, genom att vädja till Viennots geometriska konstruktion .

Ytterligare egenskaper, alla förutsatt att överensstämmelsen associerar tablåer $(P, Q)$ till permutationen $σ = (σ 1, ..., σ n)$ .

I tablåparet $(P', Q')$ associerade med den omvända permutationen $(σ n, ..., σ 1)$ , är tablået $P'$ transponeringen av tablået $P$ , och $Q'$ är en tablå som bestäms av $Q$ , oberoende av $P$ (nämligen transponeringen av tablået erhållen från $Q$ genom Schützenberger-involutionen ).
Längden på den längst ökande undersekvensen av $σ 1, ..., σ n$ är lika med längden på den första raden av $P$ (och av $Q$ ).
Längden av den längsta minskande undersekvensen av $σ 1, ..., σ n$ är lika med längden av den första kolumnen av $P$ (och av $Q$ ), som följer av de två föregående egenskaperna.
Nedstigningsmängden ${i : σ i > σ i +1$ } av $σ$ är lika med nedstigningsmängden ${i : i +1 är i en rad strikt under raden av i$ } av $Q$ .
Identifiera undersekvenser av $π$ med deras uppsättningar av index. Det är en sats från Greene att för varje $k \geq 1$ är storleken på den största mängden som kan skrivas som föreningen av högst $k$ ökande delsekvenser $λ 1 + ... + λ k$ . I synnerhet $λ 1$ lika med den största längden av en ökande undersekvens av $π$ .
Om $σ$ är en involution , är antalet fixpunkter för $σ$ lika med antalet kolumner med udda längd i $λ$ .

Se även

Viennots geometriska konstruktion , som ger en schematisk tolkning av korrespondensen.
Plactic monoid : insättningsprocessen kan användas för att definiera en associativ produkt av Young tableaux med poster mellan 1 och $n$ , som kallas Plactic monoid av ordning $n$ .

Anteckningar

Fulton, William (1997), Young Tableaux , London Mathematical Society Student Texts, vol. 35, Cambridge University Press , ISBN 978-0-521-56144-0 , MR 1464693 .
Knuth, Donald E. (1970), "Permutations, matrices, and generalized Young tableaux" , Pacific Journal of Mathematics , 34 : 709–727, doi : 10.2140/pjm.1970.34.709 , MR 0272654
Robinson, G. de B. (1938), "On the Representations of the Symmetric Group", American Journal of Mathematics , 60 (3): 745–760, doi : 10.2307/2371609 , JSTOR 2371609 , Zbl 0019.251 .
Sagan, BE (2001), The Symmetric Group , Graduate Texts in Mathematics, vol. 203, New York: Springer-Verlag, ISBN 0-387-95067-2 .
Schensted, C. (1961), "Longest growth and decreasing subsequences", Canadian Journal of Mathematics , 13 : 179–191, doi : 10.4153/CJM-1961-015-3 , MR 0121305 .
Stanley, Richard P. (1999), Enumerative Combinatorics, vol. 2 , Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press , ISBN 978-0-521-56069-6 , MR 1676282 .
Zelevinsky, AV (1981), "A generalization of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence", Journal of Algebra , 69 (1): 82–94, doi : 10.1016/0021-8693(81)90128 -9 , MR 0613858 .

Vidare läsning

Green, James A. (2007). Polynomrepresentationer av GL _n . Föreläsningsanteckningar i matematik. Vol. 830. Med bilaga om Schensted-korrespondens och Littelmann-vägar av K. Erdmann, JA Green och M. Schocker (2:a korrigerade och utökade uppl.). Berlin: Springer-Verlag . ISBN 3-540-46944-3 . Zbl 1108.20044 .

externa länkar

van Leeuwen, MAA (2001) [1994], "Robinson–Schensted correspondence" , Encyclopedia of Mathematics , EMS Press
Williams, L., Interaktiv animering av Robinson-Schensted-algoritmen