Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Application of graph combinatorics to rational identities of type A. | Application of graph combinatorics to rational identities of type A Adrien Boussicault Universite Paris-Est LabInfo IGM 77454 Marne-la-Vallee Cedex 2 France boussica@ Valentin Feray LaBRI CNRS 351 cours de la liberation 33 400 Talence France feray@ Submitted Jul 13 2009 Accepted Nov 24 2009 Published Nov 30 2009 Mathematics Subject Classifications 05E99 05C38 Abstract To a word w we associate the rational function Tw n xwi xwi 1 -1. The main object introduced by C. Greene to generalize identities linked to the Murnaghan-Nakayama rule is a sum of its images by certain permutations of the variables. The sets of permutations that we consider are the linear extensions of oriented graphs. We explain how to compute this rational function using the combinatorics of the graph G. We also establish a link between an algebraic property of the rational function the factorization of the numerator and a combinatorial property of the graph the existence of a disconnecting chain . 1 Introduction A partially ordered set poset P is a finite set V endowed with a partial order. By definition a word w containing exactly once each element of V is called a linear extension if the order of its letters is compatible with P if a P b then a must be before b in w . To a linear extension w v1v2 . vn we associate a rational function 1 w xvi XV2 xV2 XV3 . . . xvn-1 Xvn THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R145 1 We can now introduce the main object of the paper. If we denote by L P the set of linear extensions of P then we define Tp by Tp E tw. B ackground The linear extensions of posets contain very interesting subsets of the symmetric group for example the linear extensions of the poset considered in the article BMB07 are the permutations smaller than a permutation n for the weak Bruhat order. In this case our construction is close to that of Demazure characters Dem74 . S. Butler and M. Bousquet-Melou characterize the permutations n corresponding to acyclic .
