Hajnal Péter: Robinson-Schensted-megfeleltetés |
|
|
|
Péntek, 5. Október 2012, 10:00
|
|
A címben leírt megfeleltetés tulajdonképpen n elem (n! darab) permutációjának kódolása egy Young-tableau-párral. A Young-tableau egy egész szám partíciójának Young-diagramjában egy számozás úgy, hogy minden mezõ száma nagyobb legyen a tõle ÉNy-ra lévõ mezõkbe írt számoknál. Nem kell megijedni, a fogalmak szépek, elemiek és mindent elmondok elõismeret feltételezése nélkül.
A megfeleltetés egy reprezentációelméletbõl eredõ azonosság kombinatorikus bizonyítása. A megfeleltetés leírása meglepõen összetett, tulajdonságainak bizonyítása szép, de nehéz. Ezt ismertetem és a maradék idõben kitérek a mefeleltetés kapcsolatára a matematika más ágaival. A megfeleltetés egy kiterjesztését Knuth végezte el. Leírását részletesen tárgyalja az The Art of Computer Programming könyvének harmadik kötetében. |
Hely : Farkas terem |
Vissza
JEvents v3.1.8 Stable
Copyright © 2006-2013