Autor(es):
Gomes, Filipe Jorge Matos Dias 
Data: 2014
Identificador Persistente: http://hdl.handle.net/10451/11734
Origem: Repositório da Universidade de Lisboa
Assunto(s): Partições; Quadros de Young; Conjuntos parcialmente ordenados; Algoritmos combinatórios; Permutações; Diagramas de crescimento; Teses de mestrado - 2014
Descrição
Tese de mestrado em Matemática, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2014 O estudo dos quadros de Young, durante o século XX, levou ao desenvolvimento de vários algoritmos combinatórios, como a correspondência de Robinson-Schensted e o jeu de taquin de Schützenberger. Algumas propriedades destes algoritmos, especialmente aquelas que dizem respeito a aspectos de simetria, tornam-se mais claras quando os algoritmos são reformulados noutro contexto. No final do século XX, Fomin desenvolveu a noção de diagrama de crescimento, com o intuito de estudar estes algoritmos combinatórios, tornando mais transparentes as suas propriedades fundamentais. No estudo de diagramas de crescimento, os resultados de Greene e Kleitman sobre conjuntos parcialmente ordenados assumem um papel central; o teorema da dualidade de Greene para conjuntos parcialmente ordenados finitos é especialmente relevante neste contexto.
O principal objectivo desta dissertação é a utilização de diagramas de crescimento para estudar as principais propriedades de alguns algoritmos combinatórios, bem como o desenvolvimento das ferramentas necessárias para este fim. Nesta dissertação, após uma apresentação sumária das noções básicas sobre conjuntos parcialmente ordenados, partições e quadros de Young, são apresentados em detalhe os resultados de Greene e Kleitman sobre famílias de cadeias e anticadeias em conjuntos parcialmente ordenados finitos. Demonstramos o teorema da dualidade de Greene e examinamos algumas das suas consequências mais relevantes, com o objectivo de relacionar diagramas de Young com ideais de ordem de conjuntos parcialmente ordenados. Em seguida, apresentamos as versões clássicas de alguns algoritmos combinatórios envolvendo quadros de Young: a correspondência de Robinson-Schensted, a correspondência RSK, o jeu de taquin de Schützenberger e a evacuação. Estes algoritmos são posteriormente reformulados recorrendo a diagramas de crescimento, tirando partido das ferramentas desenvolvidas com o auxílio do teorema da dualidade de Greene. As propriedades fundamentais destes algoritmos são demonstradas no último capítulo, particularmente as suas propriedades de simetria e o efeito de transformações de uma permutação nos quadros de Young que lhe correspondem pelo algoritmo de Robinson-Schensted. The study of Young tableaux, during the twentieth century, has led to the development of several combinatorial algorithms, such as the Robinson-Schensted correspondence and Schützenberger's jeu de taquin. Some properties of these algorithms, especially those that concern symmetry, become clearer when the algorithms are reformulated in another context. At the end of the twentieth century, Fomin has developed the notion of growth diagram, with the purpose of studying these combinatorial algorithms, making their fundamental properties more transparent. In the study of growth diagrams, Greene and Kleitman's results on finite posets play a central part; Greene's duality theorem for finite posets is especially relevant in this context. Our main goal with this thesis is the study of properties of combinatorial algorithms using growth diagrams, as well as the development of the necessary tools for the accomplishment of this end. In this thesis, after a brief presentation of the basic notions concerning posets, partitions and Young tableaux, we present in detail Greene and Kleitman's
results on antichain and chain families in finite posets. We prove Greene's duality theorem and examine some of its most important consequences, with the purpose of connecting Young diagrams with order ideals of finite posets. Afterwards, we present the classical versions of some combinatorial algorithms involving Young tableaux: the Robinson-Schensted correspondence, the RSK correspondence, Schützenberger's jeu de taquin and evacuation. These algorithms are then recast in the context of growth diagrams, taking advantage of the tools developed using Greene's duality theorem. The fundamental properties of these algorithms are proved in the last chapter, especially their symmetry properties and those that concern the effect of transformations of a permutation on the Young tableaux that Robinson-Schensted's algorithm associates with it.
