Operators on compositions and noncommutative SchurfunctionsbyVasu TewariB.Tech., National Institute of Technology, Tiruchirappalli, 2008M.Sc. in Mathematics, The University of British Columbia, 2011a thesis submitted in partial fulfillmentof the requirements for the degree ofDoctor of Philosophyinthe faculty of graduate and postdoctoral studies(Mathematics)The University of British Columbia(Vancouver)August 2015c© Vasu Tewari, 2015AbstractIn this thesis, we study a natural noncommutative lift of the ubiquitous Schur functions,called noncommutative Schur functions. These functions were introduced by Bessenrodt,Luoto and van Willigenburg and resemble Schur functions in many regards. We prove somenew results for noncommutative Schur functions that are analogues of classical results, anddemonstrate that the resulting combinatorics in this setting is equally rich.First we prove a Murnaghan-Nakayama rule for noncommutative Schur functions. Inother words, we give an explicit combinatorial formula for expanding the product of a non-commutative power sum symmetric function and a noncommutative Schur function in termsof noncommutative Schur functions. In direct analogy to the classical Murnaghan-Nakayamarule, the summands are computed using a noncommutative analogue of border strips, andhave coefficients ±1 determined by the height of these border strips. The rule is proved byinterpreting the noncommutative Pieri rules for noncommutative Schur functions in termsof box adding operators on compositions.We proceed to give a backward jeu de taquin slide analogue on semistandard reversecomposition tableaux. These tableaux were first studied by Haglund, Luoto, Mason and vanWilligenburg when defining quasisymmetric Schur functions. Our algorithm for performingbackward jeu de taquin slides on semistandard reverse composition tableaux results in anatural operator on compositions that we call the jdt operator. This operator in turn givesrise to a new poset structure on compositions whose maximal chains we enumerate. As anapplication, we also give new right Pieri rules for noncommutative Schur functions that usethe jdt operators, in contrast to the left Pieri rules given by Bessenrodt, Luoto and vanWilligenburg.iiPrefaceThis thesis contains the results from two manuscripts written by the author: [44] and [45].Chapter 3 is based on the manuscript [44] while Chapter 4 is based on the manuscript [45].iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Symbols and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Sym, QSym and NSym . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 Combinatorial preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.1 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.2 Semistandard reverse tableaux . . . . . . . . . . . . . . . . . . . . . . 72.1.3 Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.1.4 Semistandard reverse composition tableaux . . . . . . . . . . . . . . 92.2 Symmetric functions and Schur functions . . . . . . . . . . . . . . . . . . . . 122.2.1 The Murnaghan-Nakayama rule . . . . . . . . . . . . . . . . . . . . . 132.2.2 Jeu de taquin slides on SSRTs . . . . . . . . . . . . . . . . . . . . . . 152.2.3 Rectification of SRTs . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2.4 The classical Pieri rules . . . . . . . . . . . . . . . . . . . . . . . . . 202.3 Quasisymmetric functions and quasisymmetric Schur functions . . . . . . . . 212.4 Noncommutative symmetric functions and noncommutative Schur functions . 232.4.1 Noncommutative Schur functions . . . . . . . . . . . . . . . . . . . . 25iv2.5 Operators on compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5.1 Box adding operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5.2 Box removing operators . . . . . . . . . . . . . . . . . . . . . . . . . 292.5.3 Jeu de taquin operators . . . . . . . . . . . . . . . . . . . . . . . . . 292.6 Statement of main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.6.1 A noncommutative Murnaghan-Nakayama rule . . . . . . . . . . . . . 302.6.2 Jeu de taquin and right Pieri rules . . . . . . . . . . . . . . . . . . . 322.6.3 Backward jeu de taquin slides for SSRCTs . . . . . . . . . . . . . . . 332.6.4 Right Pieri rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 A Murnaghan-Nakayama rule for noncommutative Schur functions . . . 383.1 Box adding operators, Pieri rules and reverse hookwords . . . . . . . . . . . 383.1.1 SRCTs associated with sequence of box adding operators . . . . . . . 383.1.2 Pieri rules using box adding operators . . . . . . . . . . . . . . . . . 393.1.3 Reverse hookwords and multiplication by r(1k,n−k) . . . . . . . . . . . 403.2 Multiplication by noncommutative power sums in terms of box adding operators 423.3 The Murnaghan-Nakayama rule for noncommutative Schur functions . . . . 434 Jeu de taquin and right Pieri rules . . . . . . . . . . . . . . . . . . . . . . . 554.1 Proof of validity of algorithm µi . . . . . . . . . . . . . . . . . . . . . . . . . 554.1.1 Skew shape after µ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.2 Backward jeu de taquin slides for SSRCTs of skew shape . . . . . . . . . . . 734.3 A new poset on compositions . . . . . . . . . . . . . . . . . . . . . . . . . . 784.3.1 Growth words and SRTs . . . . . . . . . . . . . . . . . . . . . . . . . 784.3.2 A poset on compositions . . . . . . . . . . . . . . . . . . . . . . . . . 794.3.3 Inner shape after a sequence of slides . . . . . . . . . . . . . . . . . . 834.4 Right Pieri rules for noncommutative Schur functions . . . . . . . . . . . . . 854.5 Some properties of our Robinson-Schensted variant . . . . . . . . . . . . . . 875 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92vList of Symbols and Notationsα compositionα˜ underlying partition of αβ/α skew reverse composition shapeχ forgetful mapcomp composition associated to a set, or to the descent set of a tableauCRHWn set of connected reverse hookwordsδi,j 1 if i = j and 0 otherwiseDes descent set of a tableaud box removing operatore(T ) evacuation of a tableauFα fundamental quasisymmetric functionhλ complete homogeneous symmetric functionhα complete homogeneous noncommutative symmetric functionht height statistic associated to a border strip, or an nc border stripjdti backward jeu de taquin slide on SSRTs from column iλ partitionλ/µ skew shapeLc reverse composition posetviµi backward jeu de taquin slide on SSRCTs from column iNSym Hopf algebra of noncommutative symmetric functionspλ power sum symmetric functionΨα noncommutative power sum symmetric functionQSym Hopf algebra of quasisymmetric functionsrect(T ) rectification of a tableauρα bijection between SSRCT and SSRTRHWn set of reverse hookwordsrα noncommutative ribbon Schur functionset set associated to a compositionsh shape of a tableausλ Schur functionSα quasisymmetric Schur functionsα noncommutative Schur functionSRT standard reverse tableauSSRT semistandard reverse tableauSRCT standard reverse composition tableauSSRCT semistandard reverse composition tableausupp(β/α) support of a skew reverse composition shapeSym Hopf algebra of symmetric functionsSn symmetric groupT semistandard reverse tableauτ semistandard reverse composition tableauτα canonical standard reverse composition tableaut box adding operatoru jeu de taquin operatorwT column reading word of a tableauviixT monomial associated to a tableauY Young’s lattice∅ empty composition or partition` is a partition of is a composition of| | size of a composition or partition, or size of a skew shapelc cover relation in Lclr cover relation in Rc≺ cover relation in Y4 refines⊆ subset ofviiiAcknowledgmentsFirst and foremost I want to thank my advisor Steph van Willigenburg for her preciousguidance and invaluable support she has provided over the course of my graduate career.She introduced me to the beautiful field of algebraic combinatorics, carefully handpickedproblems I could work on and learn from, made research immense fun, was always availableand more than happy to help, and has been very generous with her ideas and her insightfulsuggestions. I have been lucky to have a mentor like her and am extremely grateful for herconstant encouragement, fantastic and extremely well-thought-out advice on all things, andher unbridled enthusiasm at my latest theorem (however small a result it might be). Thanksin particular for her tireless and extremely careful scrutiny of my drafts time and again, andfor all her suggestions and corrections that went a long way in improving them substantially.It has always been heartening to know that I had someone of her wisdom, experience, andexpertise to go to if I was ever in doubt and invariably on such occasions her views and advicenot only banished my doubts but really picked me up and rejuvenated me. Through yearsof meetings, conversations, emails and patient instruction she has contributed singularly tomy development as a mathematician. I owe her an immense debt of gratitude.Thanks also go to other mathematicians who have provided me invaluable opportunitiesto learn and who have contributed to my research, most notably Edward Richmond, ChristineBessenrodt, Andrew Rechnitzer, and Jozsef Solymosi. I would also like to thank JozsefSolymosi for chairing my candidacy exam; Jim Bryan and Andrew Rechnitzer for servingon my PhD committee; Mike Bennett, Will Evans and Brian Warriner for serving on myexamining committee; and my external examiner Marcelo Aguiar. Thanks also go to themfor helpful guidance on a number of occasions.The mathematics department staff at UBC has helped make my journey through gradschool hassle-free and my sincere thanks go to them.I would also like to acknowledge the OEIS and Sage-Combinat (and the entire communitydeveloping it); the results in this thesis could not have been obtained without these resources.ixThanks go to Udayan Prajapati and Hemalatha Thiagarajan for their advice and helpduring my undergraduate years. I would not be pursuing mathematics were it not for them.My friends have brought me great joy and have helped me keep my head. I would liketo thank Aabu for being extraordinarily cuddly, Ponyo for being fishy in the sea, Nair forshowing up every single time (and not saying much thereafter), Potter for reporting onall movement in India (tectonic plates included), Gaindu for Master Shifu-esque wisdomimparted in inimitable style, Biru for the music, Guru for hospital visits, Gadhadhar forhospitality in Boston, Punti for song and dance, Pappu for that serious demeanour, Chomand Chacha for compski fun, Golu for car rides, Gandhi for all the laughs and sprinting forbuses, Dr. G and Hesam for helping me find my feet, GRay for culinary skills and Fridaymovies, Dr. G Jr. for the time spent playing pool and reserved 24 (and for taking a seatwhen I asked him to), Fgra for years of psychotherapy during short breaks that workedwonders, Myrto for asking hard questions and ensuing philosophical discussions that endedwith harder questions, Burbur for seething with rage at all things immaterial, Mundo forthrowing a great party every two years and deadpan delivery, Tom for the fantastic companyduring conferences and finding the best food in town, Maxime for fun conversations overdrinks, Terry for hospitality in Victoria, and Nt for whining about how Mason bees brokehis trance.Finally I would like to thank my sister, mother, and father for all their love, help andunwavering support.xDedicationI dedicate this thesis to my sister Stuti.xiChapter 1IntroductionThe Hopf algebra of symmetric functions, denoted by Sym, is a central object in algebraiccombinatorics and its most important linear basis is that of Schur functions sλ for all parti-tions λ. The ubiquity and importance of Schur functions can be gauged from the numerousways of defining them. For example, when interpreting symmetric functions in the represen-tation theory of symmetric groups, Schur functions correspond to irreducible representations[39]. Another link to representation theory is that Cauchy’s quotient of alternants formulafor Schur functions is a specialization of Weyl’s character formula. In algebraic geome-try, the cohomology rings of Grassmanians can be interpreted as quotients of polynomialrings so that Schubert classes correspond to Schur functions, and in this setting, the famedLittlewood-Richardson coefficients arise as structure constants expressing cup products [12].Finally, the combinatorial way of defining Schur functions, attributed to Littlewood [28], isto describe sλ as a generating function for semistandard reverse tableaux.Another key basis of Sym is the basis of power sum symmetric functions pλ for all parti-tions λ. The transition matrix between the two bases mentioned gives us the character tableof the symmetric group, which can also be computed combinatorially using the Murnaghan-Nakayama rule [42, Section 7.17]. This rule additionally gives a combinatorial formula forcomputing the product of a power sum symmetric function and a Schur function in terms ofSchur functions.Sym is a Hopf subalgebra of QSym, the Hopf algebra of quasisymmetric functions.Quasisymmetric functions are refinements of symmetric functions and were introduced byGessel [14] in his study of P -partitions. They can also be realized as invariants under aquasisymmetrizing action of the symmetric group [21]. Since its introduction, there has beenmuch activity surrounding QSym, and quasisymmetric functions have found applications in1areas such as combinatorial Hopf algebras [1, 9], card shuffling [11], permutation enumeration[15], discrete geometry [5], and representation theory [24]. Given the intimate connectionbetween Sym and QSym, a key line of inquiry is the existence of a Schur-like basis forQSym, that is, a basis of QSym that refines the algebraic and combinatorial properties ofthe basis of Schur functions.A prominent candidate, introduced by Haglund, Luoto, Mason and van Willigenburg [17],is the basis of quasisymmetric Schur functions Sα where α runs over all compositions. Thequasisymmetric Schur function Sα, much like a Schur function, is obtained as a generatingfunction for semistandard reverse composition tableaux, and its original definition was mo-tivated by the combinatorics of Macdonald polynomials [16]. Furthermore, these functionsnaturally refine Schur functions and many of their combinatorial properties [29].Equally interesting phenomena happen when we consider the Hopf algebra dual to QSym.This is the Hopf algebra of noncommutative symmetric functions, denoted by NSym, intro-duced in the seminal paper [13]. In addition to being the Hopf dual to QSym, NSym affordsSym as a quotient. Thus, it is intimately connected to the two Hopf algebras introducedearlier and provides an alternative route to establishing new results in Sym and QSym,with the noncommutativity offering a unique perspective on existing results. Noncommu-tative symmetric functions and their relations with a host of generalizations of symmetricfunctions have been a subject of intense study, as is evident from [6, 7, 8, 23, 24, 25].Taking the dual basis corresponding quasisymmetric Schur functions in NSym, we obtainthe basis of noncommutative Schur functions introduced in [4]. As the name suggests,these functions are noncommutative lifts of classical Schur functions, and resemble them bypossessing properties that are noncommutative analogues of Pieri rules, Kostka numbers, andthe Littlewood-Richardson rule [4]. They also have a representation-theoretic significanceas they can be identified as noncommutative irreducible characters of the symmetric group[48].In this thesis, we strengthen the connection between noncommutative Schur functionsand classical Schur functions by supplementing already existing results with analogues ofthe Murnaghan-Nakayama rule, jeu de taquin, and classical Pieri rules. We briefly outlineour results next and the full statements can be found in Section 2.6. In Chapter 3 of thisthesis, we consider the problem of finding an analogue of the classical Murnaghan-Nakayamarule. As mentioned earlier, the classical rule [32, 33] is a combinatorial procedure to computethe character table of the symmetric group. The combinatorial objects involved, which aidthe said computation, are called border strips. An alternate description of the Murnaghan-2Nakayama rule is that it gives an explicit combinatorial description of the expansion of theproduct of a power sum symmetric function pk, where k is a positive integer, and a Schurfunction sµ as a sum of Schur functionspk · sµ =∑λ(−1)ht(λ/µ)sλ, (1.1)where the sum is over all partitions λ such that the skew shape λ/µ is a border strip of sizek, and ht(λ/µ) is a certain statistic associated with the border strip λ/µ.To obtain our noncommutative analogue to the result above, we expand the product Ψr·sαin the basis of noncommutative Schur functions. Here Ψr denotes the noncommutative powersum symmetric function of the first kind, indexed by a positive integer r, while sα denotesthe noncommutative Schur function indexed by a composition α. The main result we proveis that, much like (1.1), we have an expansionΨr · sα =∑β(−1)ht(β//α)sβ, (1.2)where the sum is over certain compositions β such that the skew reverse composition shapeβ/α gives rise to a noncommutative analogue of a border strip of size r, and ht(β/α) is acertain statistic similar to ht(λ/µ) in (1.1). The box adding operators on compositions thatwe introduce in Chapter 2, and that are reminiscent of those in [2, 10], will be fundamentalto deriving (1.2).In Chapter 4 of this thesis, we introduce an analogue of a combinatorial procedure, calledjeu de taquin, for semistandard reverse composition tableaux and study the implicationsin the setting of NSym. Classically, jeu de taquin is a set of sliding rules defined onsemistandard Young tableaux (or semistandard reverse tableaux) that preserves the propertyof being semistandard while changing the underlying shape. This procedure is of utmostimportance in algebraic combinatorics, representation theory and algebraic geometry. It wasintroduced by Schu¨tzenberger [40], and its many remarkable properties have been studiedin depth since [12, 38, 42]. The procedure plays a crucial role in the combinatorics ofpermutations and Young tableaux, with deep links to the Robinson-Schensted algorithmand the plactic monoid [26]. One of the most important applications of Schu¨tzenberger’s jeude taquin is in giving a combinatorial rule for computing the induced tensor product of tworepresentations of the symmetric group, commonly called the Littlewood-Richardson rule.Analogues of jeu de taquin have been found for shifted tableaux [19, 37], Littelmann’s3crystal paths [27], increasing tableaux [46], edge labeled Young tableaux [47] and d-completeposets [35, 36]. Procedures such as promotion and evacuation, which are consequences ofjeu de taquin and important in their own right, have also been studied [34, 43]. Recently,an infinite version of jeu de taquin has been studied for infinite Young tableaux [41].Our focus here is on semistandard reverse composition tableaux and we give an algorithmfor performing backward jeu de taquin slides on them. Subsequently, we use this algorithmto give right Pieri rules. To give the aforementioned results context, we will now supplysome background. A special case of the noncommutative Littlewood-Richardson rule provedin [4] is a noncommutative analogue of the classical Pieri rules, which we will call the leftPieri rules. It corresponds to expanding the product of noncommutative Schur functionss(n) · sα and s(1,...,1) · sα in the basis of noncommutative Schur functions, where n denotes apositive integer and α denotes a composition. Given that we are computing products in anoncommutative Hopf algebra, it is natural to consider the products sα · s(n) and sα · s(1,...,1).The statement of the noncommutative Littlewood-Richardson rule in [4], which allows us tocompute the aforementioned products, requires the rectification of standard reverse tableauxand a map defined by Mason in [31], denoted by ρ, which links semistandard reverse tableauxand semistandard reverse composition tableaux. One could ask whether it is possible toeliminate the use of Mason’s map and introduce an analogue of rectification for semistandardreverse composition tableaux. This was achieved by Bechard in [3]. For what we aspire tocompute, it is preferable to consider a procedure that is the inverse of Bechard’s rectification.Our algorithm for performing backward jeu de taquin slides on SSRCTs is precisely such aprocedure.The organization of this thesis is as follows. Chapter 2 introduces the notation anddefinitions necessary for stating our main results: Section 2.1 defines combinatorial objectssuch as partitions, compositions, diagrams, and tableaux. In Section 2.2, we define Symand give a combinatorial description for the distinguished basis of Schur functions usingsemistandard reverse tableaux. We also discuss combinatorial procedures such as jeu detaquin and rectification. Section 2.3 concerns itself with QSym and a natural analogue ofSchur functions therein, the quasisymmetric Schur functions. Next we consider the Hopfdual to QSym, that is, NSym and give an implicit description for the basis of noncommu-tative Schur functions. In Section 2.5, we define certain operators on compositions. Theseoperators are crucial in helping us derive our noncommutative Murnaghan-Nakayama ruleand the right Pieri rules. Finally, in Section 2.6, we state our two main results along withcomprehensive examples: Theorem 2.6.3 (noncommutative Murnaghan-Nakayama rule), and4Algorithm 2.6.6 (backward jeu de taquin slides for SSRCTs).In Chapter 3 we give a proof for Theorem 2.6.3. In Section 3.1, we connect sequences ofbox adding operators with standard reverse composition tableaux, and then describe certaindistinguished sequences of box adding operators called reverse hookwords. The goal ofSection 3.2 is to give a rudimentary version of the noncommutative Murnaghan-Nakayamarule in terms of box adding operators in Equation (3.6). Finally, after introducing ouranalogue of classical border strips, called nc border strips, in Section 3.3, we arrive at thenoncommutative Murnaghan-Nakayama rule that mirrors the classical version in Theorem3.3.20.In Chapter 4, we proceed to give the proofs of validity of the algorithms described earlierin Subsection 2.6.3 and the connection is made precise in Theorem 4.1.21. Next, in Subsection4.1.1, we study the effect of slides on underlying composition shapes using jdt operators.In Section 4.2, we describe a procedure to perform backward jeu de taquin slides on skewsemistandard reverse composition tableaux. Using the jdt operators, in Section 4.3 we endowthe set of compositions with a new poset structure Rc. Finally, in Section 4.4, we prove rightPieri rules in Theorem 4.4.3 and enumerate the maximal chains in Rc in Theorem 4.4.4.We conclude this thesis by describing some new questions and avenues in Chapter 5.5Chapter 2Sym, QSym and NSymWe start by defining some of the combinatorial structures that we will encounter. All theclassical notions introduced in this chapter are covered in more detail in [30, 38, 42].2.1 Combinatorial preliminaries2.1.1 PartitionsA partition λ is a finite list of positive integers (λ1, . . . , λk) satisfying λ1 ≥ λ2 ≥ · · · ≥ λk.The integers appearing in the list are called the parts of the partition. Given a partitionλ = (λ1, . . . , λk), the size |λ| is defined to be∑ki=1 λi. The number of parts of λ is calledits length, and is denoted by l(λ). If λ is a partition satisfying |λ| = n, then we denote thisby λ ` n. By convention, there is a unique partition of size and length equalling 0, and wedenote it by ∅.We will depict a partition using its Young diagram. Given a partition λ = (λ1, . . . , λk) `n, the Young diagram of λ, also denoted by λ, is the left-justified array of n boxes, with λiboxes in the i-th row. We will be using the French convention where the rows are numberedfrom bottom to top and the columns from left to right, and will refer to the box in the i-throw and j-th column by the ordered pair (i, j). If λ and µ are partitions such that µ ⊆ λ,that is, l(µ) ≤ l(λ) and µi ≤ λi for all i = 1, 2, . . . , l(µ), then the skew shape λ/µ is obtainedby removing the first µi boxes from the i-th row of the Young diagram of λ for 1 ≤ i ≤ l(µ).Given a skew shape λ/µ, we refer to λ as the outer shape and to µ as the inner shape. If theinner shape is ∅, instead of writing λ/∅, we just write λ and call λ a straight shape. Thesize of a skew shape λ/µ, denoted by |λ/µ|, is the number of boxes in the skew shape, which6is |λ| − |µ|. If λ/µ does not have two boxes belonging to the same column, then it is calleda horizontal strip, while if it does not have two boxes belonging to the same row it is calleda vertical strip.Next, we define addable nodes and removable nodes of a partition. An addable node of apartition λ is a position (i, j) where a box can be appended to a part of λ so that the resultis still a partition. Note that the addable nodes of a partition do not belong to the partition.On the other hand, a removable node of λ is a position (i, j) where a box can be removed froma part of λ so that the resulting shape is still a partition. Unlike addable nodes, removablenodes of a partition belong to the partition. Furthermore, given a partition, both addablenodes and removable nodes are uniquely determined by the column to which they belong.In the definitions just given, we have identified the partition λ with its Young diagram.We will now use the aforementioned notions to define a lattice structure on the set ofpartitions, called Young’s lattice. If µ is a partition obtained by adding a box at an addablenode of the partition λ, then we say that µ covers λ and we denote it by λ ≺ µ. The partialorder obtained by taking the transitive closure of ≺ endows the set of partitions with thestructure of a lattice that we will denote by Y [38, Definition 5.1.2].Example 2.1.1. The partition λ = (3, 2, 2, 1) is represented by the following Young diagram.The box in the lower left corner is indexed by (1, 1). The addable nodes of λ are (1, 4), (2, 3),(4, 2) and (5, 1) while the removable nodes are (1, 3), (3, 2) and (4, 1). Also, the partitionµ = (3, 3, 2, 1) covers λ in Y, that is, (3, 2, 2, 1) ≺ (3, 3, 2, 1).2.1.2 Semistandard reverse tableauxIn this subsection, we will introduce certain classical objects that play a central role in thetheory of symmetric functions.Definition 2.1.2. Given a skew shape λ/µ, a semistandard reverse tableau (SSRT) T ofshape λ/µ is a filling of the boxes of λ/µ with positive integers satisfying the condition thatthe entries in T are weakly decreasing along each row read from left to right and strictlydecreasing along each column read from bottom to top.We will denote the set of all SSRTs of shape λ/µ by SSRT(λ/µ). Given an SSRT T ,the entry in box (i, j) is denoted by T(i,j). The shape underlying T is denoted by sh(T ).7A standard reverse tableau (SRT) T of shape λ/µ is an SSRT that contains every positiveinteger in [|λ/µ|] = {1, 2, . . . , |λ/µ|} exactly once.Given an SSRT, we associate to it a distinguished word called the column reading word.This word plays an important role in tableaux combinatorics, and we will encounter it whendiscussing jeu de taquin and rectification. The column reading word of an SSRT T is theword obtained by reading the entries of every column in increasing order from left to right,and we denote it by wT .Let {x1, x2, . . .} be an alphabet comprising of countably many commuting indeterminates.Given any SSRT T of shape λ ` n, we will associate a monomial xT with it as follows.xT =∏(i,j)∈λxT(i,j)Example 2.1.3. Shown below are an SSRT T of shape (4, 3, 3, 1) and its associated mono-mial.T =13 3 26 5 47 7 6 3xT = x27x26x5x4x33x2x1The column reading word of T is 1367 357 246 3.2.1.3 CompositionsA composition α is a finite ordered list of positive integers. The integers appearing in thelist are called the parts of the composition. Given a composition α = (α1, . . . , αk), its size|α| is defined to be∑ki=1 αi. The number of parts of α is called the length, and is denotedby l(α). If α is a composition satisfying |α| = n, then we write it as α n. By convention,there is a unique composition of size and length 0, and we denote it by ∅. Finally, given acomposition α, we denote by α˜ the partition obtained by sorting the parts of α in weaklydecreasing order.Just as we used Young diagrams for partitions, we will depict a composition using itsreverse composition diagram as follows. Given a composition α = (α1, . . . , αk) n, thereverse composition diagram of α, also denoted by α, is the left-justified array of n boxeswith αi boxes in the i-th row. Here we follow the English convention, that is, the rows arenumbered from top to bottom, and the columns from left to right. We will refer to the boxin the i-th row and j-th column by the ordered pair (i, j). We adopt a different convention8from Young diagrams in order to facilitate easier proofs later.Recall now the bijection between compositions of n and subsets of [n − 1]. Given acomposition α = (α1, . . . , αk) n, we can associate a subset of [n − 1], denoted by set(α),by defining it to be {α1, α1 + α2, . . . , α1 + · · ·+ αk−1}. In the opposite direction, given a setS = {i1 < · · · < ij} ⊆ [n− 1], we can associate a composition of n, denoted by comp(S), bydefining it to be (i1, i2 − i1, . . . , ij − ij−1, n− ij).Finally, we define the refinement order on compositions. Given compositions α and β,we say that α < β if one obtains parts of α in order by adding together adjacent parts of βin order. The composition β is said to be a refinement of α.Example 2.1.4. Let α = (4, 2, 3) 9. Then set(α) = {4, 6} ⊆ [8]. Shown below is thereverse composition diagram of α.Note also that (4, 2, 3) < (3, 1, 2, 1, 2).2.1.4 Semistandard reverse composition tableauxLet α = (α1, . . . , αl) and β be compositions. Define a cover relation lc on compositions asfollows.αlc β iff{β = (1, α1, . . . , αl) orβ = (α1, . . . , αk + 1, . . . , αl) and αi 6= αk for all i < k.The reverse composition poset Lc is the poset on compositions where the partial order <c isobtained by taking the transitive closure of the cover relations above. If α <c β, the skewreverse composition shape β/α is defined to be the array of boxesβ/α = {(i, j) | (i, j) ∈ β, (i, j) /∈ α}where α is drawn in the bottom left corner of β. We refer to β as the outer shape and to αas the inner shape. If the inner shape is ∅, instead of writing β/∅, we simply write β andrefer to β as a straight shape. The size of the skew reverse composition shape β/α, denotedby |β/α|, is the number of boxes in the skew reverse composition shape, that is, |β| − |α|.If β/α does not have two boxes belonging to the same column, then it is called a horizontalstrip, while if it does not have two boxes lying in the same row it is called a vertical strip.9Recall that we had the notion of horizontal and vertical strips for skew shapes as well, andit will be clear from the context which notion we are referring to.Definition 2.1.5. A semistandard reverse composition tableau (SSRCT) τ of shape β/αis a fillingτ : β/α −→ Z+that satisfies the following conditions1. the rows are weakly decreasing from left to right,2. the entries in the first column are strictly increasing from top to bottom,3. if i < j and (j, k + 1) ∈ β/α and either (i, k) ∈ α or τ(i, k) ≥ τ(j, k + 1) then either(i, k + 1) ∈ α or both (i, k + 1) ∈ β/α and τ(i, k + 1) > τ(j, k + 1).The shape underlying an SSRCT τ will be denoted by sh(τ). A standard reverse compo-sition tableau (SRCT) is an SSRCT in which the filling is a bijection τ : α/β −→ [|α/β|].That is, in an SRCT each number from the set {1, 2, . . . , |α/β|} appears exactly once. Wewill denote the set of SSRCTs (SRCTs) of shape β/α by SSRCT(β/α) (SRCT(β/α) re-spectively).Throughout this thesis, when considering an SSRCT, the boxes of the outer shape willoften be shaded. Suppose now that we fill the boxes belonging to the inner shape with bulletsand assume further that the ordered pairs of positive integers (i, j) such that (i, j) /∈ α and(i, j) /∈ β are filled with 0s. This given, the third condition in the definition above isequivalent to the non-existence of the following configurations in the filling τ .• y...z• ...zx y...zx ...zz ≥ y > 0 z > 0 x ≥ z ≥ y > 0 x ≥ z > 0The existence of a configuration of the above types in a filling will be termed a triple ruleviolation. From this point on, we will refer to the entry in the box in position (i, j) of anSSRCT τ by τ(i,j).The column reading word of an SSRCT τ is the word obtained by reading the entriesin each column in increasing order, where we traverse the columns from left to right. Wedenote it by wτ .10Just as we did with SSRTs, we will associate a monomial to an SSRCT. Given anySSRCT τ of shape α n, we will associate a monomial xτ with it as follows.xτ =∏(i,j)∈αxτ(i,j)Example 2.1.6. An SSRCT of shape (2, 5, 4, 2)/ (2, 1, 2) (left) and an SRCT of shape(3, 4, 2, 3).4 3• • 7 5 1• 7 6 2• •6 4 18 7 5 210 312 11 9The column reading word of the SSRCT τ on the left is wτ = 4 37 67 25 1.Also associated with an SRCT is its descent set. Given an SRCT τ of shape α n, itsdescent set, denoted by Des(τ), is defined to be the set of all integers i such that i + 1 liesweakly to the right of i in τ . Note that Des(τ) is a subset of [n−1]. The descent compositionof τ , denoted by comp(τ), is the composition of n associated with Des(τ). For instance, thedescent set of the SRCT in Example 2.1.6 is {1, 3, 4, 6, 8, 10} ⊆ [11]. Hence the associateddescent composition is (1, 2, 1, 2, 2, 2, 2) 12.Given a composition α, there exists a unique SRCT τα so that the underlying shape of ταis α and comp(τα) = α. This tableau is called the canonical tableau of shape α. To constructτα given α = (α1, . . . , αk), place consecutive integers from 1 +∑r−1i=1 αi to∑ri=1 αi in thatorder from right to left in the r-th row from the top in the reverse composition diagram ofα for 1 ≤ r ≤ k.Example 2.1.7. Let α = (3, 4, 2, 3). Then τα is as shown below.3 2 17 6 5 49 812 11 10Next, we will show that SSRCTs and SSRTs are intimately related via a generalizationof the bijection defined by Mason in [31] (the generalization itself is also bijective and ispresented in [29]). Let SSRCT(−/α) denote the set of all SSRCTs with inner shape α, andlet SSRT(−/α˜) denote the set of SSRTs with inner shape α˜ (which might be empty). Then11the generalized ρ mapρα : SSRCT(−/α) −→ SSRT(−/α˜)is defined as follows. Given an SSRCT τ , write the entries in each column in decreasingorder from bottom to top, and bottom justify the new columns thus obtained on the innershape α˜. This yields ρα(τ).We give the description of the inverse map ρ−1α next. Let T be an SSRT.1. Take the first column of the SSRT, and place the entries of this column above the firstcolumn of the inner shape α in increasing order from top to bottom.2. Now take the set of entries in the second column in decreasing order and place themin the row with smallest index so that either• the box to the immediate left of the number being placed is filled and the entrytherein is weakly greater than the number being placed• the box to the immediate left of the number being placed belongs to the innershape α.As a matter of convention, instead of writing ρ∅ or ρ−1∅ , we will use ρ or ρ−1 respectively.Example 2.1.8. An SSRCT of shape (2, 5, 4, 2)/ (2, 1, 2) (left), and the corresponding SSRTof shape (5, 4, 2, 2)/(2, 2, 1) (right).4 3• • 7 5 1• 7 6 2• •ρ(2,1,2)ρ−1(2,1,2)4 3• 7• • 6 2• • 7 5 12.2 Symmetric functions and Schur functionsThe algebra of symmetric functions, denoted by Sym, is the algebra freely generated overQ by countably many commuting variables {h1, h2, . . .}. Assigning degree i to hi (and thenextending this multiplicatively) allows us to endow Sym with a structure of a graded algebra.A basis for the degree n component of Sym, denoted by Symn, is given by the completehomogeneous symmetric functions of degree n,{hλ = hλ1 · · ·hλk : λ = (λ1, . . . , λk) ` n}.12A concrete realization of Sym is obtained by embedding Sym in Q[[x1, x2, . . .]], that is, thering of formal power series in countably many commuting indeterminates x1, x2, . . ., underthe identification (extended multiplicatively)hi 7−→ sum of all distinct monomials in x1, x2, . . . of degree i.This viewpoint allows us to think of symmetric functions as being certain formal powerseries f in the x variables with the property that f(xpi(1), xpi(2), . . .) = f(x1, x2, . . .) for everypermutation pi of the positive integers N.Definition 2.2.1. The Schur function indexed by the partition λ, denoted by sλ, is definedcombinatorially assλ =∑T∈SSRT(λ)xT .Moreover, we define s∅ = 1.Though not evident from the definition above, sλ is a symmetric function [38, Proposition4.4.2]. Furthermore, the elements of the set {sλ : λ ` n} form a basis of Symn for any positiveinteger n.Example 2.2.2. We obtain the expansions(2,1) = x21x2 + x1x22 + 2x1x2x3 + · · ·from the tableaux below.12 112 213 223 1 · · ·Now we will give the reader a hint of the importance of the Schur basis in the represen-tation theory of symmetric groups.2.2.1 The Murnaghan-Nakayama ruleAnother important class of symmetric functions is given by the power sum symmetric func-tions. The power sum symmetric function pk for k ≥ 1 is defined aspk =∑i≥1xki .13The set {pλ = pλ1 · · · pλk | λ = (λ1, . . . , λk) ` n} also forms a basis for Symn for anypositive integer n. The classical Murnaghan-Nakayama rule gives an algorithm to computethe product pk · sµ in terms of Schur functions. To state the rule, we need the notion of aborder strip. A skew shape λ/µ is called a border strip if it is connected and contains no2× 2 array of boxes. The height of a border strip λ/µ, denoted by ht(λ/µ), is defined to beone less than the number of rows occupied by the border strip.Theorem 2.2.3 (Murnaghan-Nakayama rule). [42, Theorem 7.17.1] Given a positive integerk and µ ` n, we havepk · sµ =∑λ`|µ|+k(−1)ht(λ/µ)sλ,where the sum is over all partitions λ such that λ/µ is a border strip of size k.As an aid to understanding the theorem above, we will do an example.Example 2.2.4. Consider the computation of p3 · s(2,1). All partitions λ such that λ/(2, 1)is a border strip of size 3 are listed below.The statistic ht(λ/(2, 1)) for the partitions above from left to right is 2, 1, 1, 0 respectively.Hence, the Murnaghan-Nakayama rule yields thatp3 · s(2,1) = s(2,1,1,1,1) − s(2,2,2) − s(3,3) + s(5,1).We can use Theorem 2.2.3 iteratively to expand a power sum symmetric function indexedby a partition in the basis of Schur functions, and combinatorially compute the structurecoefficients that arise in doing so. These structure coefficients are in fact the character valuesof the symmetric group [42, Corollary 7.17.4].A noncommutative analogue of Theorem 2.2.3 will be the main result in Chapter 3. Nextwe discuss an important combinatorial procedure whose noncommutative analogue will beour focus in Chapter 4.142.2.2 Jeu de taquin slides on SSRTsIn this subsection, we will describe backward jeu de taquin slides in the setting of SSRTs.The exposition here follows that in [38] analogously.Let λ ` n and T ∈ SSRT(λ). Given i0, j0 ≥ 1 such that λ has an addable node in positionc = (i0, j0), a backward jeu de taquin slide on T starting from c gives an SSRT jdtj0(T ) inthe manner outlined below.1. Let c = (i0, j0).2. While c is not equal to (1, 1) do• If c = (i, j), then let c′ be the box of min(T(i−1,j), T(i,j−1)). If only one of T(i−1,j)and T(i,j−1) exists then the minimum is taken to be that single value. Furthermore,if T(i−1,j) = T(i,j−1), then c′ = (i− 1, j).• Slide Tc′ into position c. Let c := c′.3. The final skew SSRT obtained is jdtj0(T ).We give an example demonstrating the above algorithm.Example 2.2.5. Let λ = (3, 2, 2, 1) and let T ∈ SSRT(λ) be25 46 58 7 1.If we start a backward jeu de taquin slide from the addable node given by c = (2, 3), thenthe algorithm executes in the following manner.25 46 5 •8 7 1→25 46 5 18 7 •→25 46 5 18 • 7→25 46 5 1• 8 7Thus, we have thatjdt3(T ) =25 46 5 18 7.15The above algorithm can be generalized naturally to SSRT of skew shape. Now let Tdenote an SSRT of skew shape λ/µ. Suppose i0, j0 ≥ 1 are such that the position c = (i0, j0)is an addable node of λ. Then jdtj0(T ) is obtained as outlined below.1. Let c = (i0, j0).2. While c is not an addable node of µ do• If c = (i, j), then let c′ be the box of min(T(i−1,j), T(i,j−1)). If only one of T(i−1,j)and T(i,j−1) exists then the minimum is taken to be that single value. Furthermore,if T(i−1,j) = T(i,j−1), then c′ = (i− 1, j).• Slide Tc′ into position c. Let c := c′.3. The final skew SSRT obtained is jdtj0(T ).Example 2.2.6. Consider the SSRT T of shape (5, 4, 3, 1)/(3, 2) as shown below.13 1 1• • 2 1• • • 4 3Suppose we want to compute jdt4(T ). Then the following sequence of sliding moves occurs,where the shaded box denotes the box into which entries slide.13 1 1 •• • 2 1• • • 4 3−→13 1 1 1• • 2 •• • • 4 3−→13 1 1 1• • • 2• • • 4 3Thus, we havejdt4(T ) =13 1 1 124 3.For completeness, we will discuss the forward jeu de taquin slide next. It is the inverseof the backward jeu de taquin slide discussed above. Let T denote an SSRT of skew shapeλ/µ. Suppose i0, j0 ≥ 1 are such that the position c = (i0, j0) is a removable node of µ. Thenthe SSRT obtained after a forward jeu de taquin slide is initiated from position c, which wedenote by jdtfj0(T ), is obtained as outlined below.161. Let c = (i0, j0).2. While c is not an addable node of λ do• If c = (i, j), then let c′ be the box of max(T(i+1,j), T(i,j+1)). If only one of T(i+1,j)and T(i,j+1) exists then the maximum is taken to be that single value. Furthermore,if T(i+1,j) = T(i,j+1), then c′ = (i+ 1, j).• Slide Tc′ into position c. Let c := c′.3. The final SSRT obtained is jdtfj0(T ).Example 2.2.7. Let T denote the SSRT below.13 1 1 1• • • 2• • • 4 3Then jdtf3(T ) is obtained by reversing the steps in Example 2.2.6 and we get thatjdtf3(T ) =13 1 1• • 2 1• • • 4 3.2.2.3 Rectification of SRTsA procedure that is closely tied to the jeu de taquin slide is rectification. To describe it in away that is convenient for us, we need to introduce a slight variant of the Robinson-Schenstedalgorithm.A discussion of the original algorithm is present in Section 4.5. Our variant establishes abijection between permutations in Sn and pairs of SRTs of the same shape. We will need thenotion of a partial tableau that we define to be an SSRT with distinct entries. Furthemore,we will abuse notation and use ∅ to denote the empty tableau.We will outline the algorithm next. Our input is a permutation σ ∈ Sn, and the outputis a pair of SRTs of the same shape and size n.Algorithm 2.2.8 (Variant of Robinson-Schensted insertion algorithm).1. Let P0 = Q0 = ∅.172. For i = 1 to n, let y := σ(i) and do(a) Set r := first row of Pi−1.(b) While y is greater than some number in row r, do• Let x be the greatest number smaller than y and replace x by y in Pi−1.• Set y := x and r := the next row.(c) Now that y is smaller than every number in row r, place y at the end of row rand call the resulting partial tableau Pi. If (a, b) is where y was placed, the partialtableau Qi is obtained by placing n− i+ 1 in position (a, b) in Qi−1.3. Finally, set P := Pn and Q := Qn.The SRTs P and Q thus obtained are called the insertion tableau and recording tableaurespectively. We present an example next.Example 2.2.9. Consider the permutation σ = 3157624 in one line notation. Then theinsertion algorithm executes as shown below, where at each stage we note the pair (Pi, Qi).(∅,∅) 7→ ( 3 , 7 ) 7→ ( 3 1 , 7 6 ) 7→(35 1 ,57 6)7→(357 1,457 6)7→(35 17 6,45 37 6)7→(35 17 6 2,45 37 6 2)7→(3 15 27 6 4,4 15 37 6 2)Recall that given an SRT T , its column reading word is wT . Furthermore, wT is apermutation written in single line notation. The rectification of T , denoted rect(T ) is definedto be P (wT ), that is, the insertion tableau obtained on performing the above variant ofRobinson-Schensted algorithm on wT .Example 2.2.10. Consider the SRT T of skew shape given below.3 157 6 24Then the column reading word is 3 157 6 24. The insertion tableau for this reading word has18already been computed in Example 2.2.9, and thus rect(T ) is as follows.3 15 27 6 4An important property of rectification that will prove crucial for us is the fact that itbehaves nicely with respect to jeu de taquin slides. More precisely, if T ′ is some SRT obtainedby performing a backward jeu de taquin slide on some SRT T , then rect(T ) = rect(T ′) [38,Theorem 3.7.7]. Rectification also allows us to describe another important combinatorialprocedure called evacuation which we describe next.Given an SRT T , the evacuation action on T , denoted by e(T ), is obtained using thealgorithm below.Algorithm 2.2.11 (Evacuation).1. Let U be a Young diagram of shape λ, where λ = sh(T ) ` n.2. Let the entry in the box in position (1, 1) in T be a. Remove this entry, and computethe rectification of the remaining SRT of skew shape. Equivalently, one can remove theentry in the box in position (1, 1) in T and let T ′ be the resulting skew SRT, and computejdtf1(T′). This viewpoint makes it clear that the underlying shape of the rectified tableauis obtained by removing a removable node from λ. Let this node be in position (i, j).3. To the box given by (i, j) in U , assign the entry n− a+ 1.4. Repeat the previous two steps until all the boxes in U are filled. Finally, e(T ) = U .Example 2.2.12. Consider the insertion tableau from Example 2.2.9. We demonstrateAlgorithm 2.2.11 by drawing the tableau T and the partially filled U at each step.3 15 27 6 4, 7→3 15 26 4,17→13 25 4,217→134 2,2317→ 13 2 ,4 2317→ 12 ,4 235 17→ 1 ,4 26 35 17→ ∅,4 26 37 5 1Thus, e(T ) is the SRT obtained in the last step above.Next, we will note down a property of our variant of the Robinson-Schensted algorithm.The proof is presented in Section 4.5.19Lemma 2.2.13. Let w ∈ Sn and suppose that w 7→ (P,Q) using the variant of Robinson-Schensted algorithm outlined in Algorithm 2.2.8. Thenw−1 7→ (e(Q), e(P )).2.2.4 The classical Pieri rulesAs an application of the concepts in the previous subsection we obtain the classical Pierirules. These rules give an explicit description for the products s(n) · sµ and s(1,...,1) · sµ interms of Schur functions. They are a special case of the Littlewood-Richardson rule whichis a combinatorial rule for expressing the product of two Schur functions as a sum of Schurfunctions,Theorem 2.2.14 (Pieri rules). [42, Theorem 7.15.7] Let µ be a partition and n be a positiveinteger. Let (1n) denote the partition with n parts all equalling 1. Then we have the followingexpansions.s(n) · sµ =∑λ/µ a horizontal strip|λ/µ|=nsλs(1n) · sµ =∑λ/µ a vertical strip|λ/µ|=nsλWe consider an example next.Example 2.2.15. Let λ = (2, 1) and n = 2. Then we obtain the expansions(2) · s(2,1) = s(2,2,1) + s(3,1,1) + s(3,2) + s(4,1)from the following horizontal strips (shown shaded).Similarly, we obtain the expansions(1,1) · s(2,1) = s(2,1,1,1) + s(2,2,1) + s(3,1,1) + s(3,2)20from the vertical strips below (shown shaded).In Chapter 4, we will obtain a noncommutative analogue of Theorem 2.2.14 above.2.3 Quasisymmetric functions and quasisymmetricSchur functionsWe will now introduce an important Hopf algebra of which Sym is a Hopf subalgebra. Thisis the algebra of quasisymmetric functions, referred to as QSym, and was originally definedby Gessel [14].A formal power series f ∈ Q[[x1, x2, . . .]] is said to be a quasisymmetric function if itsatisfies the following two conditions.1. The degrees of the monomials occurring in f are bounded.2. For all compositions (α1, . . . , αk), all monomials xα1i1 · · · xαkikin f with i1 < i2 < · · · < ikhave the same coefficient.It can be easily verified that the product of two quasisymmetric functions is quasisymmetric.Hence the set of quasisymmetric functions can be endowed with an algebra structure. It isthis algebra that we refer to as QSym. Just as in the case of Sym, we have that QSym isa graded algebra, where the degree gives the grading. We denote the degree n componentby QSymn.QSym has a host of interesting bases. We will first introduce the basis of fundamen-tal quasisymmetric functions and then use it to define the basis of quasisymmetric Schurfunctions.Let α = (α1, . . . , αk) n. Then the fundamental quasisymmetric function Fα is definedbyFα =∑xi1 · · ·xinwhere the sum is over all 1 ≤ i1 ≤ · · · ≤ in and ij < ij+1 if j ∈ set(α). Furthermore, we defineF∅ to be 1. Additionally we have that QSymn = span{Fα | α n}, which immediatelyyields that dim(QSymn) = 2n−1.21Example 2.3.1. Let α = (1, 2). Then set(α) = {1}. We obtain the following expansion forF(1,2).F(1,2) = x1x22 + x1x23 + x2x23 + · · ·+ x1x2x3 + x1x2x4 + x2x3x4 + · · ·Now we are set to define quasisymmetric Schur functions. We will give two equivalentdefinitions: one involving sum of monomials associated with SSRCTs (akin to our combi-natorial definition of Schur functions earlier), and the other an expansion in the basis offundamental quasisymmetric functions.Definition 2.3.2. Given a composition α, the quasisymmetric Schur function indexed by α,denoted by Sα is defined bySα =∑τ∈SSRCT(α)xτ =∑τ∈SRCT(α)dαβFβwhere dαβ denotes the number of SRCTs of shape α and descent composition β. Furthermore,we define S∅ to be 1.Example 2.3.3. Let α = (1, 2). Then we obtain the following expansionS(1,2) =x1x22 + x1x23 + x2x23 + x1x2x3 + x1x2x4 · · ·=F(1,2).from the following list of SSRCTs.12 213 323 313 214 2 · · ·The expansion in fundamental quasisymmetric functions is obtained from the only SRCT ofshape (1, 2) (the one with shaded boxes).As an additional example, consider α = (3, 2). Then we obtain the following expansionS(3,2) =F(3,2) + F(1,3,1) + F(2,2,1)from the following list of SRCTs.3 2 15 44 3 25 14 3 15 222In addition to Definition 2.3.2, some of the fundamental properties of Sα that were provedin [17] were the following.1. Sα ∈ QSym.2. QSymn = span{Sα | α n}.3. sλ =∑α˜=λSα.The third point above explains the reasoning behind calling the functions quasisymetricSchur functions. Analogues of the classical Littlewood-Richardson rule and Pieri rules havealso been found (see [4, 17, 18]), casting new light on classical results and giving rise to newavenues. The Hopf algebra dual to QSym is equally interesting, and we will introduce itnext.2.4 Noncommutative symmetric functions andnoncommutative Schur functionsAn algebra closely related to Sym and QSym is the algebra of noncommutative symmetricfunctions NSym, introduced in [13]. The algebra NSym is the free associative algebraQ〈h1,h2, . . .〉 generated by a countably infinite number of indeterminates hk for k ≥ 1.Assigning degree k to hk, and extending this multiplicatively allows us to endow NSymwith a structure of a graded algebra. A natural basis for the degree n graded componentof NSym, denoted by NSymn, is given by the noncommutative complete homogeneoussymmetric functions, {hα = hα1 · · ·hαk : α = (α1, . . . , αk) n}. The link between Sym andNSym is made manifest through the forgetful map, χ : NSym→ Sym, defined by mappinghi to hi and extending multiplicatively. Thus, the images of elements of NSym under χ areelements of Sym, imparting credibility to the term noncommutative symmetric function.NSym has another important basis called the noncommutative ribbon Schur basis. Wewill denote the noncommutative ribbon Schur function indexed by a composition β by rβ.The following [13, Proposition 4.13] can be taken as the definition of the noncommutativeribbon Schur functions.rβ =∑α<β(−1)l(β)−l(α)hαA multiplication rule for noncommutative ribbon Schur functions was proved in [13], and wewill be needing it later.23Theorem 2.4.1 (Proposition 3.13, [13]). Let α = (α1, . . . , αk1) and β = (β1, . . . , βk2) becompositions. Define two new compositions γ and µ as followsγ = (α1, . . . , αk1 , β1, . . . , βk2), δ = (α1, . . . , αk1 + β1, β2, . . . , βk2).Thenrα · rβ = rγ + rδ.We will also need a noncommutative analogue of the power sum symmetric functions. In[13] they have defined two such analogues, the Φ basis and the Ψ basis. Our interest is inthe Ψ basis. For a positive integer n, defineΨn =n−1∑k=0(−1)kr(1k,n−k). (2.1)This given, for a composition α = (α1, . . . , αk), we define Ψα multiplicatively as Ψα1 · · ·Ψαk .It can be shown that χ(Ψn) = pn.While the transition matrix between the Ψ basis and r basis is discussed in [13, Section4.8], no explicit rule for Ψn · rα is given. Since rα has a representation theoretic meaning[24], this product may also be considered a type of Murnaghan-Nakayama rule and hencewe will give a rule to compute Ψn · rα where n is a positive integer and α is a composition.Lemma 2.4.2. Let α = (α1, . . . , αm) be a composition and let n be a positive integer. ThenΨn · rα =n−1∑k=0(−1)kr(1k,n−k,α1,...,αm) +n−1∑k=0(−1)kr(1k,n−k+α1,α2,...,αm).Furthermore, the summands on the right are all distinct, that is, there is no cancellation inthe sum on the right.Proof. From (2.1) and the multiplication rule in Theorem 2.4.1, it follows thatΨn · rα =n−1∑k=0(−1)kr(1k,n−k,α1,...,αm) +n−1∑k=0(−1)kr(1k,n−k+α1,α2,...,αm).Hence we only need to establish that the summands above are all distinct. Consider the24following multisets of compositions.X1 ={(1k, n− k, α1, . . . , αm) | 0 ≤ k ≤ n− 1}X2 ={(1k, n− k + α1, α2, . . . , αm) | 0 ≤ k ≤ n− 1}By considering the lengths of the compositions therein, it follows that the elements in X1(and X2) are all distinct. Hence, to establish that there is no cancellation, we only need toshow that the set X1 ∩ X2 is empty. Assume otherwise. Then there exist positive integers0 ≤ a, b ≤ n− 1 such that(1a, n− a, α1, . . . , αm) = (1b, n− b+ α1, α2, . . . , αm).That the lengths of the two compositions above have to be equal implies that a + 1 = b.But then the equality of compositions above implies that n − a = 1, which in turn yieldsthat b = n. But we know that 0 ≤ b ≤ n− 1. Hence we have a contradiction, and the claimfollows.Example 2.4.3. Lemma 2.4.2 gives the following expansion for Ψ(3) · r(1,3,2).Ψ(3) · r(1,3,2) = (r(3,1,3,2))− r(1,2,1,3,2) + r(1,1,1,1,3,2)) + (r(4,3,2) − r(1,3,3,2) + r(1,1,2,3,2))Now that we have defined a noncommutative analogue of power sum symmetric functions,to state a noncommutative Murnaghan-Nakayama rule, we need to define our analogue ofthe Schur functions in NSym. The next subsection achieves that aim.2.4.1 Noncommutative Schur functionsWe will now describe a distinguished basis for NSym, introduced in [4], called the basisof noncommutative Schur functions. They are naturally indexed by compositions, and thenoncommutative Schur function indexed by a composition α will be denoted by sα.Definition 2.4.4. The noncommutative Schur functions sα for α n are defined implicitlyusing the relationrβ =∑α|β|dαβsα (2.2)where dαβ is the number of SRCTs of shape α and descent composition β.25Remark 2.4.5. The original definition of noncommutative Schur functions in [4, Section2.4] utilized the duality between the Hopf algebras NSym and QSym. The basis of noncom-mutative Schur functions is defined to be the dual basis corresponding to the basis of qua-sisymmetric Schur functions. The relation (2.2) is obtained by considering the dual versionof the expansion of a quasisymmetric Schur function in terms of the fundamental quasisym-metric functions in Definition 2.3.2.The noncommutative Schur function sα satisfies the following important property [4,Equation 2.12].χ(sα) = sα˜Thus, the noncommutative Schur functions are lifts of the Schur functions in NSym. Theyshare many properties with the Schur functions. The interested reader should refer to [4, 29]for an in-depth study of these functions. For our purposes, we require the noncommutativeLittlewood-Richardson rule proved in [4].Theorem 2.4.6. [4, Theorem 3.5] Given compositions α and β, the product sα · sβ can beexpanded in the basis of noncommutative Schur functions assα · sβ =∑γCγαβsγwhere Cγαβ counts the number of SRCTs of shape γ/β that rectify to the canonical tableau ofshape α.We should clarify what it means to rectify for SRCTs. We say that an SRCT τ1 of shapeγ/β rectifies to a tableau τ2 of straight shape α if ρ−1(P (wτ1)) = τ2.As a corollary of the above result, we obtain the noncommutative Pieri rules for noncom-mutative Schur functions proved in [4], which we state below.Theorem 2.4.7 (Left Pieri rules). [4, Corollary 3.8] Given a composition β, we haves(n) · sα =∑γsγwhere the sum on the right runs over all compositions γ >c α such that |γ/α| = n and γ/αis a horizontal strip where the boxes have been added in columns from left to right. Similarly,s(1n) · sα =∑γsγ26where the sum on the right runs over all compositions γ >c α such that |γ/α| = n and γ/αis a vertical strip where the boxes have been added in columns from right to left.The following example will illustrate the theorem above.Example 2.4.8. Let α be (1, 4, 2) and n = 3. We compute the following expansions(3) · s(1,4,2) =s(3,1,4,2) + s(2,1,5,2) + s(1,1,4,4) + s(1,1,5,3) + s(1,1,6,2)+ s(4,4,2) + s(3,5,2) + s(2,6,2) + s(1,5,4) + s(1,6,3) + s(1,7,2)from the following horizontal strips (shown shaded).Similarly, we compute the expansions(1,1,1) · s(1,4,2) =s(1,1,1,1,4,2) + s(1,1,2,4,2) + s(1,1,1,4,3) + s(1,1,1,5,2)+ s(1,2,4,3) + s(1,2,5,2) + s(1,1,5,3) + s(2,5,3)from the vertical strips below (shown shaded).Next, we will state an easy equality that will prove useful in Chapter 3.Lemma 2.4.9. Let n ≥ 0. Then we have that s(n) = r(n) and s(1n) = r(1n).Proof. By (2.2) we have thatrβ =∑αndαβsα.27where dαβ is the number of SRCTs of shape α and descent composition β. Now our claimfollows once we note that if β = (n) or β = (1n) then dαβ = δαβ. Here δαβ denotes theKronecker delta function that equals 1 if α = β and 0 otherwise.2.5 Operators on compositionsIn this section, we will define certain operators on compositions that play a key role in thisthesis. We begin by defining the box adding operators that act on compositions and add abox to a composition in accordance with the Pieri rules stated in Theorem 2.4.7.2.5.1 Box adding operatorsGiven a positive integer i and a composition α, we define ti(α) in the following manner.ti(α) ={β if αlc β and β/α is a box in the i-th column0 otherwise.It is clear from the above definition that ti(α) is nonzero if and only if α has a part equal toi− 1.Example 2.5.1. Let α = (2, 1, 3, 1). Then t1(α) = (1, 2, 1, 3, 1), t2(α) = (2, 2, 3, 1) andt5(α) = 0.Next we establish a useful relation satisfied by box adding operators.Lemma 2.5.2. Given positive integers i, j such that |i − j| ≥ 2, we have the followingequality as operators on compositions.titj = tjtiProof. We will assume, without loss of generality that i < j. Consider first the case wherei = 1 and j ≥ 3. If α = (α1, . . . , αk) is a composition, and no part of α equals j−1, then wehave t1tj(α) = tjt1(α) = 0. If, on the other hand, there is a part of α that equals j−1, pick theleftmost such part. Let this part be αr. Then t1tj(α) = (1, α1, . . . , αr+1, . . . , αk) = tjt1(α).Now consider the case where i ≥ 2. Clearly, if either i−1 or j−1 is not a part of α,we have titj(α) = tjti(α) = 0. If both i−1 and j−1 are parts of α, let αr and αs be theirleftmost occurrences in α respectively. It is easily seen that the application of either ti first28or tj first does not change the position of the leftmost instance of a part equalling j−1 ori−1 in α respectively. Hence titj = tjti for |i−j| ≥ 2.2.5.2 Box removing operatorsThe box removing operators on compositions, denoted by di for i ≥ 1, have the followingdescription: di(α) = α′ where α′ is the composition obtained by subtracting 1 from therightmost part of length i in α and omitting any 0s that might result in so doing. If there isno such part, then di(α) = 0.Example 2.5.3. Let α = (2, 1, 2). Then d1(α) = (2, 2), d2(α) = (2, 1, 1), and d3(α) = 0.Given a nonempty set of positive integers S = {b1 < b2 < · · · < br}, we will also beneeding the following product of box removing operators.vS = db1db2 · · · dbrNote that the product above is not commutative, and we will consider vS as operators dbr ,dbr−1 , . . ., db1 applied in succession to a composition, in that order. As a matter of convention,v∅ is to be interpreted as the identity map. Of particular interest to us is the operator v[i] fori ≥ 1, where [i] = {1, . . . , i}. We define [0] to be the empty set ∅. Then v[0] is the identitymap.2.5.3 Jeu de taquin operatorsNext, define an operator ai that appends a part of length i to a composition α at the end,for i ≥ 1. For example, a2((2, 1, 3)) = (2, 1, 3, 2). Notice also that ajd2((3, 5, 1)) = 0 for anypositive integer j, as d2((3, 5, 1)) = 0.With the definitions of ai and v[i], we can define the jeu de taquin operators (henceforthabbreviated to jdt operators), ui for i ≥ 1, as follows.ui = aiv[i−1]We will be using the jdt operators for studying the change in underlying shape when applyingbackward jeu de taquin slides on SSRCTs. Additionally, the role played by the box addingoperators in the left Pieri rule stated in the previous section, is played by these operators inthe right Pieri rules in Chapter 4.29Example 2.5.4. We will compute u4(α) where α = (6, 3, 2, 3, 1, 5, 4). Firstly, d1d2d3(α) =(6, 3, 2, 1, 5, 4), and thus a4v[3](α) = (6, 3, 2, 1, 5, 4, 4).Remark 2.5.5. Let α be a composition and λ = α˜. Let β = ui(α) for some positive integeri. Then β˜ is the partition obtained by adding a box at the addable node to λ in column i.2.6 Statement of main resultsAfter setting up the necessary notation, we will state our main results in the next twosubsections.2.6.1 A noncommutative Murnaghan-Nakayama ruleLet α and β be compositions such that α <c β. Define the support, supp(β/α), as follows.supp(β/α) = {j : (i, j) ∈ β/α}The skew reverse composition shape β/α whose support is an interval in Z≥1 will be calledan interval shape. Finally, an interval shape β/α will be called an nc border strip if it satisfiesthe following conditions.1. If there exist boxes in positions (i, 1) and (i, 2) in β/α, then the box in position (i, 1)is the bottommost box in column 1 of β/α.2. If there exist boxes in positions (i, j) and (i, j + 1) in β/α for j ≥ 2, then the box inposition (i, j) is the topmost box in column j of β/α.Given an nc border strip β/α, its height ht(β/α) is defined to be one less than the numberof rows it occupies, that is, one less than the number of rows that contain a non-zero numberof boxes. An nc border strip can be seen in Example 2.6.1.Suppose we are given an interval shape β/α. We discuss three notions that have to dowith the relative positions of boxes in consecutive columns of β/α. We say that column j+1is south-east of column j in β/α if there is a box in column j + 1 that is strictly south-eastof a box in column j. We say that column j + 1 is north-east of column j, if for any pair ofboxes (i1, j + 1) and (i2, j) in β/α, we have i1 < i2. Here, we assume that there exists atleast one box in the j + 1-th column. Finally, we say that column j + 1 is east of column jif there are boxes in positions (i, j) and (i, j + 1) for some i.30This given, we associate three statistics with an interval shape β/α as follows.E(β/α) = {j : column j + 1 is east of column j}SE(β/α) = {j : column j + 1 is south-east of column j and j /∈ E(β/α) }NE(β/α) = {j : column j + 1 is north-east of column j}The statistic NE(β/α) will play a crucial role in our noncommutative Murnaghan-Nakayamarule.Example 2.6.1. Consider the following interval shape β/α, where the shaded boxes belongto the outer shape.In this case we have E(β/α) = {1, 4}, SE(β/α) = {2}, NE(β/α) = {3}. Notice that theabove interval shape is an nc border strip whose height is 3.Remark 2.6.2. Given an interval shape β/α, note that E(β/α), SE(β/α), NE(β/α) arealways pairwise disjoint. Furthermore, if p is the maximum element of supp(β/α), then wehavesupp(β/α) = {p} unionmulti E(β/α) unionmulti SE(β/α) unionmultiNE(β/α).Now, given a positive integer n, consider the following sets of compositions.Bα,n = {β : α <c β and β/α is an nc border strip of size n}Pα,n = {β : β ∈ Bα,n, |NE(β/α)| = 0}Thus, Pα,n consists of all compositions β such that β/α is an nc border strip of size nsatisfying |NE(β/α)| = 0. This given, we can write down our analogue of the Murnaghan-Nakayama rule for noncommutative Schur functions as follows.Theorem 2.6.3 (Noncommutative Murnaghan-Nakayama rule). Given a composition α anda positive integer n, we have the following expansion.Ψn · sα =∑β∈Pα,n(−1)ht(β//α)sβ31Example 2.6.4. Consider the computation of Ψ4 · s(2,1,3). We need to find all compositionsβ ∈ B(2,1,3),4 satisfying |NE(β/ (2, 1, 3))| = 0. We will start by listing all the elementsof B(2,1,3),4 where the boxes of β/α will be shaded. Furthermore, if β is underlined, then|NE(β/ (2, 1, 3)| ≥ 1.To illustrate the parity condition, we will compute the coefficient of.Since ht((4, 3, 3)/ (2, 1, 3)) = 1, the coefficient of s(4,3,3) in Ψ4 · s(2,1,3) is −1. The completeexpansion is as follows.Ψ4 · s(2,1,3) = −s(1,1,1,1,2,1,3) + s(1,1,2,2,1,3) − s(1,1,1,2,2,3) + s(1,2,2,2,3) − s(1,3,2,1,3) + s(1,2,3,1,3)+s(2,3,2,3) − s(3,2,2,3) − s(3,3,1,3) + s(1,3,3,3) + s(4,2,1,3) − s(3,2,1,4) − s(2,4,1,3)+s(2,3,1,4) − s(4,3,3) + s(3,3,4) + s(6,1,3) − s(3,1,6) − s(5,1,4) + s(2,1,7)2.6.2 Jeu de taquin and right Pieri rulesWe will now state our algorithm for our analogue of the classical backward jeu de taquinslide. We will work under the following assumptions in this subsection and for all the proofsin the Chapter 4, unless otherwise stated.32• i will denote a positive integer ≥ 1.• T will refer to a fixed SSRT of shape λ.• The SSRCT ρ−1(T ) will be denoted by τ and we will assume that it has shape α whereα clearly satisfies α˜ = λ.• There exists an addable node in column i+ 1 of λ.2.6.3 Backward jeu de taquin slides for SSRCTsWith the notation from above, define a positive integer r1 to be such that such that αr1 is thebottommost part of length i in α. This given define positive integers rj for j ≥ 2 recursivelysubject to the following conditions.I. rj < rj−1.II. rj is the greatest positive integer such that τ(rj, i) > τ(rj−1, i) ≥ τ(rj, i+ 1). If the boxin position (rj, i+ 1) does not belong to τ , we let τ(rj, i+ 1) equal 0.Clearly the rjs defined above are finitely many. Let rk denote the minimum element andS = {r1 > · · · > rk}. Next we give an algorithm φi+1 that takes τ as input and outputs anSSRCT φi+1(τ) using the set S above.Algorithm 2.6.5.(i) For j=k down to 1 in that order,• Replace the entry in box (rj, i) by the entry in box (rj−1, i). The entry τ(rk, i)exits the tableau in every iteration.• Remove the box in position (r1, i).(ii) Denote the resulting filling by φi+1(τ).We will use the above algorithm and give a procedure on SSRCTs of straight shape,referred to as µi, and this is analogous to the procedure jdti on SSRTs of straight shape.Our input is again τ and the output is an SSRCT µi(τ).Algorithm 2.6.6 (Backward jeu de taquin slides for SSRCTs).33(i) If i ≥ 2, compute first the SSRCT φ2 ◦ · · · ◦ φi(τ). Denote this by τ ′. If i = 1, defineτ ′ to be τ . Furthermore, store the entries that exit in an array H, in the case i ≥ 2.(ii) Let sh(τ ′) = γ = (γ1, . . . , γk). Let δ = (γ1, . . . , γk, i).(iii) Consider a filling of the skew reverse composition shape δ/ (1) where the top k rows arefilled according to τ ′, and the last row is filled by the entries in H in decreasing orderfrom left to right.(iv) The filling of the skew reverse composition shape δ/ (1) obtained above is defined to beµi(τ).Now we will state a theorem that gives credence to our claim that µi is analogous to jdti.Theorem 2.6.7. With the notation as before, the following diagram commutes.SSRTsjdtiρ−1// SSRCTsµiSSRTsρ−1(1)// SSRCTsExample 2.6.8. Given below is an SSRT T (left) and the SSRCT τ = ρ−1(T ) (right).T =819 9 624 17 7 326 23 18 1037 28 25 2043 35 27 22 16 12 144 38 36 29 21 15 4 247 42 41 33 32 31 13 548 46 45 40 39 34 30 14 11τ =819 17 7 324 23 18 1026 9 637 35 27 22 21 15 13 543 42 41 40 39 34 30 14 1144 38 36 33 32 31 4 247 46 45 29 16 12 148 28 25 20We will compute µ9(τ). We start by computing φ2 ◦ · · · ◦ φ9(τ). To comprehensivelyillustrate the theorem, this is shown step by step below. The entries in rows rj for 1 ≤ j ≤ kthat we need in applying Algorithm 2.6.5 are depicted in green, except the entry that exits,34which is depicted in red.819 17 7 324 23 18 1026 9 637 35 27 22 21 15 13 543 42 41 40 39 34 30 14 1144 38 36 33 32 31 4 247 46 45 29 16 12 148 28 25 20819 17 7 324 23 18 1026 9 637 35 27 22 21 15 13 243 42 41 40 39 34 30 14 1144 38 36 33 32 31 447 46 45 29 16 12 148 28 25 20819 17 7 324 23 18 1026 9 637 35 27 22 21 15 4 243 42 41 40 39 34 30 14 1144 38 36 33 32 31 147 46 45 29 16 1248 28 25 20φ9(τ) φ8 ◦ φ9(τ) φ7 ◦ φ8 ◦ φ9(τ)819 17 7 324 23 18 1026 9 637 35 27 22 21 15 4 243 42 41 40 39 31 30 14 1144 38 36 33 32 12 147 46 45 29 1648 28 25 20819 17 7 324 23 18 1026 9 637 35 27 22 21 15 4 243 42 41 40 32 31 30 14 1144 38 36 33 16 12 147 46 45 2948 28 25 20819 17 7 324 23 18 1026 9 637 35 27 22 21 15 4 243 42 41 33 32 31 30 14 1144 38 36 29 16 12 147 46 45 2048 28 25φ6 ◦ · · · ◦ φ9(τ) φ5 ◦ · · · ◦ φ9(τ) φ4 ◦ · · · ◦ φ9(τ)819 17 7 324 23 18 1026 9 637 35 27 22 21 15 4 243 42 41 33 32 31 30 14 1144 38 36 29 16 12 147 46 25 2048 28819 17 7 324 23 18 1026 9 637 35 27 22 21 15 4 243 42 41 33 32 31 30 14 1144 38 36 29 16 12 147 28 25 2048φ3 ◦ · · · ◦ φ9(τ) φ2 ◦ · · · ◦ φ9(τ)35Thus, finally we have the following.819 17 7 324 23 18 1026 9 637 35 27 22 21 15 4 243 42 41 33 32 31 30 14 1144 38 36 29 16 12 147 28 25 2048 46 45 40 39 34 13 5819 9 624 17 7 326 23 18 1037 28 25 2043 35 27 22 16 12 144 38 36 29 21 15 4 247 42 41 33 32 31 30 13 548 46 45 40 39 34 14 11µ9(τ) jdt9(T )One can see that ρ(1)(µ9(τ)) = jdt9(T ).2.6.4 Right Pieri rulesNext we will state our right Pieri rules using jdt operators and then give an example.Theorem 2.6.9 (Right Pieri rules). Let α be a composition and n a positive integer. Thensα · s(n) =∑β|α|+n,uin ···ui1 (α)=βin>···>i1sβ,sα · s(1n) =∑β|α|+n,uin ···ui1 (α)=βin≤···≤i1sβ.In the statement above, (1n) denotes the composition with n parts equalling 1 each.Example 2.6.10. Let α = (1, 4, 2). We will compute sα · s(3) first. Thus, we are interestedin finding positive integers i1 < i2 < i3 such that ui3ui2ui1(α) is a composition of size 10.One can see that we have the following choices.u3u2u1(α) = (1, 4, 2, 3) u5u2u1(α) = (1, 2, 2, 5) u4u3u1(α) = (1, 4, 1, 4)u5u3u1(α) = (1, 3, 1, 5) u6u5u1(α) = (1, 2, 1, 6) u4u3u2(α) = (4, 2, 4)u5u3u2(α) = (3, 2, 5) u6u5u2(α) = (2, 2, 6) u5u4u3(α) = (1, 4, 5)u6u5u3(α) = (1, 3, 6) u7u6u5(α) = (1, 2, 7)36This gives us the following expansion for s(1,4,2) · s(3).s(1,4,2) · s(3) = s(1,4,2,3) + s(1,2,2,5) + s(1,4,1,4) + s(1,3,1,5) + s(1,2,1,6) + s(4,2,4)+s(3,2,5) + s(2,2,6) + s(1,4,5) + s(1,3,6) + s(1,2,7)Next, we compute sα · s(1,1,1). Then we are interested in finding positive integers i1 ≥ i2 ≥ i3such that ui3ui2ui1(α) is a composition of size 10. Thus, we have the following choices.u1u1u1(α) = (1, 4, 2, 1, 1, 1) u1u1u2(α) = (4, 2, 2, 1, 1) u1u1u3(α) = (1, 4, 3, 1, 1)u1u1u5(α) = (1, 2, 5, 1, 1) u1u2u3(α) = (4, 3, 2, 1) u1u2u5(α) = (2, 5, 2, 1)u1u3u5(α) = (1, 5, 3, 1) u2u3u5(α) = (5, 3, 2)This gives us the following expansion for s(1,4,2) · s(1,1,1).s(1,4,2) · s(1,1,1) = s(1,4,2,1,1,1) + s(4,2,2,1,1) + s(1,4,3,1,1) + s(1,2,5,1,1) + s(4,3,2,1)+s(2,5,2,1) + s(1,5,3,1) + s(5,3,2)37Chapter 3A Murnaghan-Nakayama rule fornoncommutative Schur functionsIn this chapter, we will give a proof for Theorem 2.6.3. We will start by discussing somecombinatorics of box adding operators. More specifically, we describe how sequences of boxadding operators correspond to SRCTs, and then we recast the left Pieri rules (Theorem2.4.7) in terms of box adding operators.3.1 Box adding operators, Pieri rules and reversehookwords3.1.1 SRCTs associated with sequence of box adding operatorsLet α be a composition and suppose w = ti1 · · · tin is such that w(α) = β, where β is not 0.Then, by [4, Proposition 2.11], we see that there is a unique SRCT of shape β/α associatedwith the word w, as we can associate the following maximal chain in Lc with w.αlc tin(α)lc · · ·lc ti2 · · · tin(α)lc ti1 · · · tin(α) = βThis maximal chain in turn gives rise to a unique SRCT of size n and shape β/α, wheren− i+ 1 is placed in the i-th box added.Example 3.1.1. Let α = (1, 3, 2) and β = t2t4t1t2t3(α) = (2, 2, 4, 3). Then w = t2t4t1t2t338uniquely corresponds to the following SRCT of shape β/α.3 14253.1.2 Pieri rules using box adding operatorsLet CComp denote the vector space consisting of formal sums of compositions. Considerthe map Φ : NSym −→ CComp defined by sending sα 7→ α and extending linearly. Wegive CComp an algebra structure by defining the product between two composition α · β asfollows.α · β = Φ(Φ−1(α) · Φ−1(β))It is easily seen that with the above definition of Φ, we have an C-algebra isomorphismbetween NSym and CComp. We will freely use the notation α · β to denote the productsα · sβ, and for the sake of convenience, we will not distinguish between sα · sβ and Φ(sα · sβ).With the above setup and armed with the definition of box adding operators, we restateTheorem 2.4.7 in the language of box adding operators.Proposition 3.1.2. Let α be a composition and n be a positive integer. Then(n) · α =(∑in>···>i1tin · · · ti1)(α),(1n) · α =(∑in≤···≤i1tin · · · ti1)(α).Recall now Equation (2.1) which gives the following expansion.Ψn =n−1∑k=0(−1)kr(1k,n−k). (3.1)Thus, in order to to obtain a noncommutative analogue of the Murnaghan-Nakayama rule,we would like to compute r(1k,n−k) · sα using box adding operators. Note that we alreadyknow the answer in the special cases k = 0 or k = n− 1, as these are the cases encompassedby Proposition 3.1.2. To this end, we will need some more notation, which is the aim of the39next subsection.3.1.3 Reverse hookwords and multiplication by r(1k,n−k)Given positive integers n and k such that 0 ≤ k ≤ n−1, define w = ti1 . . . tin to be a reversek-hookword if i1 ≤ i2 ≤ · · · ≤ ik+1 > ik+2 > · · · > in. If w is a reverse k-hookword forsome k, then we will call w a reverse hookword. Denote by supp(w) the set formed by theindices i1, . . . , in (by discarding duplicates). Call w connected if supp(w) is an interval inZ≥1, otherwise call it disconnected. Put differently, w is connected if the set of indices, whenconsidered in ascending (or descending) order, form a contiguous block of positive integers.LetRHWn = set of reverse hookwords of length n,CRHWn = set of connected reverse hookwords of length n.Moreover, let RHWn,k denote the subset of RHWn consisting of reverse k-hookwords.For the same w as before, we define the content vector of w to be a finite ordered list ofnonnegative integers (c1, c2, . . .) where ci denotes the number of times the operator ti appearsin w. Also associated with w are the notions of arm(w) and leg(w) defined as follows.arm(w) = {ij : 1 ≤ j ≤ k + 1}leg(w) = {ij : k + 1 ≤ j ≤ n}We note that arm(w) is a multiset, while leg(w) is a set. Finally, letasc(w) = |arm(w)| − 1 = n− |leg(w)|.Example 3.1.3. Let w = t2t5t6t7t8t8t9t9t7t6t4t3. Then w is a connected reverse 7-hookwordwith content vector given by (0, 1, 1, 1, 1, 2, 2, 2, 2). Furthermore, we also have thatarm(w) = {9, 9, 8, 8, 7, 6, 5, 2},leg(w) = {3, 4, 6, 7, 9}.Now, using reverse hookwords, we can express the multiplication of noncommutativeSchur functions by noncommutative ribbon Schur functions in terms of box adding operators.40Lemma 3.1.4. Let 0 ≤ k ≤ n− 1, and let α be a composition. Thenr(1k,n−k) · sα =∑w∈RHWn,kw (α).Proof. Note first that in the case k = 0, the claim is true as it is equivalent to the firstidentity of Proposition 3.1.2. We will establish the claim by induction on k. Assume thatthe claims holds for all integers ≤ k for some k ≥ 1. We will compute (r(1k+1) · r(n−k−1)) · sαin two ways. First notice that by using Theorem 2.4.1, we get(r(1k+1) · r(n−k−1)) · sα = r(1k+1,n−k−1) · sα + r(1k,n−k) · sα. (3.2)Now, using Proposition 3.1.2, we have that(r(1k+1) · r(n−k−1)) · sα =∑i1≤···≤ik+1ti1 · · · tik+1∑ik+2>···>intik+2 · · · tin (α)=∑w∈RHWn,kw (α) +∑w′∈RHWn,k+1w′ (α). (3.3)By the induction hypothesis we know thatr(1k,n−k) · sα =∑w∈RHWn,kw (α). (3.4)Now, using (3.2), (3.3) and (3.4), the claim follows.413.2 Multiplication by noncommutative power sums interms of box adding operatorsOn using the definition of the noncommutative power sum function Ψn in terms of thenoncommutative ribbon Schur functions, and Lemma 3.1.4 subsequently, we get thatΨn · sα =(n−1∑k=0(−1)kr(1k,n−k))· sα=n−1∑k=0(−1)k∑w∈RHWn,kw(α)=∑w∈RHWn(−1)asc(w)w(α). (3.5)Using the involution described in Section 5 of [10], we can simplify (3.5) so that the sum runsover the set of connected reverse hookwords. For completeness, we give a summary of thisinvolution next. Let w be a disconnected reverse hookword and let its content vector be β.Let j be the smallest integer such that j + 1 /∈ supp(w), and j is not the maximum elementin supp(w). Such a j exists since supp(w) is not an interval. Then, if j ∈ leg(w), defineΘ(w) to be the unique reverse hookword with content vector β and leg(Θ(w)) = leg(w)\{j}.Similarly, if j ∈ arm(w) but j /∈ leg(w), then define Θ(w) to be the unique reverse hookwordwith content vector β and leg(Θ(w)) = leg(w)∪{j}. It is easy to see that Θ is an involutionon the set of disconnected reverse hookwords, but more importantly, from Lemma 2.5.2 itfollows that Θ(w)(α) = w(α). Furthermore, asc(w) and asc(Θ(w)) are of opposite parity.The preceding arguments allow us to rewrite (3.5) as follows.Ψn · sα =∑w∈CRHWn(−1)asc(w)w(α) (3.6)While the equation above is a legitimate way to compute Ψn · sα, it is not cancellation-free.Giving a cancellation-free expansion for Ψn · sα will be our aim in the next section.Example 3.2.1. We will compute Ψ2 · sα where α = (1, 3, 2). The possible elements of42CRHW2 are titi, titi+1 and ti+1ti for i ≥ 1. Thus, we haveΨ2 · s(1,3,2) =∑i≥1(ti+1ti−titi+1−t2i )((1, 3, 2))= (t2t1+t3t2+t4t3+t5t4−t1t2−t2t3 − t3t4 − t1t1)((1, 3, 2))= (2, 1, 3, 2)+(3, 3, 2)+(1, 4, 3)+(1, 5, 2)−(1, 2, 3, 2)−(2, 3, 3)−(1, 4, 3)−(1, 1, 1, 3, 2)= (2, 1, 3, 2)+(3, 3, 2)+(1, 5, 2)−(1, 2, 3, 2)−(2, 3, 3)−(1, 1, 1, 3, 2).Note that this example reaffirms our claim that (3.6) is not cancellation-free. The composi-tion (1,4,3) appeared once with coefficient 1, and once with coefficient -1. Hence it does notappear in the final result.3.3 The Murnaghan-Nakayama rule fornoncommutative Schur functionsBy (3.6) we know thatΨn · sα =∑βkβsβ (3.7)wherekβ =∑w∈CRHWnw(α)=β(−1)asc(w).Thus, our aim is to compute kβ given any composition β. Considering the equation above,it would be helpful to be able to tell, given the reverse composition diagrams of α and β,whether there exists a connected reverse hookword w such that w(α) = β. To this end, wewill recall the notion of an nc border strip introduced in Section 2.6.Let α and β be compositions such that α <c β. Define the support, supp(β/α), as follows.supp(β/α) = {j | (i, j) ∈ β/α}The skew reverse composition shape β/α whose support is an interval in Z≥1 will be calledan interval shape. Finally, an interval shape β/α will be called an nc border strip if it satisfiesthe following conditions.431. If there exist boxes in positions (i, 1) and (i, 2) in β/α, then the box in position (i, 1)is the bottommost box in column 1 of β/α.2. If there exist boxes in positions (i, j) and (i, j + 1) in β/α for j ≥ 2, then the box inposition (i, j) is the topmost box in column j of β/α.Suppose we are given an interval shape β/α. We discuss three notions that have to dowith the relative positions of boxes in consecutive columns of β/α. We say that column j+1is south-east of column j in β/α if there is a box in column j + 1 that is strictly south-eastof a box in column j. We say that column j + 1 is north-east of column j, if for any pair ofboxes (i1, j + 1) and (i2, j) in β/α, we have i1 < i2. Here, we assume that there exists atleast one box in the j + 1-th column. Finally, we say that column j + 1 is east of column jif there are boxes in positions (i, j) and (i, j + 1) for some i.This given, we associate three statistics with an interval shape β/α as follows.E(β/α) = {j : column j + 1 is east of column j}SE(β/α) = {j : column j + 1 is south-east of column j and j /∈ E(β/α) }NE(β/α) = {j : column j + 1 is north-east of column j}Example 3.3.1. Consider the following interval shape β/α, where the shaded boxes belongto the outer shape.In this case we have E(β/α) = {1, 4}, SE(β/α) = {2}, NE(β/α) = {3}. Notice that theabove interval shape is an nc border strip whose height is 3.Remark 3.3.2. Given an interval shape β/α, note that E(β/α), SE(β/α), NE(β/α) arealways pairwise disjoint. Furthermore, if p is the maximum element of supp(β/α), then wehavesupp(β/α) = {p} unionmulti E(β/α) unionmulti SE(β/α) unionmultiNE(β/α).44Now, consider the following two setsAα,n = {β : β = w(α) for some w ∈ CRHWn},Bα,n = {β : α <c β and β/α is an nc border strip of size n}.Our next aim is to establish that Aα,n = Bα,n. This means that we will be able to replacechecking whether there exists w ∈ CRHWn such that w(α) = β with checking whether β/αis an nc border strip.Lemma 3.3.3.Bα,n ⊆ Aα,n.Proof. To establish the claim, we need to show that given β ∈ Bα,n (that is, β/α is annc border strip), there exists a w ∈ CRHWn such that w(α) = β. We will construct anSRCT of shape β/α that will be associated (in the sense of Section 3.1.1) with an elementof CRHWn.Let E(β/α) = {x1 < · · · < xs}. For every xi, place the integer n− i+ 1 in the topmostbox of the xi-th column of β/α if xi > 1 and in the bottommost box if xi = 1. After thisstep, traverse the remaining n− s unfilled boxes in β/α in the manner described below andplace the integers n− s down to 1 in that order.• Start from the rightmost column that contains an empty box.• Visit every empty box from top to bottom if column under consideration is not thefirst column, otherwise visit boxes from bottom to top.• Repeat the above steps for the next rightmost column in β/α that contains an emptybox.We claim that the resulting filling, which we call τ , is an SRCT. By construction, if 1 ∈supp(β/α), then the entries in the boxes in column 1 strictly increase from top to bottom.In all other columns, the entries decrease from top to bottom.To show that entries decrease from left to right along rows, assume first the existenceof boxes in position (i, j) and (i, j + 1) in β/α. Clearly j ∈ E(β/α). Since β/α is an ncborder strip, we know that the box in position (i, j) is the topmost box in the j-th columnof β/α if j ≥ 2, and is the bottommost box if j = 1. By our construction of the filling, ifj ∈ E(β/α), every box of β/α in column j + 1 contains a number strictly less than τ(i,j).45Hence in particular, τ(i,j) > τ(i,j+1) and thus, the entries decrease from left to right alongrows.Now we have to show that there are no triple rule violations in τ . Since, in every columnk where k ≥ 2, the entries decrease from top to bottom, we are guaranteed there are notriple rule violations of the formτ(i,j) τ(i,j+1)...τ(i′,j+1)where j ≥ 1, and (i′, j + 1), (i, j + 1) ∈ β/α with i′ > i.Now assume that (i, j + 1) /∈ β/α. We will show that τ(i,j) < τ(i′,j+1) for any i′ > i where(i′, j + 1) ∈ β/α. Assume first that j ∈ E(β/α). If j = 1, then we know that (i, j) isnot the bottommost box in column j of β/α, as (i, j + 1) /∈ β/α. Thus, by construction,τ(i,j) is strictly less than every entry in column 2. In particular, τ(i′,j+1) > τ(i,j), and we donot have triple rule violations. If j ≥ 2, then we know that the box in position (i, j) is notthe topmost box in column j. Again, we have that τ(i,j) is strictly less than every entry incolumn j + 1, and as before, we have no triple rule violations.Now suppose that (i, j+1) /∈ β/α, and that j /∈ E(β/α). Then, the way the filling τ hasbeen constructed implies that the greatest entry in column j is less than the smallest entryin column j + 1. This guarantees that τ(i′,j+1) > τ(i,j), and we have no triple rule violations.Hence, τ is an SRCT. Clearly, the word associated with τ is an element of RHWn. Thefact that it is an element of CRHWn follows from the fact that β/α is an interval shape.Hence there exists a w ∈ CRHWn such that w(α) = β, implying β ∈ Aα,n.Next, we give an example of the construction presented in the algorithm above.Example 3.3.4. Consider the shape β/α presented in Example 3.3.1.Here |β/α| = 6. Hence we will be placing the numbers 1 to 6 in the shaded boxes above.46Since E(β/α) = {1, 4}, the bottommost box in column 1 of β/α will have 6 placed in it,while the topmost box in column 4 will have 5 placed in it. Now the columns with emptyboxes, considered from right to left, are 5, 3 and 2. We fill in these boxes with the numbers4, 3, 2, 1 in that order from top to bottom in each column to obtain the following filling.6 25 413Lemma 3.3.5. Suppose w ∈ CRHWn is such that w(α) = β. Let τ be the SRCT of shapeβ/α corresponding to the word w. Then, the entries in τ in column j strictly decrease fromtop to bottom for all j ≥ 2.Proof. Suppose w has c occurrences of tj where j ≥ 2. We can then factorize w as followsw = w3tc−1j w2tjw1, (3.8)where w1, w2 could be empty words. Notice that since w is a reverse hookword, all theoperators that constitute w2 are of the form tk where k > j. Hence they only add boxes toparts of length ≥ j in the composition tjw1(α). Now tc−1j adds boxes in the j-th column.Thus, we have added c boxes in the j-th column and the definition of the box adding operatorsimplies that repeated applications of tj add boxes from top to bottom, when j ≥ 2. Hencethe entries in these c boxes strictly decrease from top to bottom.Next, we note down a couple of lemmas that are immediate consequences of the bijectionmentioned in Subsection 3.1.1. For Lemmas 3.3.6 and 3.3.7, and Corollary 3.3.8, we will workunder the assumption that w ∈ CRHWn is such that w(α) = β, and that τ is the SRCTof shape β/α corresponding to w. We will assume further that j belongs to supp(β/α) (orsupp(w)), but is not the greatest element therein.Lemma 3.3.6. Suppose j /∈ leg(w) for some j ≥ 1. Then the greatest entry in column j ofτ is strictly less than the smallest entry in column j + 1 in τ .Lemma 3.3.7. Suppose j ∈ leg(w) for some j ≥ 1. Then• the greatest entry in column j of τ is strictly greater than the greatest entry in columnj + 1 in τ , and47• all other entries in column j of τ are strictly smaller than the smallest entry in columnj + 1 in τ .We will note down an important corollary of the two lemmas above.Corollary 3.3.8. For all j ≥ 1, every entry in column j except the greatest one, is strictlysmaller than the smallest entry in column j + 1.Lemma 3.3.9.Aα,n = Bα,n.Proof. We have already shown in Lemma 3.3.3 that every element of Bα,n is an element ofAα,n. Thus, now we need to show that Aα,n ⊆ Bα,n.Assume β ∈ Aα,n. We have to show that β ∈ Bα,n as well. It is clear that if β = w(α) forsome w ∈ CRHWn, then α <c β. The fact that β/α is an interval shape of size n followsfrom the fact that w is connected and has length n. Let τ denote the SRCT of shape β/αcorresponding to w.Next, suppose there is a configuration of the following type.τ(i,j) τ(i,j+1)If τ(i,j) is not the greatest entry in column j, then Corollary 3.3.8 implies that τ(i,j) < τ(i,j+1),which contradicts the fact that τ is an SRCT. Hence τ(i,j) is the greatest entry in column j.Hence the box in position (i, j) is the bottommost box in column j if j = 1, or the topmostbox in column j otherwise, by invoking Lemma 3.3.5.This finishes the proof that β/α is an nc border strip if β ∈ Aα,n. Thus Aα,n ⊆ Bα,n,and we are done.Remark 3.3.10. A skew shape λ/µ is called a disconnected border strip if it is a disjointunion of border strips. Notice that if α is a composition such that α˜ = µ, and w ∈ CRHWnis such that w˜(α) = λ, then λ/µ is a disconnected border strip of size n whose support is aninterval. Equivalently if β/α is an nc border strip, then β˜/α˜ is a disconnected border stripwhose support is an interval. This explains our reasoning for calling β/α an nc border strip.We will outline our strategy for the remainder of this section. Now that we have estab-lished that Aα,n = Bα,n, our next aim is to enumerate all hookwords w such that w(α) = β48where β ∈ Bα,n, that is, β/α is an nc border strip of size n. This will be achieved in Lemma3.3.16. Once this is done, we will be able to compute the coefficientkβ =∑w∈CRHWnw(α)=β(−1)asc(w).Recall that kβ was defined to be the coefficient of sβ in the expansion Ψn · sα. This willgive us a noncommutative analogue of the Murnaghan-Nakayama rule that we will state inTheorem 3.3.20.Lemma 3.3.11. Given β ∈ Bα,n, if for any w ∈ CRHWn such that w(α) = β we have thatcolumn j ∈ E(β/α), then j ∈ leg(w).Proof. Let τ be the SRCT of shape β/α corresponding to the word w = ti1 · · · tin . Ifj ∈ E(β/α), then there exists a configuration in β/α of the following form.τ(i,j) τ(i,j+1)We know that τ(i,j) > τ(i,j+1), and this implies that there exists 1 ≤ p < q ≤ n such thattip = tj+1 and tiq = tj. But since w is a reverse hookword, this immediately implies thatj ∈ leg(w).Lemma 3.3.12. Given β ∈ Bα,n, if for any w ∈ CRHWn such that w(α) = β we have thatcolumn j ∈ SE(β/α), then j /∈ leg(w).Proof. Let τ be the SRCT of shape β/α corresponding to the word w. Assume first thatj = 1. Let the bottommost box in the first column of β/α be in position (i, 1). Since1 ∈ SE(β/α), we know that all boxes in column 2 that belong to β/α lie strictly southeastof the box in position (i, 1). Notice that τ(i,1) is the greatest amongst all the numbers incolumn 1 of τ . We have the following configuration in τ .τ(i,1)...τ(i′,2)Since τ is an SRCT, we know that τ(i′,2) > τ(i,1). Thus in particular, the smallest entry inthe second column of τ is strictly greater than τ(i,1). Thus, the first time a box is added in49the first column happens after all the boxes that were to be added in the second column byw have been added. Hence 1 /∈ leg(w).Now assume j ≥ 2. Let τ(i,j) be the entry in the topmost box of the j-th column of τ .This entry is greater than every other entry in the j-th column of τ by Lemma 3.3.5. Sincej ∈ SE(β/α), we are guaranteed the existence of a box in position (i′, j + 1) where i′ > i.Arguing like before, we must have τ(i′,j+1) > τ(i,j). Hence there is at least one entry in thej + 1-th column of τ that is greater than every entry in the j-th column of τ . Given that wis a reverse hookword, this implies that j /∈ leg(w).Lemma 3.3.13. Let β ∈ Bα,n. If j ∈ NE(β/α), then j ≥ 2.Proof. Let w ∈ CRHWn be such that w(α) = β. Assume that the claim is not true. Hence1 ∈ NE(β/α). Thus, we must have that {1, 2} ⊆ supp(β/α). If 1 ∈ leg(w), then the waythe box adding operators act implies that 1 ∈ E(β/α), as t2 will add a box adjacent to anewly added box resulting from the operator t1 applied before it.Now, assume 1 /∈ leg(w). Then w factors uniquely as tk1w1, where w1 has no instances oft1. Then we know that in computing tk1(w1(α)), the boxes added in column 1 will be strictlynorthwest of the boxes added in column 2 while computing w1(α). This also follows fromhow t1 acts. But then 1 ∈ SE(β/α). Again, this is a contradiction. Hence we must havethat j ≥ 2.Lemma 3.3.14. Let j ≥ 2 be a positive integer and µ be a composition. Suppose that µ hasparts equalling j and j− 1 and that the number of parts that equal j and lie to the left of theleftmost instance of a part equalling j − 1 is m. Then for all 0 ≤ k ≤ m, we havetjtkj+1(µ) = tkj+1tj(µ).Proof. The case where m = 0 is trivial. Assume that m ≥ 1.The operator tkj+1 adds a box to each of the k leftmost parts in µ that equal j. We knowthat there are m parts in µ that equal j and lie to the left of the leftmost instance of a partthat equals j − 1. Since k ≤ m, we are guaranteed that tjtkj+1(µ) = tkj+1tj(µ).Lemma 3.3.15. Suppose β ∈ Bα,n and that j ∈ NE(β/α). Let w ∈ CRHWn such thatw(α) = β. Define an element w′ ∈ CRHWn as follows.• If j ∈ leg(w), then let w′ be the unique reverse hookword with the same content as wobtained by setting leg(w′) = leg(w) \ {j}.50• If j /∈ leg(w), then let w′ be the unique reverse hookword with the same content as wobtained by setting leg(w′) = leg(w) ∪ {j}.Then w′(α) = β.Proof. Since j ∈ NE(β/α), we know that j is not the maximum element of supp(β/α).Hence, either j ∈ leg(w) or j /∈ leg(w). Thus, the word w′ is well-defined. Furthermore, byLemma 3.3.13 we know that j ≥ 2.Let the number of tj+1 in w equal c where c ≥ 1. Let the largest common suffix of wand w′ be w1. All operators tk that appear in w1 satisfy k ≤ j − 1. Let µ = w1(α). Sincej ∈ NE(β/α), we know that there are at least c instances of a part of length j to theleft of the leftmost part of length j − 1 in µ. Thus tjtmj+1(µ) = tmj+1tj(µ) for 0 ≤ m ≤ cby Lemma 3.3.14. This combined with the fact that tjti = titj for i − j ≥ 2 implies thatw(α) = w′(α) = β, as required.Lemma 3.3.16. If β ∈ Bα,n, then the number of words w ∈ CRHWn such that w(α) = βequals 2|NE(β//α)|.Proof. Let p be the maximum element of supp(β/α). Then, by Remark 3.3.2, we know thatsupp(β/α) = {p} unionmulti E(β/α) unionmulti SE(β/α) unionmultiNE(β/α). (3.9)Let w be an element of CRHWn such that w(α) = β. Since we know that the number ofinstances of tk in w is equal to the number of boxes in column k of β/α, w is completelydetermined by leg(w).Now by Lemma 3.3.11, we have that every element of E(β/α) belongs to leg(w). Lemma3.3.12 implies that every element of SE(β/α) does not belong to leg(w). As far as elementsof NE(β/α) are concerned, we know by Lemma 3.3.15, that it does not matter whetherthey belong to leg(w) or not, as the final shape β is going to be the same. Thus, for everysubset X ⊆ NE(β/α), the word w ∈ CRHWn satisfyingleg(w) = E(β/α) unionmultiX unionmulti {p} (3.10)has the property that w(α) = β. Hence the number of such words is 2|NE(β//α)| as claimed.Lemma 3.3.17. Let β ∈ Bα,n. Then∑w∈CRHWnw(α)=β(−1)asc(w) = (−1)n−1−|E(β//α)|δ0,|NE(β//α)|51where δ denotes the Kronecker delta function.Proof. Firstly, recall that asc(w) = |arm(w)| − 1. This in turn implies that asc(w) =n − |leg(w)|. By Lemma 3.3.11, we know that E(β/α) ⊆ leg(w). Further, if p is themaximum element of supp(w), then p ∈ leg(w) as well. Lemma 3.3.16 implies that any subsetof NE(β/α) can belong to leg(w), and Lemma 3.3.12 gives that no element of SE(β/α)belongs to leg(w).Thus, we have the following sequence of equalities.∑w∈CRHWnw(α)=β(−1)asc(w) =∑w∈CRHWnw(α)=β(−1)n−|leg(w)|=∑X⊆NE(β//α)(−1)n−1−|E(β//α)|−|X|= (−1)n−1−|E(β//α)|∑X⊆NE(β//α)(−1)|X|= (−1)n−1−|E(β//α)|δ0,|NE(β//α)| (3.11)What follows is essentially a restatement of the above lemma.Corollary 3.3.18. If β ∈ Bα,n thenkβ ={0 |NE(β/α)| ≥ 1(−1)n−1−|E(β//α)| |NE(β/α)| = 0.Now, consider the following set of compositions.Pα,n = {β : β ∈ Bα,n, |NE(β/α)| = 0}Before we state a Murnaghan-Nakayama rule in its final definitive form, we will need anothershort lemma.Lemma 3.3.19. If β/α is an nc border strip of size n, then n− 1− |E(β/α)| = ht(β/α).Proof. Suppose there are k > 0 boxes in some row of β/α, then this row contributes k − 1to |E(β/α)|. Let the number of boxes in rows that contain at least one box be k1, k2, . . . , kr52for some positive integer r. Notice that∑rj=1(kj − 1) equals n− r. Thus we have thatn− 1− |E(β/α)| = n− 1−r∑j=1(kj − 1)= r − 1. (3.12)Now notice that r − 1 is precisely ht(β/α).This given, we can write down our analogue of the Murnaghan-Nakayama rule for non-commutative Schur functions as follows.Theorem 3.3.20. Given a composition α and a positive integer n, we have the followingexpansion.Ψn · sα =∑β∈Pα,n(−1)ht(β//α)sβWhile we do not attempt it here, the above theorem can be used by compute the expansionof Ψ(γ1,...,γk) in the basis of noncommutative Schur functions. To see this, consider the equalitybelow.Ψ(γ1,...,γk) = Ψγ1 · · ·Ψγk · s∅Now applying Theorem 3.3.20 iteratively computes the desired expansion. Thus, in theory,we can compute the transition matrix between the basis of noncommutative power sumsymmetric functions and the noncommutative Schur functions using Theorem 3.3.20.Example 3.3.21. Consider the computation of Ψ4 ·s(2,1,3). We need to find all compositionsβ ∈ B(2,1,3),4 satisfying |NE(β/ (2, 1, 3))| = 0. We will start by listing all the elements ofB(2,1,3),4 where the boxes of β/α will be shaded. In the list below, beneath every compositionwe have noted those reverse hookwords that act on (2, 1, 3) to give the composition underconsideration. For the sake of clarity, the occurrences of t in the reverse hookwords havebeen suppressed. Thus, for example, 1121 denotes t1t1t2t1. Furthermore, if the words below53a composition β are underlined, then |NE(β/ (2, 1, 3)| ≥ 1.1111 1121 1112 1221 1321 1231 1132,11232231 2321 3321 1332 4321 3421 24312341 1432, 1243 1342,1234 4432,2443 5432,2543 3542,2354 34323342 6543 3654 4543 7654To illustrate the parity condition, we will compute the coefficient of.Since ht((4, 3, 3)/ (2, 1, 3)) = 1, the coefficient of s(4,3,3) in Ψ4 · s(2,1,3) is −1. The completeexpansion is as follows.Ψ4 · s(2,1,3) = −s(1,1,1,1,2,1,3) + s(1,1,2,2,1,3) − s(1,1,1,2,2,3) + s(1,2,2,2,3) − s(1,3,2,1,3) + s(1,2,3,1,3)+s(2,3,2,3) − s(3,2,2,3) − s(3,3,1,3) + s(1,3,3,3) + s(4,2,1,3) − s(3,2,1,4) − s(2,4,1,3)+s(2,3,1,4))− s(4,3,3) + s(3,3,4) + s(6,1,3) − s(3,1,6) − s(5,1,4) + s(2,1,7)54Chapter 4Jeu de taquin and right Pieri rulesIn this chapter, we will give proofs for the results in Subsection 2.6.3.4.1 Proof of validity of algorithm µiWe will work under the following assumptions in this section.• i will denote a positive integer ≥ 1.• T will refer to a fixed SSRT of shape λ.• The SSRCT ρ−1(T ) will be denoted by τ and we will assume that it has shape α whereα clearly satisfies α˜ = λ.• There exists an addable node in column i+ 1 of λ.A particular entry of T that plays a significant role in what follows is the first entrythat moves horizontally while computing jdti+1(T ). This entry is Tj,i where j is the largestinteger such that Tj,i < Tj−1,i+1. (We assume T0,s =∞ for all positive integers s.) We shalldenote this entry by fi+1(T ) (the reason behind the name being that it is the f irst entrythat moves horizontally). We will use this in the next couple of lemmas, whose proofs arestraightforward.Lemma 4.1.1. Let fi+1(T ) = Tr,i. Let T ′ be the tableau defined below.T ′p,q = Tp,q if q 6= iT ′p,i = Tp,i if p < rT ′p,i = Tp+1,i if p ≥ r.55Then T ′ is an SSRT.Remark 4.1.2. In words, T ′ is obtained from T by first removing Tr,i and sliding all en-tries above it in the i-th column down by one row. Note that the rest of the tableau is leftunchanged.Proof. The only thing we need to check is that the entries in each row of T ′ are weaklydecreasing when read from left to right. More specifically, it follows from the precedingremark that we only need to check if T ′j,i ≥ T′j,i+1 and T′j,i−1 ≥ T′j,i (assuming i ≥ 2 for thiscase) for j ≥ r.The former inequality is clear since T ′j,i = Tj+1,i and T′j,i+1 = Tj,i+1 for j ≥ r and by ourhypothesis Tr,i is the first entry that moves horizontally when a backward jeu de taquin slideis initiated from the i+ 1-th column.Now we will show that T ′j,i−1 ≥ T′j,i for j ≥ r. We have T′j,i = Tj+1,i and T′j,i−1 = Tj,i−1.But it is clear that Tj,i−1 > Tj+1,i in any SSRT T . Hence the claim follows.We will denote the SSRT T ′ above by tjdti+1(T ) (the reason behind the name tjdt isthat it stands for a ‘truncated’ jeu de taquin slide). Furthermore, we define tjdt1(T ) = T , asno entries move horizontally when a backward jeu de taquin slide is initiated from the firstcolumn.Example 4.1.3. LetT =67 68 7 410 8 511 9 9 8.If we consider a backward jeu de taquin slide from the addable node in column 3, then wehave f3(T ) = T2,2 = 8. Thustjdt3(T ) =678 6 410 7 511 9 9 8.56In the computation of jdti+1(T ), clearly i entries in T move horizontally. It is crucial forus to know these entries. DefineHi+1(T ) = multiset of entries in T that move horizontally under jdti+1(T ).We define H1(T ) to be the empty set. With this definition at hand, we state a second lemma.Lemma 4.1.4.Hi(tjdti+1(T )) ∪ {fi+1(T )} = Hi+1(T ).In the equality above, we are considering union of multisets.Proof. Let T ′ = tjdti+1(T ) and fi+1(T ) = Tr,i. Our construction of T′ implies that there isan addable node in column i in the partition shape underlying T ′. Hence, we can initiate abackward jeu de taquin slide from the i-th column of T ′ and Hi(T ′) is well-defined.If i = 1, then we have nothing to prove. Hence, we can assume that i ≥ 2. We willshow that no entry of the form T ′j,i−1 with j > r moves horizontally when a backward jeu detaquin slide is initiated from column i in T ′, as this clearly suffices to establish the claim.Suppose this was not the case. Then there exists j > r such thatT ′j,i−1 < T′j−1,i.Since T ′j,i−1 = Tj,i−1 and T′j−1,i = Tj,i for j > r, the inequality above impliesTj,i−1 < Tj,i.But this contradicts the fact that T is an SSRT.Example 4.1.5. LetT =67 68 7 210 8 5 311 9 9 8.If we consider a backward jeu de taquin slide from the addable node in column 4, then the57entries in the shaded boxes move horizontally. Thus, we haveH4(T ) = {2, 8, 11} and f4(T ) = 2.We also have thattjdt4(T ) =67 68 710 8 5 311 9 9 8.Now if one does a backward jeu de taquin slide on the tableau above from the third column,then the entries in the shaded boxes move horizontally, therefore H3(tjdt4(T )) = {8, 11}.Thus, we can verify in this case thatH4(T ) = H3(tjdt4(T )) ∪ f4(T ).The lemma above allows us to recursively compute all the entries that move horizontallywhen a backward jeu de taquin slide is performed from an addable node in column i + 1.We already know how to obtain tjdti+1(T ) given an SSRT T . Before we define a backwardjeu de taquin slide for SSRCTs, let us consider the relatively easier question of computingρ−1(tjdti+1(T )) given τ . This is precisely what the algorithm φi+1 described in Subsection2.6.3 achieves. We will establish that φi+1 maps SSRCTs to SSRCTs such that the followingdiagram commutes.SSRTstjdti+1ρ−1// SSRCTsφi+1SSRTsρ−1// SSRCTsTo allow for cleaner proofs, we will now describe how we will think of T and τ dia-grammatically. We will think of T as aligned to the left in a rectangular Ferrers diagramwherenumber of rows, n = l(λ),number of columns ≥ λ1 + 1.58The empty boxes of this Ferrers diagram are assumed to be filled with 0s. We will call thisdiagram T. Note that the 0s do not play any role as far as doing the backward jeu de taquinslides are concerned.Similarly, we will think of τ as being placed left aligned in a rectangular Ferrers diagramwherenumber of rows, n = l(α),number of columns ≥ λ1 + 1.The empty boxes of this Ferrers diagram are assumed to be filled with 0s. We will assumethat the dimensions of the rectangular Ferrers diagram are the same for both T and τ . Theexact dimensions will not matter as long as they satisfy the constraints mentioned above.We will call the rectangular filling τ.For computing tjdti+1(T ), we only need to know what the entries in columns i and i+ 1are. Since we will work with T we will take the 0s into account when considering the i-thand i+ 1-th columns. Let the i-th and i+ 1-th columns of T be as shown below.a1 b1a2 b2......an bnFurthermore, let an+1 = bn+1 =∞. Since we have assumed that there is an addable node inthe i+ 1-th column of λ, we know that|{br : br = 0, 1 ≤ r ≤ n}| > |{ar : ar = 0, 1 ≤ r ≤ n}|. (4.1)Letmin = smallest positive integer such that amin < bmin+1.Then, we have thatamin = fi+1(T ).Clearly, amin > 0. Another trivial observation, which we will use without mentioning is thatap = aq for some 1 ≤ p, q ≤ n if and only if ap = aq = 0.59Corresponding to T above, the i-th and i+ 1-th columns of τ are as shown below.c1 d1c2 d2......cn dnClearly the sequence c1, c2, . . . , cn is a rearrangement of the sequence a1, a2, . . . , an. Asimilar statement holds for the sequences d1, d2, . . . , dn and b1, b2, . . . , bn.Now let us consider what we require from the procedure φi+1. We would like it to locatefi+1(T ) in τ and then remove it from τ and rearrange the remaining entries so that whatwe have is still an SSRCT. The algorithm to accomplish this will be presented after someintermediate lemmas. For all the lemmas that follow, we will assume that s1 is the positiveinteger such thatcs1 = amin.Our first lemma implies that amin does not equal any other entry in the i-th and i+ 1-thcolumns of T. We know that amin > 0. Hence it clearly can not equal any other entry inthe i-th column since T is an SSRT. To see that amin does not equal any entry in the i+1-thcolumn, the following suffices.Lemma 4.1.6. amin 6= bmin.Proof. Assume, contrary to what is to be established, that amin = bmin. Since amin > 0, weget that min > 1, as b1 is definitely 0 given the inequality in (4.1). Now, since amin > amin−1,our assumption gives amin−1 < bmin. But this contradicts the definition of min.Our next lemma deals with entries greater than cs1 = amin in τ.Lemma 4.1.7. ct > cs1 ⇐⇒ dt ≥ bmin+1.Proof. Since cs1 = amin, we know that bmin+1 > cs1 . Thus, bmin+1 > cj for all 1 ≤ j ≤ nsatisfying cj ≤ cs1 . Thus any entry in the i + 1-th column of T that is ≥ bmin+1 can notbe the neighbour of any entry that is ≤ cs1 in the i-th column of τ. Consider the followingsets.X = {cj : cj > cs1}Y = {bj : bj ≥ bmin+1}60The fact that X and Y are sets, and not multisets, follows from the fact that bmin+1 >cs1 = amin > 0. Now, we know from our argument at the beginning of this proof that anelement of Y can only neighbour an element of X in τ. But |X| = |Y |, as X is the same as{aj : aj > amin}. Hence each element of Y is the neighbour to a unique element of X, andeach element of X has a neighbour that is an element of Y . Hence the claim follows.We note down an important consequence of the above lemma in the following remark.Remark 4.1.8. Consider the i-th and i+ 1-th columns of T again.a1 b1......amin bminamin+1 bmin+1......an bnThe boxes in the i-th column that contain entries ≤ amin and the boxes in the i+1-th columnthat contain entries ≤ bmin are shaded. All other boxes, that is, the boxes in the i-th columnthat contain entries > amin and the boxes in the i+ 1-th column that contain entries > bminare unshaded. Notice that the sets X and Y defined in the proof of Lemma 4.1.7 correspondto the unshaded entries in the i-th column and i + 1-th column respectively. Then, Lemma4.1.7 implies that in τ, the values belonging to the shaded boxes in T get neighbours fromthe shaded boxes only, while the values that belong to the unshaded boxes in T get neighboursfrom the unshaded boxes only.Recall now that s1 is the positive integer such that cs1 = amin. Define recursively integerssj satisfying 1 ≤ sj ≤ n for j ≥ 2 using the following criteria:I. sj > sj−1,61II. csj is the greatest positive integer that satisfiescsj−1 > csj ≥ dsj−1 .Clearly, only finitely many sj exist. Let the maximum be given by sk and letS = {s1, . . . , sk}.With this setup, we have the following lemma.Lemma 4.1.9. If t > sj for some 1 ≤ j ≤ k such that ct > csj , then ct > cs1.Proof. If j = 1, the claim is clearly true. Hence assume j ≥ 2. Shown below is theconfiguration in τ that we will focus on.csj−1 dsj−1......csj dsj...ctFirstly, note that since cs1 > cs2 > · · · > csk , we can not have t being equal to any si forsome 1 ≤ i ≤ k. For if t = si for some i, then we know that ct < csj for all sj < t. Thiscontradicts our assumption on t.We will now show that the hypothesis implies ct > csj−1 , as this suffices to establish theclaim. We know thatcsj−1 > csj ≥ dsj−1 . (4.2)We also know, by the definition of sj, that sj > sj−1 is such that csj is the greatest positiveinteger satisfying the inequalities in (4.2). Since t > sj, we know that ct does not satisfycsj−1 > ct ≥ dsj−1 . (4.3)62But clearly ct satisfies ct > dsj−1 , by using the hypothesis that ct > csj and (4.2). Thus,we must have that ct ≥ csj−1 , if ct is not to satisfy (4.3). Now, since csj−1 is positive bydefinition, we get that so is ct. Thus, in fact, ct > csj−1 .Lemma 4.1.10. Let t be a positive integer such that sj < t 6= sj+1 for some 1 ≤ j ≤ k − 1.Then exactly one of the following holds.1. ct > cs1 .2. ct < csj+1 .Proof. Notice that if ct > csj , then Lemma 4.1.9 implies that ct > cs1 , which is precisely thefirst condition in the claim.Now, assume that csj > ct > csj+1 . The definition of sj+1 implies that csj > csj+1 ≥ dsj .Thus we get thatcsj > ct ≥ dsj . (4.4)But since ct > csj+1 and t > sj, (4.4) and the recursive definition of the elements of S wouldimply that sj+1 equals t. This is clearly not the case. Therefore ct ≤ csj+1 . Again using thefact that csj+1 is positive, we get that ct < csj+1 .This brings us to the following important lemma which states that csk occupies therightmost box in the bottommost row of size i in α, where recall that α is the shape ofτ . Here we are identifying α with its reverse composition diagram. Establishing that cskoccupies the rightmost box in a row of size i is the same as proving that dsk = 0. That itbelongs to the bottommost row of length i requires us to prove that an entry ct that liesstrictly south of csk is either 0 or is such that its neighbour dt > 0.Lemma 4.1.11. 1. dsk = 0.2. If t > sk and ct > 0, then ct > cs1 and dt > 0.Proof. Consider first the i-th and i+1-th columns of T. For any positive integer r satisfying1 ≤ r ≤ min, consider the following multisets.Xr = {aj : amin ≥ aj ≥ br}Yr = {bj : bmin ≥ bj ≥ br}63Notice that Xr and Yr can be multisets only when br = 0. Notice further that if br = 0, thenthe cardinalities of the multisets Xr and Yr are equal. For a generic r, the following diagramdescribes the elements of Xr (boxes shaded darker in the i-th column) and Yr (boxes shadedlighter in the i+ 1-th column).a1 b1......aj bj......ar br......amin bminamin+1 bmin+1......an bnAssume, contrary to what is to be proved, that dsk > 0. Then, we know that there existsa unique positive integer r such that 1 ≤ r ≤ n and dsk = br, and hence br > 0. Note alsothat csk ≤ cs1 < bmin+1. This follows since cs1 = amin and amin < bmin+1.Now, since csk ≥ dsk , we have thatbr = dsk < bmin+1.Using the above, combined with the fact fact that b1 is always 0, we get that 1 < r ≤ min.Thus, we can consider the multisets Xr and Yr. In fact, they are sets consisting of positiveintegers as br > 0. We have, by the definition of Yr, thatdsk = br ∈ Yr.64Furthermore, sinceamin = cs1 ≥ csk ≥ dsk = br,we have csk ∈ Xr. Notice now the important fact that the elements of Yr can only beneighbours of elements in Xr, when we consider their respective positions in the i-th andi + 1-th columns of τ. This follows from Lemma 4.1.7, in a manner similar to the remarkfollowing it.We know that ar−1 ≥ br = dsk as r ≤ min. Hence, we obtain the following inequality.|Xr| ≥ |Yr|+ 1This in turn implies|Xr \ {csk}| ≥ |Yr \ {dsk}|+ 1. (4.5)Now consider the i-th and i + 1-th columns of τ. Each element of Yr neighbours someelement of Xr. Hence each element of Yr \ {dsk} neighbours a unique element of Xr \ {csk}.Now, (4.5) implies that there is at least one element of Xr \ {csk} whose neighbour does notbelong to Yr \ {dsk}. This neighbour has to be strictly smaller than dsk clearly, as dsk = bris the smallest entry in Yr. The strictness follows from dsk > 0.If, in τ, all elements of the set Xr \ {csk} lie strictly north of the box occupied by csk ,then the argument earlier implies that for some cj ∈ Xr \ {csk}, we have dj < dsk . But thiscorresponds to a triple rule violation because of the existence of the configuration shownbelow.cj dj...dsksatisfying cj ≥ dsk > dj ≥ 0Hence, there is at least one element cj ∈ Xr \ {csk} that lies strictly south of the boxoccupied by csk . Any such element has to be greater than csk . If not then it would satisfythe inequality csk > cj ≥ dsk . But this would allows us to define sk+1, which we know doesnot exist. Hence cj > csk . But then Lemma 4.1.9 implies that cj > cs1 . As cs1 = amin, thiscontradicts the fact that cj ∈ Xr \ {csk}. Hence, we conclude that dsk = 0. This establishesthe first part of the claim.65As for the second part, note for any positive integer j > sk such that cj > 0, we musthave cj > csk (again by the fact that sk+1 does not exist). Lemma 4.1.9 implies that cj > cs1 ,while Lemma 4.1.7 implies that dj ≥ bmin+1 > 0. This establishes the second part of theclaim.Remark 4.1.12. The lemma above implies that position of csk in τ only depends on theshape of τ , and not the filling itself.We would like to be able to construct the integers sj in reverse, since locating csk is easierthan locating cs1 in τ. Thus, we would like an algorithm that takes as input the integer sk(and τ) and terminates by giving s1 as output. Such an algorithm would give us a way ofcomputing fi+1(T ) = amin = cs1 given τ . Before we achieve this aim, we need some notation.Let q1 be the greatest positive integer such that dq1 = 0 and cq1 > 0. Define a sequenceof positive integers qj satisfying 1 ≤ qj ≤ n for j ≥ 2 recursively according to the followingconditions.1. qj < qj−1,2. qj is the greatest positive integer such thatcqj > cqj−1 ≥ dqj .By virtue of Lemma 4.1.11, we have that q1 = sk. In fact, qj = sk+1−j for 1 ≤ j ≤ k as thenext lemma shows.Lemma 4.1.13. For 1 ≤ j ≤ k, we have qj = sk+1−j.Proof. Suppose that for some 1 ≤ j ≤ k − 1, we know that qj = sk+1−j. We will show thatqj+1 = sk−j. By the definition of qj+1, we havecqj+1 > cqj ≥ dqj+1 . (4.6)Furthermore, since qj = sk+1−j, we havecsk−j > cqj ≥ dsk−j . (4.7)The recursive definition of qj+1 combined with (4.6) and (4.7) implies qj+1 ≥ sk−j. Suppose,contrary to what we seek to prove, that qj+1 > sk−j. Thus, we have that qj > qj+1 > sk−j.66Diagrammatically, this corresponds to the following configuration in τ.csk−j dsk−j......cqj+1 dqj+1...cqjFrom (4.6) and (4.7), we have cqj+1 > dsk−j . Since qj = sk+1−j, we must have cqj+1 > csk−j .To see this, notice that had cqj+1 < csk−j been true, the recursive definition of sk+1−j givensk−j would have implied that sk+1−j ≤ qj+1, which is clearly not the case. Thus, we get thatcqj+1 > csk−j .But then, Lemma 4.1.9 implies cqj+1 > cs1 . By Lemma 4.1.7, this implies thatdqj+1 ≥ bmin+1. (4.8)Since cs1 ≥ csk+1−j = cqj , we know that cqj < bmin+1, as cs1 = amin < bmin+1. But thenthe inequality in (4.8) is in contradiction to the inequality in (4.6). Hence qj+1 = sk−j. Sinceq1 = sk, the claim follows by induction.Thus, now we know that qk = s1. The next lemma will show that qk+1 does not exist.Lemma 4.1.14. There does not exist a positive integer t such that t < s1 andct > cs1 ≥ dt.Proof. Suppose such a t exists. By Lemma 4.1.7, we have dt ≥ bmin+1. But we also knowthat bmin+1 > amin = cs1 . Thus, the inequality in the statement of the lemma can not besatisfied.We now know how to compute cs1 given τ. Our next aim is to remove cs1 from thei-th column of τ and then rearrange entries therein so as to obtain (ρ−1(tjdti+1(T ))). Theshort algorithm that accomplishes this is presented below.Algorithm 4.1.15. 1. For j = k, k − 1, . . . 2 in that order, place cqj−1 in the box thatoriginally contained cqj .672. Place a 0 in the box that originally contained cq1. Call the resulting tableau β(τ).3. If there is a row in β(τ) comprising entirely of 0s, we remove that row. The resultingrectangular filling is (ρ−1(tjdti+1(T ))). If we omit 0s altogether, we obtain what wewill call φi+1(τ).We will demonstrate the above algorithm with an example. The proof of validity of thealgorithm will be presented subsequently.Example 4.1.16. Suppose thatT =7 3 0 0 08 5 0 0 09 6 2 1 0.Say we want to compute tjdt3(T ). It is clear that if we start a backward jeu de taquin slidefrom the addable node in the third column, then 6 is the first entry that moves horizontally.Thus tjdt3(T ) would be obtained by removing 6 from the second column. Then, we have(tjdt3(T )) =7 0 0 0 08 3 0 0 09 5 2 1 0.Now we try and repeat the above with the SSRCT τ = ρ−1(T ) using Algorithm 4.1.15. Wehaveτ =7 6 2 1 08 5 0 0 09 3 0 0 0.Then we have q1 = 3 as c3 is the lowermost non-zero entry in the second column that has aneighbour equalling 0. Since c2 > c3 ≥ d2 we have q2 = 2. Similarly, we have q3 = 1. Thus,β(τ) =7 5 2 1 08 3 0 0 09 0 0 0 0.As there is no row comprising entirely of 0s, by the third step in the algorithm, we have that(ρ−1(tjdt3(T ))) is the tableau above. We can remove the 0s to get a better picture. Then68Algorithm 4.1.15 implies thatφ3(τ) =7 5 2 18 39.We also havetjdt3(T ) =78 39 5 2 1.It is easily checked that φ3(τ) = ρ−1(tjdt3(T )).Now we will proceed to prove the validity of Algorithm 4.1.15 by showing that φi+1(τ) isan SSRCT. Since φi+1(τ) is obtained from β(τ) by removing extraneous 0s, we will workwith β(τ) as it is more convenient. We need to show that β(τ) satisfies the conditionsbelow.• Excepting 0s, the first column of β(τ) is strictly decreasing from bottom to top.• It has no triple rule violations.• The rows are weakly decreasing from left to right.The third condition above is verified by an easy argument: Note that if the position of anentry in the i-th column remains unchanged, then the condition is automatically verified.Otherwise the entry csj is replaced by csj+1 for some 1 ≤ j ≤ k − 1. Since csj+1 ≥ dsj andcsj > csj+1 , we see that the algorithm does not change the fact that the rows were weaklydecreasing from left to right. Finally, notice that csk is replaced by a 0, but since dsk wasalready 0 by Lemma 4.1.11, we still have rows weakly decreasing from left to right.Now we will verify that the first condition holds as well. Notice that if i ≥ 2, thenno changes are ever made to the first column by Algorithm 4.1.15. Hence, in this scenarioφi+1(τ) has the entries in the first column strictly decreasing from bottom to top. Considernow the case i = 1. Then, it is easily seen that Algorithm 4.1.15 replaces the bottom mostnon-zero entry (in the first column) whose neighbour is a 0 with a 0, and no other changeis made. Hence, if one omits the 0s, the first column of β(τ) is strictly decreasing frombottom to top.Thus, we only need to prove that there are no triple rule violations in β(τ). We will dothis in cases.69Lemma 4.1.17. In β(τ), consider any configuration of the type shown belowx y...z,where y and z belong to the i+ 1-th column. If z > 0 and z > y, then z > x.Proof. Notice that Algorithm 4.1.15 does not alter the position of any entry in the i+ 1-thcolumn. Let x′ be the entry in τ in the box currently occupied by x in β(τ). Since thereare no triple rule violations in τ, we know thatz > 0 and z > y =⇒ z > x′ (4.9)We have two possibilities to deal with. Firstly, if x = x′, then the claim follows easily from(4.9). Now, assume x 6= x′. Algorithm 4.1.15 implies that x < x′. Again, (4.9) implies theclaim.Lemma 4.1.18. In β(τ), consider any configuration of the type shown belowx y...z,where y and z belong to the i-th column. If z > 0 and z > y, then z > x.Proof. Firstly, notice that we only need to worry about this configuration when i ≥ 2.Let x′, y′ and z′ be the entries in τ in the boxes corresponding to those occupied by x, yand z in β(τ) respectively. Since Algorithm 4.1.15 does not change the i− 1-th column, wehave x = x′. This along with the fact that there are no triple rule violations in τ impliesz′ > 0 and z′ > y′ =⇒ z′ > x.If y = y′ and z = z′, then we have nothing to prove.Now assume that z = z′ but y 6= y′. Then we have two cases. In the first case, we havey′ = csk and thus, y = 0. Furthermore, since z occupies a box below csk , we know thatz > cs1 , by Lemma 4.1.11. Now the claim follows readily for this case. In the second case,we have y′ = csj and thus, y = csj+1 for some 1 ≤ j ≤ k − 1. The possible relative positions70of y, y′ and z in τ are shown below.y′...y...zy′...z...yAccording to Lemma 4.1.10, we have either z > cs1 (and hence z > y, y′) or z < y (andhence z < y′). In any case, we see that if z > 0 and z > y, then z > x.Now assume that y 6= y′ and z 6= z′. Then we must have y = csi1 and z = csi2 where2 ≤ i1 < i2 ≤ k. But then the situation where z > y does not arise.Thus, we have established that φi+1(τ) is an SSRCT indeed. We will prove anotherlemma that is of similar flavour to the previous two lemmas, and which we will soon use.Lemma 4.1.19. In β(τ), consider a configuration of the typex y where x is in i-th column and y in i+ 1-th column.If cs1 > y ≥ 0 then cs1 > x.Proof. For any configuration of the type in the statement of the claim, we first show thatcs1 can neither equal x nor y.Recall that cs1 = amin is the first entry that moves horizontally when computing jdti+1(T ).This entry is removed from the i-th column of τ when β(τ) is computed. Hence it can notequal x. Lemma 4.1.6 implies it can not equal y either.If cs1 > y ≥ 0, then we know that y ≤ bmin. But then Lemma 4.1.7 yields that x < cs1 ,which is what we wanted.We are now in a position to state our first important theorem.Theorem 4.1.20. The following diagram commutes.SSRTstjdti+1ρ−1// SSRCTsφi+1SSRTsρ−1// SSRCTs71Proof. We have already established that φi+1(τ) is an SSRCT. This observation and the factthat we have removed the same entry from the i-th column in both T and τ while ensuringthat none of the other entries have changed columns, establishes the claim.We define another SSRCT using the procedure φi as follows.Φi(τ) ={φ2 ◦ φ3 ◦ · · · ◦ φi(τ) i > 1τ i = 1Let γ = sh(Φi(τ)) = (γ1, . . . , γs). Let γ′ = (γ, i) be the composition obtained by appendinga part of length i to γ. Consider the filling of shape γ′/ (1) where the first s rows are filledas Φi(τ). Fill the last row with the entries of Hi(T ) in decreasing order from left to right.Call the resulting filling µi(τ).Theorem 4.1.21. With the notation as above, the following diagram commutes.SSRTsjdtiρ−1// SSRCTsµiSSRTsρ−1(1)// SSRCTsProof. First, we start by showing that µi(τ) is indeed an SSRCT. Notice that the entries inevery column are all distinct, using Lemma 4.1.6. Next, since the rows are weakly decreasingby construction, and the top s rows already form an SSRCT, we just need to check thatthere is no configuration of the formx y...zsatisfying x ≥ z > y and z is in the bottommost row.But this follows from Lemma 4.1.19. Hence µi(τ) is an SSRCT. Now the claim follows asthe set of entries in each column of jdti(T ) and µi(τ) is the same.Given the theorem above, we are justified in saying that µ is an analogue of the backwardjeu de taquin slide. From this point on, by a backward jeu de taquin slide on SSRCTs ofstraight shape we will mean an application of µ.724.1.1 Skew shape after µIf we perform backward jeu de taquin slides on SSRTs of straight shape, it is easy to predictthe resulting shape once the slide is completed. In the case of SSRCTs, when we apply theprocedure µ, it is not immediate what the resulting shape is. The aim of this subsection isto use the operators on compositions defined in Subsections 2.5.2 and 2.5.3 to predict it.Lemma 4.1.22. The shape of φi+1(τ) is di(α) if i ≥ 1.Proof. It is clear from Algorithm 4.1.15 that box that contained csk in τ contains 0 inφi+1(τ). We also know from Lemma 4.1.11 that all parts of α that are below αsk in thereverse composition diagram corresponding to α have either length strictly less than αsk orstrictly greater than αsk . Furthermore, the same lemma also implies that αsk has length i.Thus, the claim follows.As an immediate corollary, we obtain the following.Corollary 4.1.23. The shape of Φi+1(τ) is v[i](α) if i ≥ 0.Proof. Φ1 fixes the SSRCT τ . In this case the claim is clear. If we are computing Φi+1(τ)for i ≥ 1, we are computing φ2 ◦ · · · ◦ φi+1(τ). Using Lemma 4.1.22 repeatedly, we get thatΦi+1(τ) has shape d1 · · · di(α) = v[i](α).Theorem 4.1.24. The SSRCT µi(τ) is of shape γ/ (1) where γ = ui(α).Proof. This follows from the description of the procedure µi and Corollary 4.1.23.4.2 Backward jeu de taquin slides for SSRCTs ofskew shapeAfter giving a description for the backward jeu de taquin slide for SSRCTs of straight shape,it is only natural to ask for a generalization, that is, a backward jeu de taquin slide forSSRCTs of other shapes. For the proofs in this section, we will consider SSRCTs whoseentries are drawn from the ordered alphabet X = A ∪ A¯ whereA = {1 < 2 < 3 < · · · }A¯ = {1¯ < 2¯ < 3¯ < · · · }.We will further assume that 1¯ is greater than any letter in A. Thus, we have a total orderon X.73Consider a skew reverse composition shape α/β. Let τo be an SSRCT of shape α/βconstructed using the alphabet A, and let τ¯ be an SSRCT of straight shape β constructedusing the alphabet A¯. Then we will denote by τ the SSRCT of straight shape α formed byfilling the inner shape in τo according to τ¯ .Let i ≥ 1. Assume, for the moment, that we are computing φi+1(τ). We will showthat the shape of the SSRCT obtained by considering entries that belong to A in φi+1(τ) isindependent of the filling τ¯ . The example next will clarify what we are aspiring to.Example 4.2.1. Consider the two tableaux below.τo =3• • 2 1• • • 5• 4and τ¯ =3¯ 1¯5¯ 4¯ 2¯6¯Thusτ =33¯ 1¯ 2 15¯ 4¯ 2¯ 56¯ 4.Then φ3(τ) is the SSRCT below.33¯ 4 2 15¯ 4¯ 2¯ 56¯If we replace the entries in the above tableau that belong to A¯ by bullets, then we obtain thefollowing SSRCT.3• 4 2 1• • • 5•We would like to demonstrate that the above tableau is obtained independent of our choiceof the filling τ¯ .74We will use the same notation as the one we established when we described the processφi+1. Thus, our focus is on the i-th and i+ 1-th columns of T and τ respectively, as shownbelow. Recall that ρ(τ) = T .a1 b1a2 b2......an bnc1 d1c2 d2......cn dnThe only difference from the earlier situation is that the entries are now allowed to beelements of A¯. We will recall the notation here for the sake of convenience. We havethat amin is the first entry that moves horizontally when a backward jeu de taquin slide isinitiated from the i + 1-th column in T . Hence min is the smallest positive integer suchthat amin < bmin+1. Also we assume that, in τ, the entry corresponding to amin is cs1 , thatis, s1 is the positive integer such that cs1 = amin. Finally, we define recursively integers sjsatisfying 1 ≤ sj ≤ n for j ≥ 2 using the following criteria.1. sj > sj−1,2. csj is the greatest positive integer that satisfiescsj−1 > csj ≥ dsj−1 . (4.10)Clearly, only finitely many sj exist. Let the maximum be given by sk and letS = {s1, . . . , sk}. (4.11)Lemma 4.2.2. Assume cs1 ∈ A¯. Let 1 ≤ j ≤ k be the greatest positive integer such thatcsj belongs to A¯. If t > sj is a positive integer such that ct > 0, then one of the followingstatements holds.1. ct ∈ A.2. ct ∈ A¯ and dt ∈ A¯.Proof. Firstly, note that cs1 ∈ A¯ implies that bmin+1 ∈ A¯. Notice also that if csj ∈ A¯, thenfor all 1 ≤ r ≤ j, we must have that csr ∈ A¯ as cs1 > · · · > csj > · · · > csk .75If ct ∈ A, then the first condition is already satisfied. Hence assume that ct ∈ A¯. If j = k,then Lemma 4.1.11 implies that ct > cs1 . Then, Lemma 4.1.7 implies dt ≥ bmin+1. Hencedt ∈ A¯.Now assume that j < k. We have that csj ∈ A¯ and csj+1 ∈ A. Since the definition of sj+1implies thatcsj > csj+1 ≥ dsj ,we get that dsj ∈ A.By our assumptions, we know that t > sj and ct ∈ A¯. Using this and the fact that j isthe largest integer such that csj ∈ A¯, we conclude that t 6= sj+1. But then, we must havethat ct > csj . To see this, note that if ct < csj , then we have the following inequality usingthe fact that dsj ∈ A.csj > ct > dsjBut then, we get that csj+1 > ct and hence, must belong to A¯, which is not the case. Hencect > csj indeed.Lemma 4.1.10 implies the inequality ct > cs1 and then Lemma 4.1.7 implies that dt ≥bmin+1. Thus, we get that dt ∈ A¯.Note that the above lemma assumes nothing about the filling τ¯ .Lemma 4.2.3. Assume cs1 ∈ A¯. Consider the SSRCT of straight shape inside φi+1(τ)formed by the entries that belong to A¯. The shape of this SSRCT is di(β).Proof. Let 1 ≤ j ≤ k be the greatest positive integer such that csj ∈ A¯. Then from Lemma4.2.2, it follows that csj occupies the rightmost box in the bottommost row of length i in thereverse composition diagram of β. According to Algorithm 4.1.15, this entry gets replacedeither by an element of A or 0. In either case, the shape of the SSRCT formed by the entriesthat belong to A¯ is di(β).Lemma 4.2.4. Assume that cs1 ∈ A. Then the SSRCT in φi+1(τ) formed by consideringthe entries that belong to A is independent of the choice of τ¯ . Furthermore, this SSRCT hasshape di(α)/ β.Proof. Since cs1 belongs to A and cs1 > csj for all 2 ≤ j ≤ k, we get that csj ∈ A for2 ≤ j ≤ k. Note by Lemma 4.1.11 that csk occupies the rightmost box in the bottommost76part of length i in the reverse composition diagram of α. Now Algorithm 4.1.15 immediatelyimplies the claim.Lemma 4.2.5. Assume that cs1 ∈ A¯. Then the SSRCT in φi+1(τ) formed by consideringthe entries that belong to A is independent of the choice of τ¯ . Furthermore, this SSRCT hasshape di(α)/ di(β).Proof. Let j be the greatest positive integer satisfying 1 ≤ j ≤ k such that csj ∈ A¯. ByLemma 4.2.3, we know that csj occupies the rightmost box in the bottommost row of lengthi in the reverse composition diagram of β. Also, by Lemma 4.1.11 we know that csk occupiesthe rightmost box in the bottommost row of length i in the reverse composition diagram ofα (recall also that we draw the reverse composition diagram of β in the bottom left corner ofthe reverse composition diagram of α when depicting α/β). Observe now that sj does notdepend on τ¯ . Thus, from Algorithm 4.1.15, it follows that the SSRCT in φi+1(τ) formed bythe entries that belong to A is independent of τ¯ and that it has shape di(α)/ di(β).Now we define µi(τo) as follows.µi(τo) = the SSRCT formed by considering the entries that belong to A in µi(τ).It is not clear from the above definition that µi(τo) does not depend on the choice of τ¯ . Weestablish this next.Let To = ρβ(τo) and T¯ = ρ(τ¯). Define T to be ρ(τ). Consider a backward jeu de taquinslide on T starting from an addable node in column i. Let j be the greatest integer satisfying1 ≤ j ≤ i− 1 such that entry that moves horizontally from column j to column j + 1 whencomputing jdti(T ) is an element of A¯. If there is no such j, define j to be 0. If j ≥ 1, thenthe entries moving horizontally when computing jdti(T ) from all columns between 1 and j(inclusive) are all elements of A¯, because the entries moving horizontally during a backwardjeu de taquin slide increase weakly as we move from column i−1 to column 1. Now by usingTheorem 4.1.20, we get that if we compute φ2 ◦ · · · ◦ φi(τ), all the entries that exit fromcolumns between 1 and j belong to A¯.The preceding discussion along with Lemmas 4.2.4 and 4.2.5 implies the following propo-sition.Proposition 4.2.6. Let γ be the SSRCT Φi(τ) where i ≥ 1. Then the SSRCT formedby considering the entries in γ that belong to A¯ has shape v[j](β). The SSRCT formed byconsidering the entries in γ that belong to A has shape v[i−1](α)/ v[j](β). Furthermore, thisSSRCT is independent of the choice of τ¯ .77This proposition along with our description of the procedure µ prior to Theorem 4.1.21,implies the following theorem, which proves that µi(τo) is well-defined and does not dependon the choice of filling τ¯ .Theorem 4.2.7. Let γ be the SSRCT µi(τ) where i ≥ 1. Then the SSRCT formed byconsidering the entries in γ that belong to A¯ has shape uj+1(β)/ (1). The SSRCT formed byconsidering the entries in γ that belong to A has shape ui(α)/ uj+1(β), and is independent ofthe choice of τ¯ .From this point on, we will not require the alphabet A¯.4.3 A new poset on compositionsIn this section we will introduce a new poset structure on the set of compositions that arisesfrom performing backward jeu de taquin slides on SSRCTs. But before that we need tounderstand the link between maximal chains in Young’s lattice Y and SRTs.4.3.1 Growth words and SRTsWith any maximal chain in Y starting at the empty partition, we can associate a sequenceof positive integers as explained next. Letλ0 = ∅ ≺ λ1 ≺ · · · ≺ λnbe a maximal chain. Then each partition λk for 1 ≤ k ≤ n is obtained by adding a box at anaddable node of λk−1, say, in column ik. The sequence in · · · i1 is called the column growthword corresponding to this maximal chain. Note that the column growth word is alwaysreverse lattice, that is, in any suffix of the column growth word the number of js weaklyexceeds the number of j + 1s for all positive integers j. What we have outlined is clearlya bijection between reverse lattice words of length n and maximal chains in Y starting at∅ and ending at a partition of n. We will now associate an SRT of size n given a columngrowth word w = in · · · i1. This is done by considering the corresponding maximal chain andassigning n− k + 1 to the box in λk that is not in λk−1. This SRT will be denoted by Tw.Before we state our next lemma connecting the column reading word of Tw to its associ-ated reverse lattice word, we require the notion of standardization. Given a word w = in · · · i178where the ijs are positive integers, define the inversion set as follows.Inv(w) = {(p, q) : ip < iq}There exists a unique permutation in σ ∈ Sn such that Inv(σ) = Inv(w). We call σ thestandardization of w, and denote it by std(w).Lemma 4.3.1. Let w = in · · · i1 be a reverse lattice word, and let σ = std(w). Then thecolumn reading word of Tw equals σ−1.Proof. Notice that all the instances of a positive integer j in w are in positions given by theentries in the j-th column of Tw read in increasing order. This implies the claim.Example 4.3.2. Consider the reverse lattice word w = 341123121. Then we have thatσ = std(w) = 791258364 in single line notation. Notice that Tw is the SSRT below.347 5 19 8 6 2The column reading word of Tw is the following permutation.347958162It can be checked that the permutation above is precisely σ−1.Now recall that if we perform our variant of the Robinson-Schensted algorithm on thecolumn reading word of a tableau T , we recover T as the insertion tableau. This impliesthe following corollary to the previous lemma, establishing Tw as an insertion tableau forpermutation associated naturally to it.Corollary 4.3.3. Let w = in · · · i1 be a reverse lattice word, and let σ = std(w). ThenTw = P (σ−1).This interepretation of Tw will be of importance to us in the next subsection.4.3.2 A poset on compositionsWe will now define a new poset on the set of compositions, denoted by Rc, using its coverrelation lr defined by setting α lr β if and only if β = ui(α) for some i ≥ 1. The order79relation <r in Rc is obtained by taking the transitive closure of the cover relation lr.Example 4.3.4. Let α = (3, 1, 4, 2, 1) and β = u4(α) = (2, 1, 4, 1, 4). Then αlr β in Rc.The next theorem is about counting maximal chains inRc, and the reader should compareit with the analogous result in the case of Young’s lattice Y [42, Proposition 7.10.3] and,more recently, in the case of Lc [4, Proposition 2.11].Theorem 4.3.5. The number of maximal chains from ∅ to a composition α in Rc is equalto the number of SRCTs of shape α.To prove the above theorem, we will use our variant of the Robinson-Schensted algorithmdefined in Subsection 2.2.3 and answer a more general question. We will start by proving aresult that allows us to compute the resulting inner shape after a sequence of backward jeude taquin slides has been applied to an SSRCT of straight shape.Let τ be an SSRCT of shape α. Consider the computation of µin · · ·µi1(τ), where weassume that the sequence of backward jeu de taquin slides we are executing is valid at allsteps. This means that for all 1 ≤ k ≤ n − 1, the outer shape β underlying the SSRCTµik · · ·µi1(τ) is such that β˜ has an addable node in column ik+1. Furthermore, we also assumethat α˜ has an addable node in column i1, so that we can compute µi1(τ) to start with.We will deviate a little from our earlier description of backward jeu de taquin slides foran SSRCT of straight shape. Let max(τ) denote the maximum entry in the SSRCT τ (ifτ = ∅ then this is 0). We will assume that in computing µi(τ), instead of getting an SSRCTof skew reverse composition shape, with the vacant lower left corner filled by a bullet •, weinsert the number max(τ) + 1 in the corner left vacant. In this way we ensure that µi(τ) isalso an SSRCT of straight shape. We will do backward jeu de taquin slides (the procedurejdt) on SSRTs of straight shape with a similar rule.Example 4.3.6. Consider the SRCT τ =5 28 7 4 19 6 31110of shape (2, 4, 3, 2). We will computeµ4µ3µ4(τ) under the set of rules outlined prior to the example. Firstly, max(τ) = 11. Weobtain the following SSRCTs sequentially (where the entries that come in the lower left cornerare highlighted).5 28 7 3 19 612 11 10 4−→5 28 6 3 112 11 10 413 9 7−→5 28 6 3 112 9 7 414 13 11 1080We will next state a theorem that allows us to compute the final SRCT (under our newsetup) obtained when a sequence of slides is applied to an empty SRCT ∅.Theorem 4.3.7. Let w = in · · · i1 be a reverse lattice word, and let σ = std(w). Thenµin · · ·µi1(∅) = ρ−1(Q(σ)).Proof. Let µin · · ·µi1(∅) = τ . Clearly, τ is an SRCT. Now consider the correspondingsequence of slides starting from the empty SRT, also denoted ∅, and suppose that the finalSRT obtained is T . Thus, jdtin · · · jdti1(∅) = T . From Theorem 4.1.21, it follows thatρ(τ) = T in this new setting.Observe that in obtaining T , we encounter a sequence of SRTs for 1 ≤ k ≤ n as follows.Tk = jdtik · · · jdti1(∅)If we let λk denote sh(Tk) ` k, we get a maximal chain in Y .∅ ≺ λ1 ≺ · · · ≺ λnThus, we have that w = in · · · i1 is the column growth word corresponding to the maximalchain above. This combined with the reversibility of jeu de taquin for SSRTs gives us thekey fact that Tw = e(T ) (essentially as evacuation undoes backward jeu de taquin slides).From Corollary 4.3.3 we know that Tw = P (σ−1), and by Lemma 2.2.13, we know thatP (σ−1) = e(Q(σ)). Combining the previous two facts, we obtain the following.e(T ) = e(Q(σ))Since evacuation is an involution as will shown in Section 4.5, we get that T = Q(σ). Thisimplies that the SRCT given by µin · · ·µi1(∅) = τ = ρ−1(T ), equals ρ−1(Q(σ)).We claim that the above theorem also supplies us with a bijection between the set ofmaximal chains from ∅ to α in Rc and the set of SRCTs of shape α.Proof. (of Theorem 4.3.5) Consider a maximal chain in Rc as shown below.∅lr α1 lr · · ·lr αn = α81Just as in the case of Y , the maximal chain above gives us a reverse lattice word w = in · · · i1where αk = uik(αk−1) for 1 ≤ k ≤ n. Associate the SRCT µin · · ·µi1(∅) with this maximalchain. Note that the shape of this SRCT, by Theorem 4.1.24, is uin · · · ui1(∅) where ∅denotes the empty composition. But this is clearly α. To establish that the map associatingthe SRCT µin · · ·µi1(∅) to the reverse lattice word in · · · i1 obtained from the maximal chainis indeed a bijection, we will use the invertibility of jeu de taquin slides for SSRTs.Consider an SRCT τ of shape α, and let T = ρ(τ). We will analyze the execution ofthe evacuation action on T . At every step a forward jeu de taquin slide is initiated fromthe lower left corner, and this slide finishes in an addable node to the shape underlying therectified tableau. Noting down the columns of these addable nodes gives us a sequence ofn positive integers in, in−1,. . . , i1. This sequence is uniquely determined by T (by theinvertibility of jeu de taquin slides on SSRTs) and the word w = in · · · i1 is reverse lattice.Now since backward jeu de taquin slides undo the forward jeu de taquin slides, we get thatT = jdtin · · · jdti1(∅),and hence thatτ = µin · · ·µi1(∅).Since τ had shape α to start with, we get that uin · · · ui1(∅) = α as well (here again ∅ refersto the empty composition). Now we can associate the following (unique) maximal chainfrom ∅ to α in Rc to τ .∅lr ui1(∅)lr ui2ui1(∅)lr · · ·lr uin · · · ui1(∅) = αThis finishes the proof.We will give an example illustrating the ideas above.Example 4.3.8. To compute τ = µ3µ4µ1µ1µ2µ3µ1µ2µ1(∅), note that the column growthword is 341123121 and its standardization (which is a permutation in S9) in single linenotation is σ = 791258364. On applying the Robinson-Schensted variant, σ maps to the82following insertion tableau (left) and recording tableau (right).P (σ) =127 5 39 8 6 4Q(σ) =458 6 29 7 3 1Then, by Theorem 4.3.7, we have that τ = ρ−1(Q(σ)).τ =458 7 3 19 6 2It is straightforward to check that jdt3jdt4jdt1jdt1jdt2jdt3jdt1jdt2jdt1(∅) gives the followingsequence of SRTs (the bullets indicating where the next slide begins).1 • →•2 1→23 1 •→2 •4 3 1→•4 25 3 1→•45 26 3 1→→456 27 3 1 •→456 2 •8 7 3 1→458 6 29 7 3 1Note that the final SRT obtained above is ρ(τ).In the next subsection, we will use Theorem 4.3.7 and the proof strategy for Theorem4.3.5 to consider the effect of a sequence of slides starting from a nonempty SRCT.4.3.3 Inner shape after a sequence of slidesLet τ1 be an SRCT of shape α n, and let T1 = ρ(τ1) be of shape λ ` n. Considering theexecution of the evacuation action on T1 as in the proof of Theorem 4.3.5, we get a sequenceof n positive integers in, in−1,. . . , i1. This sequence is uniquely determined by T1 and theword w = in · · · i1 is reverse lattice.Remark 4.3.9. Note that if we started with the final SRT in Example 4.3.8, and performedthe procedure discussed prior to this remark, we will be obtain the same sequence of SRTs inreverse and the columns to which the bullets belong are precisely the integers in down to i1.83It follows that T1 = jdtin · · · jdti1(∅) which in turn implies that τ1 = µin · · ·µi1(∅).Consider now the SRCT τ2 defined below.τ2 = µkm · · ·µk1(τ1)Let ρ(τ2) be T2. Clearly, we have that T2 = jdtkm · · · jdtk1(T1). Denote by u the wordkm · · · k1.Let v = u · w, where · denotes concatenation of words, and let pi = std(v), σ = std(w)and ω = std(u). Now, note that Theorem 4.3.7 implies thatτ2 = ρ−1(Q(pi)).Observe additionally that the integers m+n, m+n− 1, . . ., n+ 1 are the new entries addedwhen computing µkm · · ·µk1(τ1), and they form an SSRCT of size m (with all entries distinct)inside τ2. But this SSRCT is obtained by performing our insertion algorithm on the prefixof length m in pi, and then applying ρ−1 to the partial Q-tableau obtained at this stage. Ifone subtracts n from all entries in this partial Q-tableau, one gets an SRT that is preciselythe Q-tableau obtained after performing the insertion process on ω = std(u).From this point on, we switch perspectives again, and on performing backward jeu detaquin slides on SSRCTs, instead of filling the vacant box in the lower left corner withlarger entries, we will fill them with bullets. The preceding discussion implies the followingtheorem.Theorem 4.3.10. Let τ1 be an SRCT of straight shape α, and τ2 be the SRCT µjm · · ·µj1(τ1).Let w = jm · · · j1 and ω = std(w) ∈ Sm. Let β = ujm · · · uj1(α) and γ = sh(ρ−1(Q(ω))).Then τ2 is an SRCT of shape β/ γ.The following corollary is obtained from the theorem above.Corollary 4.3.11. Let τ1 be an SRCT of straight shape α, and τ2 be the SRCT µjm · · ·µj1(τ1).Let w = jm · · · j1 and ω = std(w) ∈ Sm. Let β = ujm · · · uj1(α). Then τ2 is an SRCT ofshape β/ (n) if and only if jm > · · · > j1, and it is an SRCT of shape β/ (1n) if and only ifjm ≤ · · · ≤ j1.SRT versions of the two results above also exist and they are also implied in the discussionearlier. We will recast the corollary above for SRTs as another corollary.84Corollary 4.3.12. Let T1 be an SRT of straight shape λ, and T2 be the SRT jdtjm · · · jdtj1(T1).Let w = jm · · · j1 and ω = std(w) ∈ Sm. Let β = ujm · · · uj1(α) and δ = β˜. Then T2 is anSRT of shape δ/(n) if and only if jm > · · · > j1, and it is an SRT of shape δ/(1n) if andonly if jm ≤ · · · ≤ j1.Suppose now that T is an SRT of shape δ/(n). Then the invertibility of the jeu de taquinslides for SRTs along with the corollary above implies that T has been obtained from anSRT T ′ by doing a sequence of backward jeu de taquin slides as followsT = jdtin · · · jdti1(T′),where in > · · · > i1. Similarly, if T is an SRT of shape δ/(1n), then it has been obtainedfrom an SRT T ′ by doing a sequence of backward jeu de taquin slides as followsT = jdtin · · · jdti1(T′),where in ≤ · · · ≤ i1. Note now that the maps ρ(n) : SSRT(−/(n)) → SSRCT(−/ (n)), andρ(1n) : SSRT(−/(1n)) → SSRCT(−/ (1n)) are bijections. Using this and Theorem 4.1.21, itis clear that we can apply the above arguments to SRCTs. This insight is all we need toprove our right Pieri rules for the noncommutative Schur functions stated in Theorem 2.6.9.4.4 Right Pieri rules for noncommutative SchurfunctionsTo recover Pieri rules from Theorem 2.4.6 that allow us to compute the products sα · s(n)(and sα ·s(1n)) we need to find all SRCTs of shape γ/ (n) (respectively γ/ (1n)) that rectify tothe canonical tableau of shape α. In light of Corollary 4.3.11 we have the following lemma.Lemma 4.4.1. Let τ = µin · · ·µi1(τα), where in > · · · > i1. Then τ rectifies to τα.Proof. Let Tα = ρ(τα) and T = ρ(n)(τ). Then, by Theorem 4.1.21, we have that T =jdtin · · · jdti1(Tα), which in turn implies that rect(T ) = rect(Tα) (as discussed before Algo-rithm 2.2.11). Therefore, we get that τ rectifies to τα.Remark 4.4.2. The arguments after Corollary 4.3.12 imply that if there is an SRCT ofshape γ/ (n) that rectifies to τα, then it has to be obtained from τα by doing a sequence ofbackward jeu de taquin slides from columns i1, i2, · · · , in in that order, where in > · · · > i1.85Similarly, if there is an SRCT of shape γ/ (1n) that rectifies to τα, then it has to beobtained from τα by doing a sequence of backward jeu de taquin slides from columns i1,i2, · · · , in in that order, where in ≤ · · · ≤ i1.We can now prove the right Pieri rules, stated in Theorem 2.6.9.Theorem 4.4.3. (Right Pieri rules) Let α be a composition and n a positive integer. Thensα · s(n) =∑β|α|+n,uin ···ui1 (α)=βin>···>i1sβ,sα · s(1n) =∑β|α|+n,uin ···ui1 (α)=βin≤···≤i1sβ.Proof. We will only give the proof for sα · s(n) as the proof of sα · s(1n) is similar. Notice firstthat if we have two distinct sequences in > · · · > i1 and jn > · · · > j1 such thatτ1 = µin · · ·µi1(τα),τ2 = µjn · · ·µj1(τα),then τ1 and τ2 are distinct SRCTs. This follows from the reversibility of backward jeu detaquin slides for SRTs, once we consider the images of τ1 and τ2 under the generalized ρ mapof Subsection 2.1.4. By Corollary 4.3.11, we get thatsh(τ1) = γ1/ (n) where γ1 = uin · · · ui1(α),sh(τ2) = γ2/ (n) where γ2 = ujn · · · uj1(α).We claim that γ1 6= γ2. But in view of Remark 2.5.5 and given that the sequences in >· · · > i1 and jn > · · · > j1 are distinct, this immediately follows. Using Remark 4.4.2, we getthat all summands sγ in sα · s(n) are obtained by picking a sequence in > · · · > i1 such thatµin · · ·µi1(τα) is an SRCT, and then letting γ be the outer shape of this SRCT. This givesus a multiplicity free expansion in the noncommutative Schur basis for the product sα · s(n)as stated in the claim.We conclude by proving a generalization of Theorem 4.3.5. Instead of counting maximalchains starting from ∅ and ending at some composition β, we consider maximal chainsstarting from a composition α and ending at a composition β where α <r β.86Theorem 4.4.4. Let fα,β denote the number of maximal chains from α to β in Rc. Thenfα,β =∑γ|β|−|α|Cβαγf∅,γ.Proof. Let |α| = m and |β| = n + m. If α <r β, then there is at least one sequence ofpositive integers in, · · · , i1 such that uin · · · ui1(α) = β. Let w = in · · · i1 and consider theSRCT τ = µin · · ·µi1(τα). Then sh(τ) = β/ γ where γ = sh(ρ−1(Q(std(w)))), by Theorem4.3.10. Note also that τ rectifies to τα, by an argument similar to the proof of Lemma 4.4.1.As stated in Theorem 2.4.6, we have thatCβαγ = number of SRCTs of shape β/ γ that rectify to τα.Now consider any skew SRCT τ of shape β/ γ that rectifies to τα. This can be completedto an SRCT τaug of straight shape β where the inner shape corresponding to γ has beenfilled according to an SSRCT of shape γ with distinct entries from the set B = {n+m,n+m − 1, . . . ,m + 1}. Now, notice that every choice of the filling of shape γ gives a uniquemaximal chain from α to β. To see this, perform a forward jeu de taquin slide starting fromthe lower left corner of ρ(τaug). As long as the resulting tableau has elements from B, repeatthe previous step. Notice that the procedure above stops when we reach ρ(τα). Reversingthese slides starting from ρ(τα), and using the generalized ρ map defined in Subsection 2.1.4,at every step gives us the unique maximal chain from α to β.Using the fact that the number of SRCTs of shape γ is f∅,γ, as established in Theorem4.3.5, the claim follows.Remark 4.4.5. It is worth emphasizing that fα,β is not the number of SRCT of shape β/α ingeneral, although it is true in the case where α is ∅ by Theorem 4.3.5. The above theorem canbe considered as a noncommutative generalization of extracting coefficients in the classicalidentity sλ/µ =∑ν`|λ|−|µ|cλµνsν.4.5 Some properties of our Robinson-SchenstedvariantWe will outline the relation between our variant of the Robinson-Schensted algorithm andthe classical Robinson-Schensted algorithm. The latter assigns to a permutation σ ∈ Sn87a pair of standard Young tableaux of the same shape and size equalling n. We begin bydefining standard Young tableaux.Given a partition λ, a standard Young tableau (SYT) T of shape λ is a filling of the boxesof λ with distinct positive integers from 1 to |λ|, satisfying the condition that the entries inT are strictly increasing along each row read from left to right and strictly increasing alongeach column read from bottom to top.The classical Robinson-Schensted algorithm and evacuation action for SYTs (which wewill denote by evac) are discussed in detail in [38, 42] and we will not present them here.To link the classical algorithms for SYTs with the variant for SRTs outlined in Subsection2.2.3, we will need the notion of the complement of a permutation, and the complement ofan SYT/SRT.Given a permutation σ = σ(1) · · ·σ(n) in single line notation, the complement of σ,denoted by σc is obtained by replacing σ(i) by n + 1 − σ(i) for 1 ≤ i ≤ n. Similarly, givenan SYT (SRT) T of shape λ ` n, the complement of T is the SRT (SYT), denoted by T c,obtained by replacing an entry k in T by n + 1 − k. Finally, define T t to be the transposeof any tableau T .Observe that the complement and transpose operators on SYTs/SRTs commute. Fur-thermore, both the evac operator on SY Ts and the e operator on SRTs commute with thetranspose operator. Finally, note thate(T ) = (evac(T c))c if T is an SRT,evac(T ) = (e(T c))c if T is an SYT.Since evac is an involution by [42, Proposition A.1.2.9], we can see that e is also an involution.Now we are ready to make explicit the relation between the classical algorithm for SYTsand the one for SRTs. Let pi ∈ Sn. We will denote the insertion and recording tableauxobtained by using the classical Robinson-Schensted correspondence by P (pi) and Q(pi) re-spectively, and denote those obtained by using our variant by Pv(pi) and Qv(pi) respectively.Observe that(Pv(pi), Qv(pi)) = ((P (pic))c, (Q(pic))c).Further using [42, Theorem A.1.2.10 and Corollary A.1.2.11] and the fact that evac is an88involution, we get that(P (pic), Q(pic)) = (evac(P (pi)t), Q(pi)t).The two equalities above together imply that(Pv(pi), Qv(pi)) = ((evac(P (pi)t))c, (Q(pi)t)c).Using [42, Corollary A.1.2.11] and the fact that P (pi−1) = Q(pi) we get thatPv(pi−1) = (evac(P (pi−1)t))c= (evac(Q(pi)t))c.Since (Qv(pi))c = Q(pi)t, we get thatPv(pi−1) = (evac(Qv(pi)c))c= e(Qv(pi)).Again, using [42, Corollary A.1.2.11] and the fact that Q(pi−1) = P (pi) we get thatQv(pi−1) = (Q(pi−1)t)c= (P (pi)t)c.Now, since P (pi)t = evac(Pv(pi)c), we get thatQv(pi−1) = (evac(Pv(pi)c))c= e(Pv(pi)).This establishes Lemma 2.2.13.89Chapter 5ConclusionWe now conclude with a discussion of questions borne out of the results and techniques inthis thesis.Just as we utilized the noncommutativity of NSym to give companion rules to theleft Pieri rules, one possible avenue to consider is to find a combinatorial rule to computesα · Ψn. This will result in a different lift of the classical Murnaghan-Nakayama rule inNSym. Data suggest that the coefficients in the expansion in this case are also ±1. Giventhat our proof techniques for computing Ψn · sα involved the left Pieri rules and box addingoperators crucially, our belief is that the jdt operators and the right Pieri rules will be keyto computing sα · Ψn combinatorially. Another avenue is to find a representation-theoreticinterpretation for the structure coefficients that arise when we expand a noncommutativepower sum symmetric function in terms of noncommutative Schur functions. While we didnot address them here, these structure coefficients can indeed be computed by iterativelyusing our noncommutative Murnaghan-Nakayama rule. In the classical case the structurecoefficients are character values of the symmetric group, and it would be interesting to knowwhat they are in the setting of NSym. Finally, we must mention the other noncommutativepower sum symmetric functions introduced in [13], denoted by Φn for n a positive integer.The problem of finding a Murnaghan-Nakayama rule for this basis is still unsolved, andcomputer experiments suggest that this rule will be substantially more complex than theone considered in this thesis.It would also be interesting to study the combinatorics of jdt operators arising fromour description of the backward jeu de taquin slide for SSRCTs, and implications thereoffor the associated poset of compositions Rc. The jdt operators satisfy certain congruencerelations that resemble plactic (or Knuth) relations. This hints at a monoid-like structure90for jdt operators that resembles the plactic monoid, and raises the question of finding apresentation for the jdt operators. It is known that if we have a monoid with relationscompatible with standardization and restriction to intervals, then we have a correspondingcombinatorial Hopf algebra. It would be extremely interesting to know if the above resultcan be used in the setting of jdt operators.Another area to consider is the computation of noncommutative Littlewood-Richardson(LR) coefficients. Given that jdt operators were introduced to model backward jeu de taquinslides on SSRCTs, which in turn were inspired by the definition of noncommutative LR coeffi-cients involving rectification, it is natural to ask if these operators give a more efficient way tocompute noncommutative LR coefficients. We hope to address some of the abovementionedquestions in the future.91Bibliography[1] M. Aguiar, N. Bergeron, and F. Sottile, Combinatorial Hopf algebras and gen-eralized Dehn-Sommerville relations, Compos. Math., 142 (2006), pp. 1–30.[2] J. Bandlow, A. Schilling, and M. Zabrocki, The Murnaghan-Nakayama rulefor k-Schur functions, J. Combin. Theory Ser. A, 118 (2011), pp. 1588–1607.[3] M. Bechard, Rectification of Composition Tableaux, arxiv preprint, http://arxiv.org/abs/1201.4502. Retrieved on 05/01/2015.[4] C. Bessenrodt, K. Luoto, and S. van Willigenburg, Skew quasisymmet-ric Schur functions and noncommutative Schur functions, Adv. Math., 226 (2011),pp. 4492–4532.[5] L. Billera, S. Hsiao, and S. van Willigenburg, Peak quasisymmetric functionsand Eulerian enumeration, Adv. Math., 176 (2003), pp. 248–276.[6] G. Duchamp, F. Hivert, J.-C. Novelli, and J.-Y. Thibon, Noncommutativesymmetric functions VII: free quasi-symmetric functions revisited, Ann. Comb., 15(2011), pp. 655-673.[7] G. Duchamp, F. Hivert, and J.-Y. Thibon, Noncommutative symmetric functions.VI. Free quasi-symmetric functions and related algebras, Internat. J. Algebra Comput.,12 (2002), pp. 671-717.[8] G. Duchamp, A. Klyachko, D. Krob, and J.-Y. Thibon, Noncommutative sym-metric functions. III. Deformations of Cauchy and convolution algebras, Discrete Math.Theor. Comput. Sci., 1 (1997), pp. 159–216.[9] R. Ehrenborg, On posets and Hopf algebras, Adv. Math., 119 (1996), pp. 1–25.92[10] S. Fomin and C. Greene, Noncommutative Schur functions and their applications,Discrete Math., 193 (1998), pp. 179–200.[11] J. Fulman, Descent algebras, hyperplane arrangements, and shuffling cards, Proc.Amer. Math. Soc, 129 (2001), pp. 965–973.[12] W. Fulton, Young Tableaux, L.M.S Student Texts, Vol. 35, Cambridge UniversityPress, Cambridge, 1997.[13] I. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh, and J.-Y. Thibon,Noncommutative symmetric functions, Adv. Math., 112 (1995), pp. 218–348.[14] I. Gessel, Multipartite P-partitions and inner products of skew Schur functions, Com-binatorics and algebra, Proc. Conf., Boulder/Colo. 1983, Contemp. Math. 34, 289-301,1984.[15] I. Gessel, and C. Reutenauer, Counting permutations with given cycle structureand descent set, J. Combin. Theory Ser. A, 64 (1993), pp. 189–215.[16] J. Haglund, M. Haiman, and N. Loehr, A combinatorial formula for Macdonaldpolynomials, J. Amer. Math. Soc., 18 (2005), pp. 735–761.[17] J. Haglund, K. Luoto, S. Mason, and S. van Willigenburg, QuasisymmetricSchur functions, J. Combin. Theory Ser. A, 118 (2011), pp. 463–490.[18] , Refinements of the Littlewood-Richardson rule, Trans. Amer. Math. Soc., 363(2011), pp. 1665–1686.[19] M. Haiman, On mixed insertion, symmetry, and shifted Young tableaux, J. Combin.Theory Ser. A, 50 (1989), pp. 196–225.[20] T. Halverson and A. Ram, Murnaghan-Nakayama rules for characters of Iwahori-Hecke algebras of the complex reflection groups G(r, p, n), Canad. J. Math., 50 (1998),pp. 167–192.[21] F. Hivert, Hecke algebras, difference operators, and quasi-symmetric functions, Adv.Math., 155 (2000), pp. 181–238.[22] M. Konvalinka, Skew quantum Murnaghan-Nakayama rule, J. Algebraic Combin., 35(2012), pp. 519–545.93[23] D. Krob, B. Leclerc, and J.-Y. Thibon, Noncommutative symmetric functions.II. Transformations of alphabets, Internat. J. Algebra Comput., 7 (1997), pp. 181–264.[24] D. Krob and J.-Y. Thibon, Noncommutative symmetric functions. IV. Quantumlinear groups and Hecke algebras at q = 0, J. Algebraic Combin., 6 (1997), pp. 339–376.[25] , Noncommutative symmetric functions. V. A degenerate version of Uq(glN), Inter-nat. J. Algebra Comput., 9 (1999), pp. 405-430.[26] A. Lascoux and M.-P. Schu¨tzenberger, Le mono¨ıde plaxique, Noncommutativestructures in algebra and geometric combinatorics (Naples, 1978), Quad. “Ricerca Sci.”Vol. 109, CNR, Rome, 1981, pp. 129–156.[27] M. van Leeuwen, An analogue of jeu de taquin for Littelmann’s crystal paths, Se´m.Lothar. Combin., 41 (1998).[28] D. Littlewood, The Construction of Invariant Matrices, Proc. London Math. Soc.,43 (1937), pp. 226–240.[29] K. Luoto, S. Mykytiuk, and S. van Willigenburg, An introduction to quasisym-metric Schur functions. Hopf algebras, quasisymmetric functions, and Young composi-tion tableaux., Springer Briefs in Mathematics, Springer, New York, 2013.[30] I. Macdonald, Symmetric functions and Hall polynomials. 2nd ed., Oxford UniversityPress, 1998.[31] S. Mason, A decomposition of Schur functions and an analogue of the Robinson-Schensted-Knuth algorithm, Se´m. Lothar. Combin., 57 (2008).[32] F. Murnaghan, The characters of the symmetric group, Amer. J. Math., 59 (1937),pp. 739–753.[33] T. Nakayama, On some modular properties of irreducible representations of a sym-metric group. I and II, Jap. J. Math., 17 (1940), pp. 165–184 and pp. 411–423.[34] S. Pon and Q. Wang, Promotion and evacuation on standard Young tableaux ofrectangle and staircase shape, Electron. J. Combin., 18 (2011).[35] R. Proctor, d-Complete posets Generalize Young Diagrams for the Jeu deTaquin Property, arxiv preprint, http://arxiv.org/abs/0905.3716. Retrieved on05/01/2015.94[36] L. Riegler and C. Neumann, Playing jeu de taquin on d-complete posets, arxivpreprint, http://arxiv.org/abs/1401.3619. Retrieved on 05/01/2015.[37] B. Sagan, Shifted tableaux, Schur Q-functions, and a conjecture of R. Stanley, J.Combin. Theory Ser. A, 45 (1987), pp. 62–103.[38] , The symmetric group. Representations, combinatorial algorithms, and symmetricfunctions. 2nd ed., Springer, 2001.[39] I. Schur, U¨ber eine Klasse von Matrizen, die sich einer gegebenen Matrix zuordnenlassen, Inaugural-Dissertation Berlin, 1901.[40] M.-P. Schu¨tzenberger, La correspondance de Robinson, Combinatoire etrepre´sentation du groupe syme´trique (Actes Table Ronde CNRS, Univ. Louis-PasteurStrasbourg, Strasbourg, 1976), Lecture Notes in Math. Vol. 579, Springer, Berlin, 1977,pp. 59–113.[41] P. S´niady, Robinson-Schensted-Knuth algorithm, jeu de taquin, and Kerov-Vershikmeasures on infinite tableaux, SIAM J. Discrete Math., 28 (2014), pp. 598–630.[42] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999.[43] , Promotion and evacuation, Electron. J. Combin., 16 (2009).[44] V. Tewari, A Murnaghan-Nakayama rule For noncommutative Schur functions, arxivpreprint, http://arxiv.org/abs/1403.0607. Retrieved on 05/01/2015.[45] , Backward jeu de taquin slides for composition tableaux and a noncommutativePieri rule, Electron. J. Combin., 22 (2015).[46] H. Thomas and A. Yong, A jeu de taquin theory for increasing tableaux, with ap-plications to K-theoretic Schubert calculus, Algebra & Number Theory, 3 (2009), pp.121–148.[47] , Equivariant Schubert calculus and jeu de taquin, arxiv preprint, http://arxiv.org/abs/1207.3209. Retrieved on 05/01/2015.[48] S. van Willigenburg, Noncommutative irreducible characters of the symmetric groupand noncommutative Schur functions, J. Comb., 4 (2013), pp. 403-418.95
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Operators on compositions and noncommutative Schur...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Operators on compositions and noncommutative Schur functions Tewari, Vasu 2015
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Operators on compositions and noncommutative Schur functions |
Creator |
Tewari, Vasu |
Publisher | University of British Columbia |
Date Issued | 2015 |
Description | In this thesis, we study a natural noncommutative lift of the ubiquitous Schur functions, called noncommutative Schur functions. These functions were introduced by Bessenrodt, Luoto and van Willigenburg and resemble Schur functions in many regards. We prove some new results for noncommutative Schur functions that are analogues of classical results, and demonstrate that the resulting combinatorics in this setting is equally rich. First we prove a Murnaghan-Nakayama rule for noncommutative Schur functions. In other words, we give an explicit combinatorial formula for expanding the product of a noncommutative power sum symmetric function and a noncommutative Schur function in terms of noncommutative Schur functions. In direct analogy to the classical Murnaghan-Nakayama rule, the summands are computed using a noncommutative analogue of border strips, and have coefficients ±1 determined by the height of these border strips. The rule is proved by interpreting the noncommutative Pieri rules for noncommutative Schur functions in terms of box adding operators on compositions. We proceed to give a backward jeu de taquin slide analogue on semistandard reverse composition tableaux. These tableaux were first studied by Haglund, Luoto, Mason and van Willigenburg when defining quasisymmetric Schur functions. Our algorithm for performing backward jeu de taquin slides on semistandard reverse composition tableaux results in a natural operator on compositions that we call the jdt operator. This operator in turn gives rise to a new poset structure on compositions whose maximal chains we enumerate. As an application, we also give new right Pieri rules for noncommutative Schur functions that use the jdt operators, in contrast to the left Pieri rules given by Bessenrodt, Luoto and van Willigenburg. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2015-08-05 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0166481 |
URI | http://hdl.handle.net/2429/54290 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2015-09 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2015_september_tewari_vasu.pdf [ 602.85kB ]
- Metadata
- JSON: 24-1.0166481.json
- JSON-LD: 24-1.0166481-ld.json
- RDF/XML (Pretty): 24-1.0166481-rdf.xml
- RDF/JSON: 24-1.0166481-rdf.json
- Turtle: 24-1.0166481-turtle.txt
- N-Triples: 24-1.0166481-rdf-ntriples.txt
- Original Record: 24-1.0166481-source.json
- Full Text
- 24-1.0166481-fulltext.txt
- Citation
- 24-1.0166481.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0166481/manifest