DISSERTATION / DOCTORAL THESIS Titel der Dissertation / Title of the Doctoral Thesis “Cayley–Catalan Combinatorics of Affine Permutation Groups” verfasst von / submitted by Robin Sulzgruber MSc angestrebter akademischer Grad / in partial fulfilment of the requirements for the degree of Doktor der Naturwissenschaften (Dr. rer. nat.) Wien, 2017 / Vienna 2017 Studienkennzahllt.Studienblatt/ A796605405 degreeprogrammecodeasitappearsonthestudent recordsheet: Dissertationsgebietlt. Studienblatt/ Mathematik fieldofstudyasitappearsonthestudentrecordsheet: Betreutvon/Supervisor: Univ.-Prof.Dr.ChristianKrattenthaler Contents Table of Contents iii Acknowledgements v Abstract vii Zusammenfassung ix Chapter 0. Introduction 1 Chapter 1. Notation 5 1.1. Partitions 5 1.2. Lattice paths 6 1.3. Roots, hyperplanes and reflections 6 1.4. Affine permutations 9 1.5. Affine signed permutations 12 Chapter 2. Exploring the Catalan-cube 17 2.1. Dyck paths and Catalan numbers 17 2.2. Rational Catalan numbers 18 2.3. Cayley numbers and parking functions 20 2.4. Rational parking functions 22 2.5. The q,t-Catalan numbers 23 2.6. The q,t-Cayley numbers 27 2.7. Rational q,t-Catalan numbers 29 Chapter 3. Core partitions 31 3.1. Cores and the affine symmetric group 31 3.2. Affine inversions 37 3.3. Simultaneous core partitions 41 3.4. The skew-length statistic 43 Chapter 4. The finite torus 49 4.1. Coxeter–Catalan numbers 49 4.2. The finite torus 51 4.3. Lattice path models for the finite torus 52 4.4. p-stable elements of the affine Weyl group 57 4.5. The dinv-statistic 60 Chapter 5. The Shi arrangement 63 5.1. Non-nesting parking functions and the Shi arrangement 63 5.2. Lattice path models for non-nesting parking functions 65 iii iv CONTENTS 5.3. The area-statistic 71 5.4. Rational Shi tableaux 72 Chapter 6. The zeta map 83 6.1. The uniform zeta map 83 6.2. From area to dinv 85 6.3. Combinatorics in type C 87 n 6.4. Combinatorics in type D 97 n 6.5. Combinatorics in type B 108 n Bibliography 113 Index 117 Acknowledgements FirstandforemostIwanttothankChristianKrattenthalerwhoalwaysgavemethefreedomto pursuemyownideas,butatthesametimeprovidedadviseanddirectionwheneveritwasneeded. Thank you also for encouraging and making it possible for me to travel and visit conferences during my studies. I could not have hoped for a better advisor. I gained a lot from working and discussing with numerous people generously sharing their knowledgewithme. ThankyoutoCesarCeballos,TomDenton,IlseFischer,JimHaglund,Myrto Kallipoliti, Christoph Neumann, Vivien Ripoll, Carsten Schneider, Christian Stump, Marko Thiel, Nathan Williams and Meesue Yoo. I gratefully acknowledge the financial support from the Austrian Science Fund FWF in the framework of the special research program SFB F50. I would also like to thank the University of Vienna and in particular the Faculty of Mathematics. Throughout my time here I have experienced an environment that was both fascinating mathematically and very enjoyable in general. IcountmyselfveryluckybepartofalargegroupofawesomeyoungpeoplewhoworkedinVienna whileIwashere: Alex,Andrei,Cesar,Chen,Christoph,Daniel,Emma,Florian,Gwendal,Hans, Henri, Judith, Koushik, Lukas, Manjil, Marko, Meesue, Michael, Myrto, Sabine, Stephan, Ting, Tomack, Viviane, Vivien, Yvonne, Zhicong and Z´ofia. Thank you for drinks had, games played, riddling and travelling the world together! Finally, thankyoutoallmyMugglefriends(non-mathematicalfriends)andmyfamilyfortheir genuine interest in what a parking function might be! v Abstract Cayley–Catalan combinatorics refers to the study of combinatorial objects counted by (gener- alised)CatalannumbersorCayleynumbers. Examplesofclassicalcombinatorialobjectstreated in this thesis that fall into this category are Dyck paths, parking functions and core partitions. These objects turn out to be closely related to the group of affine permutations and their inver- sions. ManyinvolvedideascarryovertoarbitraryaffineWeylgroups. Exploringthisconnection wereviewthefinitetorus,theShiarrangementandnon-nestingparkingfunctions. Inparticular, we define new combinatorial models for these objects in terms of labelled lattice paths when the crystallographic root system is of classical type. Several combinatorial statistics on Catalan objects have been introduced to give combinatorial interpretations for polynomials appearing in representation theory or algebraic geometry. For example, Haglund’s bounce-statistic, Haiman’s dinv-statistic or Armstrong’s skew-length of a partitionhaveallbeenusedtodefineq-analoguesofCatalannumbers. Westrengthenandexpand on previously known symmetry properties of the skew-length statistic. The dinv-statistic is generalisedtoastatisticonthefinitetorus,allowingforanewdefinitionofq-Catalannumbersfor arbitraryWeylgroups. Furthermore,weextendthenotionofShitableauxtogiveageneralisation of the skew-length statistic for affine Weyl groups, thereby enabling us to give a combinatorial definition of rational q-Catalan numbers for Weyl groups. An important bijection in this field is the so called zeta map. The original zeta map is a bijectiononthesetofDyckpaths,however,itcanbegeneralisedtoauniformbijectionattached to any Weyl group. We prove that this bijection transforms the dinv-statistic on elements of the finite torus into the area-statistic on non-nesting parking functions. Furthermore, we develop the lattice path combinatorics of the zeta map for the infinite families of crystallographic root systems in analogy to the connection to Dyck paths when the Weyl group is the symmetric group. This leads to the discovery of two new bijections between ballot paths and lattice paths in a square, both of which are known to be counted by central binomial coefficients. vii Zusammenfassung Die Bezeichnung Cayley–Catalan Kombinatorik bezieht sich auf das Studium von kombina- torischen Objekten, die von (verallgemeinerten) Catalan-Zahlen oder Cayley-Zahlen abgez¨ahlt werden. Beispiele fu¨r klassische kombinatorische Objekte, die in dieser Dissertation behandelt werden und in diese Kategorie fallen, sind Dyck-Pfade, Parkfunktionen oder Kernpartitionen. Alle diese Objekte sind eng verwandt mit der Gruppe affiner Permutationen und deren Inver- sionen. Viele der zu beobachtenden Konzepte lassen sich auf allgemeine affine Weyl-Gruppen u¨bertragen. In diesem Zusammenhang besprechen wir den endlichen Torus, das Shi-Gefu¨ge und nichtverschachtelte Parkfunktionen. Insbesondere definieren wir in den F¨allen, in denen das zu- grundeliegendekristallographischeWurzelsystemvonklassischemTypist, neuekombinatorische Modelle fu¨r diese Objekte anhand von bezeichneten Gitterpunktwegen. Verschiedene kombinatorische Statistiken wurden auf Catalan-Objekten definiert, um Poly- nomen, dieinderDarstellungstheorieoderderalgebraischenGeometrieauftauchen, einekombi- natorische Bedeutung zu verleihen. Zum Beispiel wurden Haglunds bounce-Statistik, Haimans dinv-Statistik und Armstrongs Schiefl¨ange einer Zahlenpartition benutzt, um q-Analoga der Catalan-Zahlen zu definieren. Wir verfeinern und verallgemeinern bisher bekannte Symme- trieeigenschaften der Schiefl¨ange. Die dinv-Statisik wird zu einer Statistik auf den Elementen des endlichen Torus verallgemeinert. Dies erlaubt es uns q-Catalan-Zahlen fu¨r beliebige Weyl- Gruppen zu definieren. Zus¨atzlich erweitern wir den Begriff von Shi-Tafeln, um eine Verallge- meinerungderSchiefl¨angefu¨raffineWeyl-Gruppenzuerm¨oglichen. DadurchsindwirinderLage, eine kombinatorische Definition von rationalen q-Catalan-Zahlen fu¨r Weyl-Gruppen anzugeben. Eine wichtige Bijection in diesem Gebiet ist die sogenannte Zeta-Abbildung. Die urspru¨ngliche Zeta-Abbildung ist eine Bijektion auf der Menge der Dyck-Pfade, jedoch wurde sie einheitlich zu einer einer beliebigen Weyl-Gruppe zugeh¨origen Bijektion verallgemeinert. Wir beweisen, dassdieseBijektiondiedinv-StatistikaufdenElementendesendlichenTorusaufdasGebietder entsprechendennichtverschachteltenParkfunktionu¨berfu¨hrt. WeitersentwickelnwirinAnalogie zuderVerbindungzuDyck-PfadenimFalledersymmetrischenGruppedieGitterpunktwegskom- binatorik der Zeta-Abbildung fu¨r die unendlichen Familien von kristallographischen Wurzelsys- temen. Dies fu¨hrt zur Entdeckung von zwei neuen Bijektionen zwischen Abstimmungspfaden und Gitterpunktwegen, die einem Quadrat eingeschrieben sind, von welchen jeweils bekannt ist, dass sie von Zentralbinomialkoeffizienten abgez¨ahlt werden. ix CHAPTER 0 Introduction Three of the most ubiquitous sequences of numbers in combinatorics are the factorials n!, the Catalannumbers(cid:0)2n(cid:1)/(n+1)andtheCayleynumbers(n+1)n−1. Factorialscountpermutations n of an n-set which can be represented as bijections between n-sets, as linear orders of an n-set or as collections of labelled cycles. Catalan numbers count a wealth of combinatorial objects such asbinarytrees,Dyckpaths,non-crossingpartitions,non-crossingperfectmatchings,certainpat- tern avoiding permutations, rooted plane trees, triangulations of polygons and many more [70]. Cayleynumberscountmostobviouslymapsfroman(n−1)-settoan(n+1)-set, mostfamously labelled trees, but also parking functions and regions of the Shi arrangement among others. Itisoneofthebeautifulcoincidencesinalgebraiccombinatoricsthatthesenumbersarerelated to each other elegantly by way of a group G acting on a set X such that (cid:18) (cid:19) 1 2n #G=n!, #X =(n+1)n−1 and #{Gx:x∈X}= . n+1 n As we shall see, a convenient choice is to take the symmetric group G = S acting on the set n X =PF of parking functions. An integer vector with non-negative entries (f ,...,f )∈Nn is n 1 n called parking function if there exists a permutation σ ∈ S such that f < σ(i) for all i. For n i example, there are sixteen parking functions of length three. (cid:110) (cid:111) PF = (0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,2,0),(2,0,0),(0,1,1), 3 (1,0,1),(1,1,0),(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0) Clearly the symmetric group acts on the set of parking functions via permutation of entries. At this point the orbits {Gx:x∈X} are easily seen to be indexed by increasing parking functions, which can be identified with Dyck paths. There are five increasing parking functions of length three. (0,0,0) (0,0,1) (0,0,2) (0,1,1) (0,1,2) Of course there are other equivalent choices for G and X. The study of the parking function representation has given rise to a whole new branch in algebraic combinatorics. It connects a variety of topics in mathematics – from Macdonald poly- nomials, and symmetric functions in general [29, 19], and the representation theory of Weyl groups and related algebras [9, 33], to hyperplane arrangements [5], Hilbert schemes [41, 42] andknotinvariants[34]. Itisinpartresponsiblefortherevivalofclassicalcombinatorialobjects such as core partitions and abacus diagrams. Over the years Catalan numbers have been generalised in many different directions, which I prefer to view as dimensions. In this thesis the focus is on the following four dimensions. The first is the introduction of a rational parameter, which encompasses the introduction of a Fuß-parameter. Many of the objects counted by Catalan numbers listed above can be assigned 1