Dual equivalence graphs and a combinatorial proof of LLT and Macdonald positivity

Abstract

We make a systematic study of a new combinatorial construction called a dual equivalence graph. We axiomatize these graphs and prove that their generating functions are symmetric and Schur positive. By constructing a graph on ribbon tableaux which we transform into a dual equivalence graph, we give a combinatorial proof of the symmetry and Schur positivity of the ribbon tableaux generating functions introduced by Lascoux, Leclerc and Thibon. Using Haglund's formula for the transformed Macdonald polynomials, this also gives a combinatorial formula for the Schur expansion of Macdonald polynomials.

59 pages, 51 figures, now includes Maple code

References in corpus (1)

• A generalized Major index statistic

Cited by in corpus (12)

• Skew quasisymmetric Schur functions and noncommutative Schur functions
• Stanley symmetric functions and Peterson algebras
• A generalization of Newton's identity and Macdonald functions
• Fomin-Greene monoids and Pieri operations
• What makes a D_0 graph Schur positive?
• A combinatorial proof that Schubert vs. Schur coefficients are nonnegative
• Representation theory of the nonstandard Hecke algebra
• Combinatorial expansions in K-theoretic bases
• Type A-admissible cells are Kazhdan-Lusztig
• Rules of Three for commutation relations
• Coxeter-Knuth graphs and a signed Little map for type B reduced words
• Macdonald polynomials as characters of Cherednik algebra modules