Dual equivalence graphs, ribbon tableaux and Macdonald polynomials

Abstract

Abstract. We make a systematic study of a new combinatorial construction called a dual equivalence graph. We axiomatize such constructions and prove that the generating functions of such graphs are Schur positive. We construct a graph on k-ribbon tableaux which we conjecture to be a dual equivalence graph, and we prove the conjecture for k ≤ 3. This implies the Schur positivity of the k-ribbon tableaux generating functions introduced by Lascoux, Leclerc and Thibon. From Haglund’s formula for Macdonald polynomials, this has the further consequence of a combinatorial expansion of the transformed Macdonald-Kostka polynomials eKλµ, which we prove when µ is a partition with at most 3 columns. 1.