Ungt maleri

The Young tableaux are objects combinatorial play en viktig rolle i teorien om representasjoner av grupper og i teorien om symmetriske funksjoner . De gjør det spesielt mulig å konstruere de irredusible representasjonene av den symmetriske gruppen , så vel som de for den generelle lineære gruppen på feltet av komplekser . Youngs bord ble introdusert av Alfred Young , matematiker ved Cambridge University , i 1900. De ble brukt på studien av den symmetriske gruppen av Georg Frobenius i 1903. Teorien deres ble utviklet av mange matematikere, blant dem Percy MacMahon , WVD Hodge , G . de B. Robinson , Gian-Carlo Rota , Alain Lascoux , Marcel-Paul Schützenberger og Richard P. Stanley .

Definisjon

Youngs diagram

Et ungt diagram (også kalt et Ferrers-diagram) er en endelig samling av bokser, eller celler, organisert i venstrejusterte linjer, med den egenskapen at lengden på linjene vokser bredt (hver linje er like lang eller lengre enn den forrige) . Sekvensen av lengden på linjene gir en partisjon av heltallet som er det totale antallet celler i diagrammet. Bildet til høyre viser diagrammet som er knyttet til poengsummen . Partisjonen kalles formen på diagrammet. Inkluderingen av ett Young-diagram i et annet definerer en gitterstruktur kjent som en Youngs gitter . Hvis vi teller antall celler i et kolonnediagram, får vi en annen partisjon, kalt konjugat eller transponere partisjon av . λ{\ displaystyle \ lambda}ikke{\ displaystyle n}(5,4,1){\ displaystyle (5,4,1)}λ{\ displaystyle \ lambda}λ{\ displaystyle \ lambda}

Cellene i et Young-diagram indekseres vanligvis av par av heltall, den første indeksen angir raden, den andre kolonnen. Imidlertid er det to konvensjoner for å representere disse diagrammene, den første som plasserer hver rad under den forrige, den andre som plasserer den over. Den første konvensjonen brukes hovedsakelig av anglofoner , den andre er ofte foretrukket av frankofoner  ; Dette er grunnen til at disse notasjonene kalles engelsk notasjon og fransk notasjon . Engelsk notasjon tilsvarer matriser, fransk notasjon til kartesiske koordinater.

Ungt maleri

For et naturlig tall betegner vi settet med heltall fra til . A Youngs tabell oppnås ved å fylle cellene i et Youngs diagram med heltall. Opprinnelig var innganger variabler ; nå bruker vi heltall. I sin opprinnelige søknad til representasjoner av den symmetriske gruppen har Youngs arrays separate oppføringer, vilkårlig assosiert med arraycellene. A Youngs matrise er standard når verdiene til oppføringene er to og to forskjellige, og er heltall fra 1 til totalt antall celler, og slik at oppføringene øker strengt i rader og kolonner. En matrise er semi-standard når radene øker i vid forstand , og kolonnene øker i streng forstand , og når alle heltall fra 1 til maksimumsverdien er til stede. m{\ displaystyle m}[m]{\ displaystyle [m]}1{\ displaystyle 1}m{\ displaystyle m}x1,x2,x3,...{\ displaystyle x_ {1}, x_ {2}, x_ {3}, \ ldots}ikke{\ displaystyle n}

Den vekten av en matrise er en sekvens som, for hver verdi til stede i en Youngs matrise, indikerer antallet ganger det vises der. Dermed er en semi-standard Youngs array en standard array når vekten er . (1,1,...,1){\ displaystyle (1,1, \ ldots, 1)}

Ungt venstre bord

En venstre form er et par partisjoner slik at Young-diagrammet til partisjonen inneholder Young-diagrammet til partisjonen ; dette betyr at hvis og , så for alt . En venstre skjema er betegnet eller . Det venstre diagrammet til en venstre form er den innstilte forskjellen mellom de unge diagrammene av og av  : den inneholder boksene som er i diagrammet for og ikke i diagrammet for . En tabell til venstre for Young oppnås ved å fylle ut boksene i det tilsvarende venstre diagrammet. Igjen, en tabell er semi-standard hvis oppføringene øker strengt i kolonne, og øker bredt i rad. Hvis i tillegg alle heltall fra 1 til antall celler vises nøyaktig en gang, er tabellen standard. (λ,μ){\ displaystyle (\ lambda, \ mu)}λ{\ displaystyle \ lambda}μ{\ displaystyle \ mu}λ=(λ1,λ2,...){\ displaystyle \ lambda = (\ lambda _ {1}, \ lambda _ {2}, \ ldots)}μ=(μ1,μ2,...){\ displaystyle \ mu = (\ mu _ {1}, \ mu _ {2}, \ ldots)}λJeg≥μJeg{\ displaystyle \ lambda _ {i} \ geq \ mu _ {i}}Jeg{\ displaystyle i}λ/μ{\ displaystyle \ lambda / \ mu}λ∖μ{\ displaystyle \ lambda \ setminus \ mu}λ{\ displaystyle \ lambda}μ{\ displaystyle \ mu}λ{\ displaystyle \ lambda}μ{\ displaystyle \ mu}

Den venstre formen til et ungt venstre diagram kan ikke alltid bestemmes ut fra cellesettet i diagrammet. For eksempel hvis og , det venstre formdiagrammet består av en enkelt celle i posisjon . Men denne cellen kan fås på et uendelig antall andre måter, for eksempel ved å forlenge den første linjen i de to figurene, eller ved å legge til andre identiske linjer. På samme måte, hvis et diagram består av flere ikke-relaterte deler, kan det fås fra flere forskjellige former. λ=(5,4,2,1){\ displaystyle \ lambda = (5,4,2,1)}μ=(5,3,2,1){\ displaystyle \ mu = (5,3,2,1)}λ/μ{\ displaystyle \ lambda / \ mu}(2,4){\ displaystyle (2,4)}

Alle halv-standard tabell venstre form med positive innganger bestemmer en sekvens av poeng (eller Young diagrammer) som følger: vi begynner med ; i det tredje trinnet tar vi som partisjon den hvis diagram er hentet fra ved å legge til alle cellene som inneholder en verdi ; den endelige poengsummen er poengsummen . Ethvert påfølgende par diagrammer i denne sekvensen definerer en venstre form hvis diagram maksimalt inneholder en oppføring i hver kolonne (fordi oppføringene øker i kolonnen). Slike former kalles horisontale striper ( horisontale striper på engelsk). Denne serien av partisjoner bestemmer helt . T{\ displaystyle T}λ/μ{\ displaystyle \ lambda / \ mu}μ{\ displaystyle \ mu}Jeg{\ displaystyle i}μ{\ displaystyle \ mu}T{\ displaystyle T}≤Jeg{\ displaystyle \ leq i}λ{\ displaystyle \ lambda}T{\ displaystyle T}

Utvidelse

I stedet for å ta verdiene til en Youngs rekke i heltall, tar vi dem i hvilket som helst alfabet , ordnet helt. Når vi suksessivt leser radene i et semistandard Youngs bord, får vi en sekvens av økende ord i vid forstand på dette alfabetet. Hvert ord i denne sekvensen dominerer det neste i den forstand det og mer for . For Young-diagrammet av poengsummen (3,3,1) er ordene i linjene , og hver dominerer det neste. Produktet av radord blir ofte noen ganger referert til som en matrise. I vårt eksempel er dette ordet . Korrespondansen mellom ord og halvstandardtabell er en-til-en: for å dekode ordet, er det tilstrekkelig hver gang å ta det lengste prefikset som øker i bred forstand. I skjemaet tabellen til høyre , den ord-tabell er tatt inn i rader, som hver dominerer den neste. x=x1⋯xr{\ displaystyle x = x_ {1} \ cdots x_ {r}}y=y1⋯ys{\ displaystyle y = y_ {1} \ cdots y_ {s}}r≤s{\ displaystyle r \ leq s}xJeg<yJeg{\ displaystyle x_ {i} <y_ {i}}1≤Jeg≤r{\ displaystyle 1 \ leq i \ leq r}4234122{\ displaystyle 4 \, 234 \, 122}4234122{\ displaystyle 4234122}(7,6,4,2){\ displaystyle (7,6,4,2)}684556223357111444{\ displaystyle 684556223357111444}

Kombinatoriske egenskaper

Schensted-algoritme

Den Schensted algoritmen er en algoritme som gjør det mulig å sette inn et heltall i en semi-standard eller standard matrise, slik at det oppnås en ny rekke av den samme type. Denne algoritmen tillater:

• å gi alle tabellene en intern komposisjonslov ved å sette elementene i ett bord suksessivt inn i et annet.
• for å etablere en sammenheng mellom permutasjoner, og mer generelt sekvenser av positive heltall og par av standard (resp. semi-standard) Unge matriser av samme form, kjent som korrespondansen Robinson-Schensted-Knuth .(P,Spørsmål){\ displaystyle (P, Q)}
• å indusere en ekvivalensrelasjon på settet med endelige sekvenser av positive heltall. To ord er ekvivalente hvis de til og med har tabell P. i korrespondansen Robinson-Schensted.

En geometrisk konstruksjon av Robinson-Schensted-korrespondansen mellom permutasjoner og par av standard Young tabeller av samme form ble gitt av Viennot.

Knuth relasjoner

Fra studiet av dette ekvivalensforholdet på ord med lengde 3 definerte Donald Knuth omskrivingsregler på settet med ord på . Disse omskrivningsreglene induserer også en ekvivalensrelasjon, og Knuth har vist at den sammenfaller med Schensted-forholdet. En viktig konsekvens av denne teoremet er at loven om komposisjon som følger av Schensteds algoritme har alle egenskapene som kreves for å gi settet med matriser en monoid struktur  : den plaksiske monoiden . [m]{\ displaystyle [m]}

Kvadratformel

De formel brakettene ( krok-lengde formel i engelsk) er en formel for å beregne antall standard form av tablåer gitt. Dette tallet er viktig, fordi antall standard Youngs matriser av en gitt form er lik dimensjonen til den irredusible representasjonen av den symmetriske gruppen som tilsvarer en partisjon av . λ{\ displaystyle \ lambda}Sikke{\ displaystyle S_ {n}}λ{\ displaystyle \ lambda}ikke{\ displaystyle n}

Settet firkantet i forbindelse med en celle av den formen Ferrers diagrammet er sammensatt av denne celle, og alle cellene til høyre og nedenfor (på engelsk notasjon), henholdsvis til høyre og ovenfor (på fransk notasjon) av cellen . Den lengde av plassen (på engelsk krok-lengde ) er det antall celler som utgjør kvadratet. I partisjonseksemplet har den øverste venstre cellen 5 celler på samme rad og 3 i samme kolonne. Lengden på firkanten er derfor 7. x{\ displaystyle x}Y(λ){\ displaystyle Y (\ lambda)}λ{\ displaystyle \ lambda}x{\ displaystyle x} h(x){\ displaystyle h (x)}λ=(5,4,1){\ displaystyle \ lambda = (5,4,1)}

Vi betegner antall standard Young arrays of form , for en partisjon av . fλ{\ displaystyle f ^ {\ lambda}}λ{\ displaystyle \ lambda}ikke{\ displaystyle n}

Kvadratformel  -  La være antall standard Unge matriser av form for en partisjon av . Så det har vi gjort fλ{\ displaystyle f ^ {\ lambda}}λ{\ displaystyle \ lambda}ikke{\ displaystyle n}

fλ=ikke!∏x∈Y(λ)h(x){\ displaystyle f ^ {\ lambda} = {\ frac {n!} {\ prod _ {x \ in Y (\ lambda)} h (x)}}}.

Figuren motsatt gir lengden på brakettene for skilleveggen . Vi oppnår λ=(5,4,1){\ displaystyle \ lambda = (5,4,1)}

fλ=10!7⋅5⋅4⋅3⋅1⋅5⋅3⋅2⋅1⋅1=288.{\ displaystyle f ^ {\ lambda} = {\ frac {10!} {7 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 1 \ cdot 5 \ cdot 3 \ cdot 2 \ cdot 1 \ cdot 1}} = 288 .}

Det er derfor 288 standard Young tabeller av dette skjemaet, og det er like mange irredusible representasjoner av den symmetriske gruppen S 10 som tilsvarer denne partisjonen.

Den firkantede formelen kalles også Frame-Robinson-Thrall-setningen ifølge forfatterne av et bevis. Kombinatorisk bevis, ved bruk av Schützenbergers ertingsspill, ble gitt av Novelli, Pak og Stoyanovskii. Det er faktisk gitt mange bevis, blant annet andre bevis ved sammenheng. Beviset fra Novelli, Pak og Stoyanovskii blir av Krattenthaler ansett som det mest naturlige: " Den sammenheng som  presenteres i avisen under vurdering, må betraktes som den naturlige krokbinding  ". Referansebøker, som Sagan 2001 eller Fulton 1997 , inneholder bevis. En grunnleggende og detaljert demonstrasjon av Jason Bandlow eksisterer online.

Sum av kvadrater formel

En formel nær kvadratformelen er som følger:

Summen av firkanter  -  La være et helt tall. Vi har : ikke{\ displaystyle n}

∑λ(fλ)2=ikke!{\ displaystyle \ sum _ {\ lambda} (f ^ {\ lambda}) ^ {2} = n \,!},

hvor summen er over alle partisjoner av , og er antall standard Young arrays of form . λ{\ displaystyle \ lambda}ikke{\ displaystyle n}fλ{\ displaystyle f ^ {\ lambda}}λ{\ displaystyle \ lambda}

For partisjonene (3), (2,1) og (1,1,1) til heltallet 3 er det henholdsvis 1, 2 og 1 standard Youngs array (x) av denne formen, d 'hvor totalt 1 + 4 + 1 = 6 = 3!. Et bevis på denne formelen er godt utført ved hjelp av Youngs gitter .

Oversikt over applikasjoner

Youngs arrays har mange anvendelser innen kombinatorikk , representasjonsteori og algebraisk geometri . Ulike måter å telle Young arrays har blitt utforsket, og har ført til definisjonen og identiteten på Schur-polynomer . Mange algoritmer har blitt utviklet, inkludert Schützenberger teaser spill , den Robinson-Schensted-Knuth korrespondanse , eller VIENNOT geometriske konstruksjon . Lascoux og Schützenberger introduserte et assosiativt produkt på settet med semi-standard Young arrays som ga dette settet en monoid struktur, kalt plaxic monoid .

I representasjonsteorien beskriver standard tabeller av størrelse størrelsen på de irredusible representasjonene av den symmetriske gruppen på bokstaver. Standardmonomiale baser av en irredusibel endelig dimensjonsrepresentasjon av den generelle lineære gruppen parametriseres av settet med semi-standard Young arrays of form fast på alfabetet . Dette har viktige konsekvenser i invariant teori . Den Little-Richardson regel som beskriver, blant annet, dekomponering av tensorprodukt av ikke-reduserbare representasjoner av det til ikke-reduserbare komponenter formuleres i form av venstre Young tabeller. k{\ displaystyle k}k{\ displaystyle k} GLikke{\ displaystyle {\ text {GL}} _ {n}}{1,2,...,ikke}{\ displaystyle \ {1,2, \ ldots, n \}}GLikke{\ displaystyle {\ text {GL}} _ {n}}

Applikasjoner i algebraisk geometri fokuserer på Schuberts kalkulus , Grassmannians og flaggmanifold . Noen viktige kohomologiklasser kan være representert av Schubert-polynomier  (in) og beskrevet i termer av Young tableaux.

Søknader til gruppepresentasjoner

Representasjoner fra den symmetriske gruppen

Representasjon av GL ( E )

Hvis E er et ℂ-vektorrom av dimensjon m , og λ en partisjon, definerer vi Schur-modul E λ som å være ℂ-vektorrommet hvis base er dannet av settet av Young arrays of form λ og med verdi i [ m ]. Å vite at det er mulig å identifisere en Youngs matrise med verdier i [ m ] til et polynom av ℂ [ X i, j | 1 i i, j ≤ m ], det eksisterer en naturlig virkning av GL ( E ) på Youngs matriser ved enkel matriksmultiplikasjon. Schurs moduler er derfor representasjoner av GL ( E ). Vi kan vise at enhver irredusibel polynomrepresentasjon av GL ( E ) er isomorf til en unik Schur-modul.

Symmetriske funksjoner

De tegnene av Schurs moduli (som representasjoner av GL ( E )) er symmetriske polynomer som kalles Schur polynomer , etter den russiske matematikeren Issai Schur . Youngs arrays gir en elegant måte å uttrykke disse polynomene på. I tillegg er det en ren kombinatorisk regel som bruker Youngs tabeller, og som gjør det mulig å spalte produktet av to Schur-polynomer. Dette innebærer spesielt at tabellene gjør det mulig å spalte tensorproduktet fra to irredusible representasjoner av GL ( E ) til en direkte sum av irreducible representasjoner.

Merknader og referanser

1. (i) Ian G. Macdonald , Symmetric functions and Hall polynomials , OUP , al.  "Oxford Mathematical Monographs",1979( ISBN  0-19-853530-9 ) anbefaler lesere som foretrekker fransk notasjon å lese denne boken "fra bunnen og opp i et speil".
2. Og venstre semi-standard matriser kan defineres som slike sekvenser; dette er hvordan Macdonald fortsetter 1979 , s.  4.
3. (i) Alain Lascoux Bernard Leclerc og Jean-Yves Thibon, "The plactic monoid" , i M. Lothaire , algebraisk Combinatorics på ord , UPC , al.  "Encyclopedia of Mathematics og dets Applications" ( N o  90)2002( ISBN  978-0-521-81220-7 , leses online ) , s.  164-196.
4. Lascoux, Leclerc og Thibon 2002 , s.  166.
5. (in) JS Frame, Gilbert B. Robinson og Robert M. Thrall, "  The hook graphs of the symmetric groups  " , Canadian Journal of Mathematics , vol.  6,1954, s.  316-324.
6. .
7. Gjennomgang av artikkelen av Novelli, Pak og Stoyanovskii i MathSciNet . Begrenset tilgang.
8. (in) Jason Bandlow, "  An elementary proof of the hook formula  " , The Electronic Journal for Combinatorics , vol.  15,2008( les online ).

Bibliografi

• (no) William Fulton , Young tableaux , Cambridge University Press , koll.  "London Mathematical Society elevtekster" ( N o  35)1997( ISBN  978-0-521-56144-0 og 978-0-521-56724-4 , matematiske anmeldelser  1464693 )
• (i) Donald E. Knuth , “  Permutasjoner, matriser og generaliserte unge tablåer  ” , Pacific Journal of Mathematics , vol.  34,1970, s.  709–727 ( ISSN  0030-8730 , matematiske anmeldelser  0272654 , les online )
• (no) Donald E. Knuth , The Art of Computer Programming , vol.  3: Sortering og søk ,1998, 2 nd  ed. [ detalj av utgaven ]
• (en) Bruce E. Sagan  (en) , The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , New York / Berlin / Heidelberg etc., Springer, coll.  "  GTM  " ( n o  203)2001, 2 nd  ed. , 238  s. ( ISBN  0-387-95067-2 )
• (no) Richard P. Stanley , Enumerative Combinatorics , vol.  2 [ detalj av utgaver ] ( online presentasjon )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">