Algoritem RSK : delo diplomskega seminarja

Golob, Luka (author), Konvalinka, Matjaž (mentor)

Diplomska naloga podaja natančen dokaz bijektivnosti in simetrije algoritma RSK. Po dokazih predstavimo njegove posledice, med katerimi sta najbolj znani Cauchyjeva identiteta in zveza s permutacijami: $n! = \sum_{\lambda \vdash n} (f^\lambda)^2$. Preostala polovica naloge obravnava teorijo simetričnih funkcij. Za nekatere razrede simetričnih funkcij dokažemo, da tvorijo bazo, predvsem pa je tema naravnana k definiciji skalarnega produkta in dokazu, po katerem Schurove funkcije tvorijo ortonormirano bazo za definirani skalarni produkt.

• Language: Slovenian
• Keywords: algoritem RSK, simetrične funkcije, Schurove funkcije
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2022
• PID: 20.500.12556/RUL-138862
• UDC: 519.1
• COBISS.SI-ID: 119128323
• Publication date in RUL: 24.08.2022

Secondary language

• Language: English
• Title: RSK algorithm

Abstract

In this diploma thesis, we show that the RSK algorithm is bijective and has a symmetric property. Afterwards we present some of its corollaries, among which the most prominent ones are the Cauchy identity and the permutation formula: $n! = \sum_{\lambda \vdash n} (f^\lambda)^2$. The other half of the thesis develops the theory of symmetric functions. For some classes of functions we show that they form a basis. The main aim is to define a scalar product on symmetric functions and then to prove that Schur functions form an orthonormal basis.

• Keywords: RSK algorithm, symmetric functions, Schur functions