Tabelle di Young semistandard e corrispondenza Robinson-Schensted-Knuth

L’obiettivo di questa tesi è quello di presentare la corrispondenza di Robinson-Schensted-Knuth e alcune sue proprietà. Questa corrispondenza è importante perchè fornisce una corrispondenza biunivoca tra l’insieme delle coppie ordinate di tabelle di Young semistandard della stessa forma (P; Q) e l’insieme delle biparole di interi positivi in ordine lessicografico. Nel primo capitolo si forniscono le definizioni di base, la più importante delle quali è quella di tabella di Young semistandard. Ho poi descritto l’algoritmo principale relativo alle tabelle di Young, ossia l’algoritmo d’inserimento, il quale ci permette di inserire in una tabella T un intero per ottenere una nuova tabella. Nel secondo capitolo, descriviamo la corrispondenza di Robinson-Schensted-Knuth. Nel terzo capitolo, descriviamo le principali proprietà di questa corrispondenza, e in particolare un risultato fondamentale dovuto a M.P. Schützenberger, noto come il teorema di simmetria. Partendo dalla descrizione della dualità delle tabelle di Young e degli algoritmi di inserimento e di cancellazione, arriviamo a descrivere anche le relazioni elementari di Knuth e la Knuth-equivalenza tra parole. Seguono importanti corollari che descrivono le caratteristiche delle parole associate alla stessa tabella di inserimento. Infine, esprimeremo alcuni risultati ottenuti in forma matriciale.