MIT Combinatorics Seminar

Dual equivalence graphs, ribbon tableaux and Macdonald polynomials

Sami Assaf (UC Berkeley)

Friday, December 1, 2006   4:15 pm    Room 2-136


We introduce a new combinatorial construction, called a dual equivalence graph, based on Haiman's 1992 discovery of an equivalence relation on tableaux which is "dual" to jeu-de-taquin. We define a generating function on the vertices of such graphs and show that it is always Schur positive. We outline the construction of a graph on standard k-tuples of young tableaux which we prove is a dual equivalence graph for k <= 3. This gives a combinatorial description of the Schur coefficients of the ribbon tableaux generating functions introduced by Lascoux, Leclerc and Thibon. Recalling Haglund's monomial expansion for Macdonald polynomials, we conclude with a combinatorial formula for the Schur expansion of Macdonald polynomials indexed by a partition with at most 3 columns.