An analogue of the Robinson-Schensted-Knuth correspondence, growth diagrams, and non-symmetric cauchy kernels

Abstract

Prova-se uma restri c~ao de uma an aloga da correspond^encia de Robinson- Schensted-Knuth, para preenchimentos semistandard de linhas de horizonte aumentadas, da autoria de Mason, a multiconjuntos de c elulas em diagramas em escada, segundo a conven c~ao Francesa, possivelmente truncados por escadas mais pequenas nos cantos superior esquerdo ou inferior direito. A condi c~ao imposta nos pares de linhas de horizonte aumentadas com preenchimento semistandard e que o par de formatos, rearranjos um do outro, satisfa ca uma desigualdade na ordem de Bruhat, com respeito ao grupo sim etrico, onde um formato e limitado pelo outro em ordem reversa. Para tableaux de Young semistandard, a desigualdade signi ca que o par de chaves a direita e tal que uma chave e limitada pela evacua c~ao de Sch utzenberger da outra. Esta bijec c~ao e seguidamente usada para obter uma expans~ao n~ao sim etrica do kernel de Cauchy, sobre diagramas em escada ou diagramas em escada truncados, na base dos caracteres de Demazure do tipo A, e na base dos atomos de Demazure. Esta expans~ao implica uma outra, da autoria de Lascoux, sobre diagramas de Ferrers arbitr arios, quando especializada a diagramas em escada ou diagramas em escada truncados, e explicita, no ultimo, os tableaux de Young no cristal de Demazure via operadores elementares de bolha actuando em vectores de entradas inteiras n~ao negativas. Fomin introduziu uma apresenta c~ao em diagramas de crescimento para a correspond^encia de Robinson-Schensted, e van Leeuwen e Roby desenvolveramna. Krattenthaler usou a mesma abordagem para tratar preenchimentos de diagramas sujeitos a certas restri c~oes. Os diagramas de crescimento evitam opera c~oes de inser c~ao e tornam as simetrias transparentes. N os tamb em introduzimos nesta tese uma apresenta c~ao de diagramas de crescimento para a an aloga da correspond^encia de Robinson-Schensted Knuth referida acima. Isto e feito naturalmente via tableaux de Young reversos os quais est~ao em bijec c~ao com as linhas de horizonte aumentadas com preenchimentos semistandard. Enquanto, na primeira parte do nosso trabalho, a estrat egia foi Resumo v considerar o diagrama em escada mais pequeno contendo o diagrama truncado, e, no entanto, observado por Lascoux que a expans~ao n~ao sim etrica do kernel de Cauchy sobre diagramas de Ferrers arbitr arios, pode ser reduzida ao caso da expans~ao dos diagramas em escada, considerando para esse efeito o maior diagrama em escada contido no diagrama de Ferrers. De acordo com esta observa c~ao, usamos agora diagramas de crescimento convenientes para reduzir a expans~ao sobre diagramas de Ferrers arbitr arios a diagramas em escada, deslocando, para esse efeito, as c elulas que est~ao fora da maior escada para o seu interior. Isto e alcan cado interpretando a ac c~ao dos operadores de cristal em palavras como emparelhamentos e deslocamentos de c elulas marcadas com 1 no preenchimento 0-1 do nosso diagrama de crescimento, e converter, em seguida, a informa c~ao resultante para linhas de horizonte aumentadas com preenchimento semistandard. Com estas ferramentas obtemos uma prova combinat oria para a expans~ao n~ao sim etrica do kernel de Cauchy sobre diagramas de Ferres arbitr arios. Em particular, fornecemos, deste modo, uma outra prova combinat oria para a expans~ao do kernel Cauchy sobre diagramas em escada truncados, considerados na primeira parte do trabalho. A expans~ao n~ao sim etrica do kernel de Cauchy previamente obtida por Lascoux, sobre diagramas em escada, foi baseada na estrutura de grafos de cristal duplos, e a obtida por Fu e Lascoux apoiou-se em propriedades dos operadores de Demazure. No caso dos diagramas de Ferrers arbitr arios, esta foi deduzida algebricamente por Lascoux.

We prove a restriction of an analogue of the Robinson-Schensted-Knuth correspondence for semi-skyline augmented llings, due to Mason, to multisets of cells of a staircase, in French convention, possibly truncated by a smaller staircase at the upper left end corner, or at the bottom right end corner. The condition to be imposed on the pairs of semi-skyline augmented llings is that the pair of shapes, rearrangements of each other, satis es an inequality in the Bruhat order, w.r.t. the symmetric group, where one shape is bounded by the reverse of the other. For semi-standard Young tableaux the inequality means that the pair of their right keys is such that one key is bounded by the Sch utzenberger's evacuation of the other. This bijection is then used to obtain an expansion formula of the non-symmetric Cauchy kernel, over staircases or truncated staircases, in the basis of Demazure characters of type A, and the basis of Demazure atoms. The expansion implies a Lascoux's expansion formula over arbitrary Ferrers shapes, when specialised to staircases or truncated staircases, and make explicit, in the latter, the Young tableaux in the Demazure crystal by interpreting Demazure operators via elementary bubble sorting operators acting on weak compositions. Fomin has introduced a growth diagram presentation for the Robinson- Schensted correspondence and van Leeuwen and Roby developed it further. Krattenthaler uses the same approach to treat llings of diagrams under certain restrictions. The growth diagram approach avoids insertion operations and makes symmetries transparent. We also introduce a growth diagram presentation for the analogue of the Robinson-Schensted-Knuth correspondence. This is done in a natural way via reverse semi-standard Young tableaux which are in bijection with semi-skyline augmented llings. While our strategy, in the rst part of our work, is to consider the smallest staircase containing the truncated shape, it is however observed by Lascoux that the Cauchy kernel expansion, over an arbitrary Ferrers shape, can be recovered from the expansion on staircases, by considering the biggest staircase inside the Ferrers Abstract iii shape. The strategy, in the last chapter, is then to use a convenient growth diagram to reduce the expansion, over arbitrary Ferrers shapes, to staircases by moving the cells outside the biggest staircase into inside. This is achieved by interpreting the action of crystal operators, on words, as matchings and slides of cells marked with 1 in the 01- lling of our growth diagram, and, then, convert the resulting information to semi-skyline augmented llings. With these tools we nd a combinatorial proof for the Lascoux's non-symmetric Cauchy kernel expansion over arbitrary Ferrers shapes. In particular, this a ords another combinatorial proof for strict truncated staircases, considered in the rst part of our work. A previous expansion of the non-symmetric Cauchy kernel, over staircases, was given by Lascoux, based on the structure of double crystal graphs, and, by Fu and Lascoux, relying on Demazure operators properties. The expansion, over an arbitrary Ferrers shape, was derived by Lascoux algebraically