Contents Preface vii Chapter 1. Introduction to q-Analogues and Symmetric Functions 1 Permutation Statistics and Gaussian Polynomials 1 The Catalan Numbers and Dyck Paths 6 The q-Vandermonde Convolution 8 Symmetric Functions 10 The RSK Algorithm 17 Representation Theory 22 Chapter 2. Macdonald Polynomials and the Space of Diagonal Harmonics 27 Kadell and Macdonald’s Generalizations of Selberg’s Integral 27 The q,t-Kostka Polynomials 30 The Garsia-HaimanModules and the n!-Conjecture 33 The Space of Diagonal Harmonics 35 The Nabla Operator 37 Chapter 3. The q,t-Catalan Numbers 41 The Bounce Statistic 41 Plethystic Formulas for the q,t-Catalan 44 The Special Values t=1 and t=1/q 47 The Symmetry Problem and the dinv Statistic 48 q-Lagrange Inversion 52 Chapter 4. The q,t-Schr¨oder Polynomial 59 The Schr¨oder Bounce and Area Statistics 59 Recurrences and Explicit Formulae 62 The Special Value t=1/q 65 The Delta Operator 68 The Schr¨oder dinv Statistic 70 The Limit as d→∞ 73 Chapter 5. Parking Functions and the Hilbert Series 77 Extension of the dinv Statistic 77 An Explicit Formula 79 The Statistic area′ 82 The pmaj Statistic 82 The Cyclic-Shift Operation 85 Chapter 6. The Shuffle Conjecture 91 v vi CONTENTS A Combinatorial Formula for the Character of the Space of Diagonal Harmonics 91 Path Symmetric Functions and LLT Polynomials 92 Superization 99 The Fermionic Formula 101 Skewing, Balanced Paths, and Hall-Littlewood Polynomials 103 The m-parameter 107 Chapter 7. The Proof of the q,t-Schr¨oder Theorem 113 Summation Formulas for Generalized Skew and Pieri Coefficients 113 The Proof 119 Some Related Results 120 Appendix A. The Combinatorics of Macdonald Polynomials 123 The Monomial Statistics 123 Proof of the Formula 125 Consequences of the Formula 129 Nonsymmetric Macdonald Polynomials 135 The Genesis of the Macdonald Statistics 139 Appendix B. The Loehr-WarringtonConjecture 141 The Conjecture 141 Expansion into LLT polynomials 144 Appendix C. Solutions to Exercises 147 Chapter 1 147 Chapter 2 149 Chapter 3 152 Chapter 4 154 Chapter 5 156 Chapter 6 157 Chapter 7 159 Appendix A 160 Appendix B 162 Bibliography 163 Preface This book is an expanded version of lecture notes for a topics course given by the authoratthe UniversityofPennsylvaniaduringthe springof2004onthe com- binatorics of the q,t-Catalannumbers and the space of diagonalharmonics. These subjectsarecloselyrelatedtothestudyofMacdonaldpolynomials,whichareanim- portantfamilyofmultivariableorthogonalpolynomialsintroducedbyMacdonaldin 1988withapplicationstoawidevarietyofsubjectsincludingHilbertschemes,har- monic analysis, representation theory, mathematical physics, and algebraic combi- natorics. Manywonderfulresultsaboutthesepolynomialsfromanalytic,algebraic, and geometric viewpoints have been obtained, but the combinatorics behind them had remained rather impenetrable. Toward the end of the spring 2004 semester the author, inspired primarily by new combinatorial identities involving diagonal harmonics discussed in Chapter 6 of this book, was led to a combinatorialformula for Macdonald polynomials. The discovery of this formula, which was proved in subsequentjointworkwithMarkHaimanandNickLoehr,hasresultedinavolume of broader interest, as in Appendix A we include a discussion of the formula, its proof, and the nice applications it has to the theory of symmetric functions. Amongtheseapplicationswemightdrawthereader’sattentiontotheshort,el- egantproofinAppendixAofLascouxandSchu¨tzenberger’s“cocharge”theoremon Hall-Littlewoodpolynomials,afundamentalresultinthetheoryofsymmetricfunc- tionswhoseoriginalproofwasneithershortnorelegant. Anotherapplicationofthe combinatorial formula is a way of writing the Macdonald polynomial as a positive sum of LLT polynomials, which are symmetric functions introduced by Lascoux, Leclerc,andThibon. This decompositionis especiallysignificantinview oftwore- cent preprints, one by Grojnowski and Haiman and another by Sami Assaf, which contain proofs that the coefficients of LLT polynomials, when expanded in terms of Schur functions, are positive. Although Grojnowski and Haiman’s proof uses Kazhdan-Lusztig theory and algebraic geometry, Assaf’s proof is a self-contained 21 page combinatorial argument. Thus we now have an accessible, combinatorial proof that Macdonald polynomials are Schur positive. (This Macdonald positivity result was first proved in 2000 by Haiman using properties of the Hilbert scheme from algebraic geometry.) The attempt to understand the combinatorics of Mac- donaldpolynomialsiswhatledGarsiaandHaimantostudydiagonalharmonicsand has been the motivation behind quite a bit of research in algebraic combinatorics over the last 20 years. Chapter 1containssome well-knownintroductorymaterialonq-analoguesand symmetric functions. Chapter 2 gives some of the historical background and basic theorems involving Macdonald polynomials and diagonal harmonics, including a discussion of how a certain S action on the space of diagonal harmonics leads to n a number of beautiful and deep combinatorialproblems. Chapters 3−6 deal with vii viii PREFACE the combinatorics of the character induced by this action. The most fundamental object in this subject is the q,t-Catalan numbers, the focus of Chapter 3. From there we move on to a study of the q,t-Schr¨oder numbers in Chapter 4, which are a bigraded version of the multiplicity of a hook shape in the character. Chapter 5 deals with a (conjectured) expression for the bigraded Hilbert series, which has an elegant expression in terms of combinatorial objects called parking functions. In Chapter 6 we study the “shuffle conjecture” of Haiman, Loehr, Remmel, Ulyanov, and the author which gives a combinatorial prediction, parameterized in terms of parking functions, for the expansion of the character into monomials. This conjectureincludesallofthe resultsandconjecturesfromChapters3−5asspecial cases. Chapter 7 consists of an exposition of the proof of the broadest special case of this conjecture that we can prove, that of hook shapes. The proof involves themanipulationoftechnicalsymmetricfunctionidentitiesinvolvingplethysmand Macdonald polynomials. These identities are rather difficult to learn about from reading journal articles, and it is hoped this chapter will be a useful guide to readers interested in learning these subjects. Appendix B contains a discussion of an amazing extension of the shuffle conjecture recently proposed by Loehr and Warrington. Therearehomeworkexercisesinterspersedthroughoutthetext,instrategically chosen locations, to help the reader absorb the material. Solutions to all the ex- ercises are given in Appendix C. The book is meant to have value either as a text for a topics course in algebraic combinatorics, a guide for self-study, or a reference book for researchers in this area. The author would like to thank Mahir Can, Nick Loehr, Sarah Mason, Jaren Smith, Chunwei Song, Greg Warrington, and the other students and postdocs at- tending the course at Penn in the spring of 2004 for many helpful comments on the exposition of the material. In addition he would like to thank Laura Stevens and Sami Assaf for reading through the text and providing a list of errata. The authorisalsothankfulforthesupportandencouragementofEdwardDunneofthe AMS editorial staff, who first suggested the author write this book after hearing an address by the author on this subject at the AMS sectionalmeeting in Orlando in November 2002. During the course of working on this book, the author was supported by NSA Grant #02G-193 and NSF Grant DMS 0553619. James Haglund