Towards a classification of descent multiplicity-free compositions by Caleb Cheek B.Sc., University of Alberta, 2010 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) August 23, 2012 c Caleb Cheek 2012 Abstract This work studies combinatorics related to expansions of a quasisymmetric refinement of Schur functions into Gessel’s fundamental basis, with almost all results concerning whether an expansion is multiplicity-free. The combinatorial side of this problem concerns a certain composition poset, and whether there are two standard fillings of the same composition diagram with a given descent set. This thesis uses entirely combinatorial arguments, extending results by Bessenrodt and van Willigenburg to work towards a classification of such descent multiplicity-free compositions. The main tools used regard the situation of appending or prepending parts to compositions. Compositions with multiplicity retain multiplicity when parts are appended or prepended, while multiplicity-free compositions stay multiplicity-free when a class of shapes called staircase-like are appended. A classification of compositions which are partitions or reverse partitions is achieved, leading up to a classification of compositions not containing a part of length one. This is used as the basis for a conjectured classification of multiplicity-free compositions without a trailing staircase. The conjecture would in turn imply a complete classification of multiplicity-free compositions. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 1 Preliminaries . . . . . . . . . . . 1.1 Introduction . . . . . . . . . . 1.2 Compositions . . . . . . . . . 1.2.1 Diagrams and tableaux . . . . 1 1 2 3 2 Descent multiplicity-free compositions . . . . . . . . . . . . . . . . 2.1 Extending multiplicity-free compositions . . . . . . . . . . . . . 2.1.1 Extending multiplicities through covering relations. . . . 2.1.2 Concatenation. . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Staircases . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Results for partition and reverse partition shapes . . . . . . . . . 2.2.1 Partition shapes . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Reverse partition shapes . . . . . . . . . . . . . . . . . . 2.3 Multiplicity-free compositions with no parts of length one . . . . 2.4 Conjectured classification of multiplicity-free compositions . . . 2.4.1 Multiplicity-free compositions without a trailing staircaselike shape . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Conjecture on inserting parts in the middle of a composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 8 8 9 11 12 12 18 22 31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 34 36 iii Acknowledgements I would like to thank Stephanie van Willigenburg for her guidance, as well as Vasu Tewari for interesting discussions on mathematical and (mostly) non-mathematical topics. I would also like to thank the authors of [3] for their Maple program to calculate standard composition tableaux and determine multiplicities, which was extraordinarily useful in developing conjectures for this thesis. Special thanks go to Stephanie van Willigenburg for her very careful proofreading and Andrew Rechnitzer for his assistance in editing this thesis. iv Chapter 1 Preliminaries 1.1 Introduction In representation theory, much has been made of the multiplicity-free representations for which the irreducible components occur exactly once. Such representations are ubiquitous, often owing to the fact that their decomposition into irreducibles is canonical. In fact, much of classical invariant theory, including Weyl’s fundamental theorems, can be understood in terms of multiplicity-free representations [6]. Central in algebraic combinatorics is the algebra of symmetric functions, Sym, and its interaction with both representation theory and various combinatorial objects. The rich interplay between the basis of Schur functions for Sym and the combinatorics of Young tableaux has been especially significant. Accordingly, examination of multiplicity-free representations benefits from techniques in algebraic combinatorics when there is a correspondence between the representations involved and some basis of Sym or one of its generalizations. Often, a representation will be multiplicity-free exactly when its corresponding symmetric function is multiplicity-free when expanded in a particular basis. The multiplicity-free question has been answered in the case of expanding the product of two Schur functions as a sum of Schur functions [9], and the product of two Schur P-functions as a sum of Schur P-functions [1], as well as expanding skew Schur functions and Schur P-functions as sums of Schur functions [4, 7, 10]. Each case has yielded applications to the character theory of algebraic objects related to the symmetric group. In the other direction, Stanley has used the multiplicity-free rule for multiplying Schur functions of rectangular shape to count self-complementary plane partitions [8]. Multiplicity-free products have also been a key ingredient in constructing explicit bijections related to q-analogues of Littlewood-Richardson coefficients [9]. Our problem concerns the generalization of Sym to the algebra of quasisymmetric functions, QSym, and the basis of quasisymmetric Schur functions indexed by compositions. Just as the Schur functions interact with the combinatorics of Young tableaux, quasisymmetric Schur functions interact with the combinatorics of composition tableaux. In particular, the expansion of the quasisymmetric Schur 1 1.2. Compositions functions indexed by a composition α into a sum of Gessel’s fundamental basis of quasisymmetric functions is determined by the number of composition tableaux with a given descent set, giving an entirely combinatorial approach to the problem. If this expansion is multiplicity-free, we term the composition α multiplicity-free, and it is this side of the problem we will be interested in. Previous work by Bessenrodt and van Willigenburg in [3] has classified the multiplicity-free Schur functions and skew Schur functions when expanding (as elements of QSym) in terms of Gessel’s fundamental basis. In the same paper, they classify multiplicity-free quasisymmetric Schur functions which expand into only one or two components or which correspond to compositions with one or two parts, as well as multiplicity-free families of quasisymmetric Schur functions corresponding to compositions that rearrange the same partition. Our goal in this thesis is to build toward a conjecture we believe would classify all multiplicity-free compositions. Section 2.1 outlines the guiding principles used, identifying a class of shapes that don’t introduce multiplicity when appended, and noting the fact that compositions with multiplicity retain multiplicity when appended or prepended with new parts. Section 2.2 gives a classification of multiplicity-free compositions which happen to be partitions or reverse partitions, and this is shown in Section 2.3 to give a nearly complete list of compositions not containing a part of length one. We finish in Section 2.4 with a conjecture that, if true, seems to give a way to generate all multiplicity-free compositions. We also identify some key ideas that would simplify its proof. 1.2 Compositions Let n ∈ N. A composition α = (α1 , α2 , . . . , αk ) of n is a sequence of positive integers αi with ∑ki=1 αi = n. We also include the empty composition 0/ as the only composition of 0 as part of our definition. We refer to n as the size of α, denoted |α|. The αi are referred to as the parts of α, and the number of parts k is called the length of α, denoted (α). The length of the longest part of α is referred to as its width, denoted w(α). A partition is a composition which has its parts in weakly decreasing order. Any composition α determines a unique partition λ (α) by rearranging its parts into weakly decreasing order. We will frequently make use of a natural bijection between compositions of n and subsets of [n − 1] := {1, 2, . . . , n − 1}. This is given by associating a composition (α1 , α2 , . . . , αk ) with the subset set(α) := {α1 , α1 + α2 , . . . , α1 + α2 + · · · + αk−1 } ⊆ [n − 1]. If we have repeated parts αi+1 = αi+2 = · · · = αi+m = k, we will usually abbre2 1.2. Compositions viate this part of the list as km , with k0 representing an omission from the list. 1.2.1 Diagrams and tableaux Given a composition α, its composition diagram is the left-justified array of boxes with αi boxes in row i from the top for 1 ≤ i ≤ (α). We will denote this diagram by α as well, and treat a composition and its diagram interchangeably, referring to the parts of α as its rows, and so forth. When it is necessary to index a box of the diagram, we do so in the matrix-style convention (as opposed to the Cartesian convention), with box (i, j) referring to the box in the ith row from the top and jth column from the left. Example 1.2.1. The composition diagram for (1, 22 , 1, 3), with box (3, 2) shaded. A subdiagram of the composition diagram for α is any subset D of the boxes in α. If the subdiagram happens to consist of left-justified rows, we will write it in composition notation as a list of row lengths D = (d1 , d2 , . . . , dk ). We can now have rows of length 0, since D is not necessarily a composition. Example 1.2.2. The composition diagram (1, 22 , 1, 3), with subdiagram (0, 2, 1, 0, 2) shaded. A filling of a composition diagram is an assignment of a positive integer to each box of the diagram. 3 1.2. Compositions The composition poset LC . We will be interested in fillings of composition diagrams that respect an order defined through covering relations as follows: Given two compositions α and γ, we say that γ covers α if γ can be obtained from α by either: (i) prepending α with a new part of size 1, or (ii) by adding 1 to the first (leftmost) part of size k for some k. We write α γ to indicate that γ covers α. We now have a partial order given by the relation ≤, where α ≤ γ if γ can be obtained from α by a sequence of cover relations. The resulting poset on compositions is denoted by LC . Example 1.2.3. The compositions covering (1, 22 , 1, 3) are (1, 22 , 1, 4) , (1, 3, 2, 1, 3), (23 , 1, 3) and (12 , 22 , 1, 3), and their respective diagrams (with the new box shaded) are: , , , and . Composition tableaux. Let α be a composition of n, and 0/ = α n α n−1 ··· α1 α0 = α be a sequence of consecutive cover relations in LC (in other words, a saturated chain from 0/ to α in the poset LC ). If we put the number i in the box deleted when moving from α i−1 to α i for 1 ≤ i ≤ n, the resulting filling T is a standard composition tableau (SCT) of shape α. We will interchangeably describe SCTs by the filling of the composition diagram with integers or the procedure of adding boxes according to the cover relations. The pictorial aspect of the description as fillings makes concise descriptions, while the description as a procedure of adding boxes is much more instructive in detailing the SCTs of a certain type or listing all SCTs of a given shape. Example 1.2.4. The standard composition tableau T 4 1.2. Compositions 3 2 4 1 of shape (2, 2) arises from the saturated chain 0/ Remark 1.2.5. Standard composition tableaux are defined in their original context by a triple rule [2, Definition 2.9, Proposition 2.11]. For our purposes, the triple rule description is cumbersome, so we will not give it here. Descents. The descent set of a composition tableau T is the set desc (T ) ⊆ [n − 1] of all i where i + 1 appears in a box weakly to the right of i. An element of this set is referred to as a descent of T . We will occasionally switch between the set desc (T ) and the associated composition com(T ) := set−1 (desc (T )). We can also describe the descent set of a composition tableaux as part of the box-adding procedure: The integer i is a descent in a saturated chain 0/ = α n α n−1 · · · α 1 α 0 = α if the box deleted when moving from α i−1 to α i is weakly left of the box deleted when moving from α i to α i+1 . Example 1.2.6. The filling 1 5 3 6 2 7 9 8 4 is an SCT of shape (1, 22 , 1, 3), with descent set {1, 2, 3, 5, 6, 7}. This descent set has the composition (13 , 2, 12 , 2) as its associated composition of 9. Canonical filling. Given any composition diagram α = (α1 , α2, . . . , α (α) ), there is a unique filling T of α with desc (T ) = set(α), called the canonical filling of the diagram α defined by filling row i with the entries i−1 i−1 i 1 + ∑ α j, 2 + ∑ α j, . . . , ∑ α j. j=1 j=1 j=1 5 1.2. Compositions This is the filling associated to the saturated chain from 0/ to α where boxes are added in order from left to right, bottom to top; accordingly, we say that if row i contains these entries, it is row-filled. Example 1.2.7. The diagram (1, 22 , 1, 3), now row-filled. 1 3 2 5 4 6 9 8 7 When building composition tableaux for more complicated shapes, it will be useful to describe an SCT of shape β as extending the saturated chain used to build an SCT T of a composition α ≤ β . To facilitate the description of such tableaux in terms of their description as fillings, define T + m to be the tableau obtained from T by adding m to each entry. If the difference in size |β | − |α| is m boxes, then an SCT of shape β can be described by starting with T + m of shape α and filling the remaining boxes in some way that satisfies the cover relations. Remark 1.2.8. We will make extensive use of the equivalence between the two descriptions of SCTs when we describe tableaux this way, usually starting with either T or T + m in pictorial form as a filling and then describing the rest of the SCT by order in which boxes are added. Example 1.2.9. Using the SCT T from Example 1.2.4, we can extend to a filling of the shape (3, 2, 2) by starting with T + 3 in the (0, 2, 2) subdiagram, and then row-filling the top row to get the SCT 3 2 6 5 7 4 1 with descent set {3, 4, 6}. Suppose we build an SCT of shape α from the saturated chain 0/ = α n α n−1 · · · α 1 α 0 = α. If there is some subchain α i · · · α k where each box added is the leftmost box in the lowest row not already completed, then we say that the subdiagram formed by these boxes is built in row order. The canonical filling of α is the result of building the whole diagram in row order. 6 1.2. Compositions Unlike the canonical filling for a composition diagram, building a subdiagram in row order is not always possible; for instance, if α = (2, 2) and β = (3, 3), then α ≤ β , but a filling of α cannot extend to a filling of β by building the remaining subdiagram in row order. Descent multiplicities. Let α be a composition of n. Motivated by the expansion of a quasisymmetric refinement of Schur functions into Gessel’s fundamental basis of quasisymmetric functions ([5, Theorem 6.2]), we will be interested in counting the number of standard composition tableaux of shape α with a given descent set. Identifying a descent set with its associated composition, we write dα,β for the number of standard composition tableaux T of shape α with com(T ) = β , and refer to dα,β as the descent multiplicity of β in the shape α. Since computation of descent multiplicities in general is expected to be a very difficult problem (for a connection to a quasisymmetric analogue of the notoriously difficult Kostka numbers, see [5, Theorems 6.1 and 6.2]), we will mostly restrict our attention to the situation where dα,β is either 0 or 1 for every composition β of n; if this is the case, we say that the composition α is (descent) multiplicity-free. Working towards this goal, we will frequently need draw upon the respective strengths of the two descriptions of SCTs. Demonstrating multiplicity in a composition α simply requires a pair of tableaux with the same descent set, while verifying that a composition is multiplicity-free requires close analysis of possible building procedures to distinguish each descent set. 7 Chapter 2 Descent multiplicity-free compositions 2.1 Extending multiplicity-free compositions This section outlines what are effectively the main guiding principles that have been used to generate the results in this thesis. We start with some tools that simplify the amount of calculation involved in verifying whether a composition is multiplicity-free. 2.1.1 Extending multiplicities through covering relations. It will be useful if we can get some handle on the interaction between multiplicity and covering relations. The following lemma provides a shorthand way to demonstrate multiplicity in certain compositions covering a composition with multiplicity: Lemma 2.1.1. Suppose α and β are compositions with α ≤ β , and that α has multiplicity from a pair of tableaux T and T . Consider the location of the last box added, which is filled with the entry 1. If it happens that there is a saturated chain from α to β where the next box added is either • weakly to the left of both the box containing 1 in T and the box containing 1 in T , or • strictly to the right of both the box containing 1 in T and the box containing 1 in T , then β will have multiplicity as well. Remark 2.1.2. In the situation of Lemma 2.1.1, we will say that the multiplicity in α extends to multiplicity in β . In particular, if the entry 1 occurs in the same column of T and T , then any saturated chain from α to β will satisfy one of the two conditions in the lemma. In this case, we will simply say that the multiplicity in α extends to multiplicity in β without reference to how the remaining subdiagram is built. 8 2.1. Extending multiplicity-free compositions Proof. Simply continue the pair of saturated chains corresponding to T and T from 0/ to α on to β , using the same procedure to build the rest of β in both cases. The descents in these chains are clearly in the same places, since the next box added after filling α will either contribute a descent in both or neither. Example 2.1.3. For α = (1, 3, 3), we have multiplicity coming from the pair of tableaux 3 1 5 3 2 , and 5 4 2 7 6 4 6 1 7 with descent set {1, 3, 5}. The composition β = (1, 4, 3) covers α, and the only box to be added is strictly (and therefore weakly) to the right of the box containing 1 in both these tableaux. Consequently, the multiplicity in α extends to multiplicity in β ; in fact, it extends to β = (1, m, k) for any m ≥ k ≥ 3. The multiplicity in α also extends to (1k1 , 3, 3) for k1 ∈ N since all of the new boxes added are in the first column. The next example shows that it is not always the case that multiplicity extends from α to a shape β ≥ α: Example 2.1.4. For α = (3, 5), we have multiplicity from the pair of tableaux 5 2 1 8 7 6 4 3 , and 5 4 2 8 7 6 3 1 but calculation shows that the composition β = (4, 5) ≥ α is multiplicity-free. The multiplicity in (3, 5) cannot be extended to (4, 5), since the next box added contributes a descent when extending the second tableau, but not the first. 2.1.2 Concatenation. Given two compositions α and γ, define their concatenation α · γ (also referred to as γ appended to α, or α prepended to γ) to be the composition consisting of the parts of α followed by the parts of γ. The following simple lemma is an essential tool in classifying the multiplicity-free compositions: Lemma 2.1.5. If α and γ are compositions, then appending or prepending γ to α can only increase multiplicities. Specifically, we have that dα,β ≤ d(α·γ),(β ·γ) 9 2.1. Extending multiplicity-free compositions and dα,β ≤ d(γ·α),(γ·β ) for all compositions β . Proof. For the first inequality, start with an SCT T of shape α with descent set set(β ). Build an SCT T of shape α · γ by first building γ in row order and then building the prepended part α using the same order as T . In terms of a filling of α · γ with integers, this appends the canonical filling of γ with |α| added to each entry of T . The descents of T in the appended part γ of T are simply set(γ), and contributions to the descent set from the prepended part are set(β ) (from the descents internal to T ) together with |α|, since this entry appears in bottom left corner of the prepended shape α, and |α| + 1 is therefore weakly to the right. The result is then an SCT T of shape α · γ with com(T ) = β · γ. Similarly, to build an SCT of shape γ · α and descent set γ · β , first fill α with T + |γ|, and then row-fill the prepended part γ. Example 2.1.6. With α = (2, 2) and γ = (3, 2), we have that dα,(1,2,1) = 1 from the SCT T= 3 2 4 1 with descent set {1, 3}. Following the procedure in Lemma 2.1.5, we start with T + 5 and add boxes on top in row order to get the SCT 3 2 5 4 8 7 9 6 1 with descent set {3, 5, 6, 8} and associated composition (3, 2, 1, 2, 1), demonstrating that d(γ·α),(γ·(1,2,1)) ≥ 1. It is easy to see that in the case when γ = (1k ), then dα,β = d(α·γ),(β ·γ) since the appended boxes must be filled before any of the boxes of α, and there is only one SCT of shape γ. We will soon extend this observation. Lemma 2.1.5 greatly cuts down on the amount of work involved in generating a list of multiplicity-free compositions as the number of parts grows; a composition α = (α1 , α2 , . . . , αk ) only has a chance of being multiplicity-free if (α1 , α2 , . . . , αk−1 ) and (α2 , α3 , . . . , αk ) are both multiplicity-free. 10 2.1. Extending multiplicity-free compositions 2.1.3 Staircases We turn our attention to the shapes γ = (1k1 , 2k2 , 3k3 , . . . , mkm ) where ki ≥ 1 for all 1 ≤ i ≤ m. We call such a composition a fat staircase. Example 2.1.7. The fat staircase (1, 22 , 3, 4). The key property of fat staircases for our purposes is that if i + 1 appears in the composition, then i appears in a higher row for every i ∈ N. We will call a composition with this property staircase-like. The following lemma is just a rephrasing of the second cover relation in LC : Lemma 2.1.8. Let α be a composition, and suppose αi = k. If j > i and α j ≥ k +1, then when building an SCT of shape α, row j must already have k + 1 boxes before row i is completed. The significance of Lemma 2.1.8 is that it gives us a way to compute multiplicities after appending a staircase-like shape: Lemma 2.1.9. Let α be a composition and γ be staircase-like. Then the SCTs of shape α · γ have descent sets T1 ∪ {|α|} ∪ (T2 + |α|), where T1 is an SCT of shape α and T2 is an SCT of shape γ. Furthermore, the multiplicity of T1 ∪{|α|}∪(T2 +|α|) in α · γ is the product dα,com(T1 ) · dγ,com(T2 ) of the multiplicity of com(T1 ) in α and the multiplicity of com(T2 ) in γ. Proof. Lemma 2.1.8 tells us that when building an SCT of shape α · γ, all rows of length m in γ must be completed before any higher row of length m − 1 is completed. Since γ must start with a part of length 1, and for every 2 ≤ m ≤ w(α), some part of length m − 1 will occur before any parts of length m, we must fill the rest of γ before the box in the first row. The box in the first row of γ must in turn be filled before any of the boxes of α. Thus the SCTs of shape α · γ are made by taking an SCT T2 of shape γ, and then extending T2 + |α| to an SCT of shape α · γ by prepending an SCT T1 of shape α. The descents of this new SCT are just the descents in T1 and T2 + |α|, together with the extra descent |α| from the bottom corner of T1 since |α| + 1 is immediately below it. 11 2.2. Results for partition and reverse partition shapes This also gives a recursive formula to find descent sets and multiplicities in the case where γ is actually a concatenation of several staircase-like shapes. For the particular cases of γ = (1k1 ) or γ = (1k1 , 2), the only SCT of shape γ is row-filled, so α · γ inherits multiplicities from α. Thus Lemma 2.1.9 extends the result in [3, Lemma 4.2]. We now have a useful way to generate new multiplicity-free compositions: Corollary 2.1.10. If α is a multiplicity-free composition and γ is a multiplicity-free staircase-like composition, then α · γ is multiplicity-free. 2.2 Results for partition and reverse partition shapes Based on our observations in the last section, an easy place to start is to first classify the multiplicity-free compositions which form either weakly increasing or weakly decreasing sequences. Recall that a composition with weakly decreasing part lengths is a partition. We will refer to a composition with weakly increasing part lengths as a reverse partition. 2.2.1 Partition shapes Theorem 2.2.1. A partition α is descent multiplicity-free if and only if it is one of the following, possibly followed with (1k1 ) appended for some k1 ∈ N0 : (i) (2k ) for k ≤ 4, (ii) (3k ) for k ≤ 2, (iii) (4k ) for k ≤ 2, (iv) (m, 2k ) for 0 ≤ k ≤ 3, m ≥ 3, (v) (m, 3) for m ≥ 4. The first three cases can be shown to be multiplicity-free computationally. We verify that the compositions in the latter two cases are multiplicity-free in a series of lemmas, and follow with a proof that all other partitions have multiplicity. Lemma 2.2.2. [3, Lemma 5.2] For m ≥ 2, the composition α = (m, 2) is multiplicityfree, and the possible descent sets for SCTs of shape α belong to one of the following two cases: (i) {i, m + 1} for 1 ≤ i ≤ m − 1, and 12 2.2. Results for partition and reverse partition shapes (ii) {m}. Proof. The descent set of an SCT of shape α depends on the order in which box in position (2, 2) is filled: The cover relations dictate that we either: • complete filling the second row before starting the first, in which case the diagram ends up row-filled with descent set {m}, or • first fill the shape ... with 2 ≤ k ≤ m boxes in the first row before filling box (2, 2). In this case, we now have that m + 1 is a descent from box (1, 1), as is m + 1 − k in box (2, 2). Lemma 2.2.3. For m ≥ 2, the composition α = (m, 2, 2) is multiplicity-free, and the possible descent sets for SCTs of shape α belong to one of the following four cases: (i) {m, m + 2} (ii) {i, m + 1, m + 3} for 1 ≤ i ≤ m (iii) {i, j, m + 2, m + 3} for 2 ≤ j ≤ m, 1 ≤ i < j, and (iv) {i, m + 1, m + 2} for 1 ≤ i ≤ m − 1. Proof. We have a few more cases to deal with than the previous lemma, owing to the fact that there are two valid composition tableaux for a square diagram (2, 2). We get two SCTs of shape α by directly extending these fillings: either we row-fill the entire diagram to get descent set {m, m + 2}, or we start with the SCT T of shape (2, 2) 3 2 4 1 and then extend T + m to an SCT of shape α by row-filling the top row, in which case we get the descent set {m, m + 1, m + 3}. There are two types of SCT of shape α that result from first filling the shape 13 2.2. Results for partition and reverse partition shapes ... with k boxes in the top row for some k with 2 ≤ k ≤ m and then the last box in the (2, 2) square before completing the top row: this is just the shape in the last lemma with (1) appended. These give descent sets {m + 1 − k, m + 1, m + 3} and {m + 1 − k, i, m + 2, m + 3} for m + 1 − k < i ≤ m. We could instead fill ... with 2 ≤ k ≤ m boxes in the top row (noting that the only SCT of this shape is the canonical filling) and then the last box in the square to give descent set {m + 1 − k, m + 1, m + 2}. Lemma 2.2.4. The composition α = (m, 2, 2, 2) is multiplicity free for m ≥ 2. Remark 2.2.5. We don’t list descent sets here for reasons of brevity, although we do generate them in the proof. Proof. We once again break down the SCTs of shape α into those which directly extend fillings of the rectangle (2, 2, 2), and those where 2 ≤ k ≤ m boxes in the top row are filled before the last box in the rectangle, in which case we can apply the previous two lemmas. There are five SCTs of shape (2, 2, 2), namely 2 1 2 4 3 , 5 4 , 4 6 5 3 6 1 3 6 2 3 4 3 1 , 5 4 , 5 2 5 1 1 6 2 6 For each such filling, T + m extends to an SCT of shape α by row-filling the top row, contributing the descent sets {m, m + 2, m + 4}, {m, m + 2, m + 3, m + 5}, {m, m + 1, m + 3, m + 4}, {m, m + 1, m + 3, m + 5} and {m, m + 1, m + 2, m + 4, m + 5}, respectively. There are two ways to first fill the shape 14 2.2. Results for partition and reverse partition shapes ... with 2 ≤ k ≤ m boxes in the top row and then the last box in the rectangle. These simply extend the two SCTs of shape (2, 2), resulting in the two descent sets {m + 1 − k, m + 1, m + 2, m + 4} and {m + 1 − k, m + 1, m + 2, m + 3, m + 5}. The SCTs generated by filling ... with 2 ≤ k ≤ m boxes in the top row and then the last box in the rectangle are obtained from SCTs of shape (k, 2) since the appended part (1, 2) must be filled before the rest of the shape. Combining this observation with Lemma 2.2.2, the SCTs obtained have descent sets {m + 1 − k, m + 1, m + 3, m + 4} and {m + 1 − k, i, m + 2, m + 3, m + 4} for m + 1 − k < i ≤ m. Lastly, the SCTs generated by filling ... with 2 ≤ k ≤ m boxes in the top row and then the last box in the rectangle are obtained from SCTs of shape (k, 2, 2) since the appended part of length 1 must be filled before the rest of the shape. Lemma 2.2.3 then gives that the SCTs obtained have descent sets (i) {m + 1 − k, m + 1, m + 3, m + 5}, (ii) {m + 1 − k, i, m + 2, m + 4, m + 5} for m + 1 − k < i ≤ m + 1, (iii) {m + 1 − k, i, j, m + 3, m + 4, m + 5} for m + 1 − k < i < j ≤ m + 1, and (iv) {m + 1 − k, i, m + 2, m + 3, m + 5} for m + 1 − k < i ≤ m. Since all of these descent sets are unique, the result follows. 15 2.2. Results for partition and reverse partition shapes Lemma 2.2.6. For m ≥ 3, the composition α = (m, 3) is multiplicity-free, and the possible descent sets for SCTs of shape α belong to one of the following five cases: (i) {m} (ii) {m − 1, m + 1} (iii) {i, m + 1} for 1 ≤ i ≤ m − 2 (iv) {i, m + 2} for 2 ≤ i ≤ m − 1, and (v) {i, j, m + 2} for 1 ≤ i < j ≤ m, i = j − 1. Proof. If we fill all three boxes in the second row before a box in the first row, the diagram ends up row filled with descent set {m}. Suppose we start by filling two boxes in the second row before filling a box in the first row. There are two cases to consider: • If we fill the first box in the top row and then the last box in the second row, we get descent set {m − 1, m + 1}. • If we fill k boxes in the top row with 3 ≤ k ≤ m before the last box in the second row, we get descent set {m + 1 − k, m + 1}. If we fill only one box of the second row before a box in the first row, covering relations force the next box filled to be in position (1, 2). Extend the top row to k boxes with 2 ≤ k ≤ m before filling box (2, 2). We again have two cases: • If k ≥ 3, we can now fill both boxes in the second row, and the resulting SCT has descent set {m + 2 − k, m + 2}. • If k ≤ m − 1, we can fill the box in position (2, 2), and then fill 1 ≤ ≤ m − k more boxes in the first row before filling box (2, 3) to get descent set {m + 1 − k − , m + 2 − k, m + 2}. We are now ready to prove the theorem. Proof of Theorem 2.2.1. The previous lemmas show that the last two cases are multiplicity-free (noting that the composition (m) is clearly multiplicity-free), and the first three can be verified by simple computation. Appending parts of length 1 doesn’t change whether a composition has multiplicity from Lemma 2.1.9. We now show that there are no other partition shapes which are multiplicity-free. If m > k ≥ 4, then (m, k) has multiplicity: Row-fill the subdiagram (m − 2, k − 3), and then use the two fillings 16 2.2. Results for partition and reverse partition shapes ... 4 5 2 3 1 , and ... 3 5 4 1 2 for the remaining subdiagram. The composition (5, 5) has multiplicity from the two tableaux 8 5 4 2 1 10 9 7 6 3 , and 8 7 6 4 3 10 9 5 2 1 with descent set {2, 5, 8}. This extends to show that (m, m) has multiplicity for m ≥ 5. The composition (25 ) has multiplicity, coming from the two tableaux 3 2 3 2 4 1 6 5 6 5 , and 7 4 9 8 8 10 7 9 10 1 which both have descent set {1, 3, 4, 6, 7, 9}. These two fillings extend to show that (m, 24 ) has multiplicity for m ≥ 3. The composition (3, 3, 2) has multiplicity from the two tableaux 5 3 2 5 4 2 7 6 4 , and 7 6 1 8 1 8 3 with descent set {1, 3, 5, 7}. This extends to give multiplicity in (m, 3, 2) for m ≥ 3. The composition (3, 3, 3) has multiplicity from the two pairs of tableaux 5 3 2 5 4 2 7 6 4 , and 7 3 1 9 8 1 9 8 6 with descent set {1, 3, 5, 7}, and 4 2 1 6 4 3 8 7 5 , and 8 7 5 9 6 3 2 1 9 17 2.2. Results for partition and reverse partition shapes with descent set {2, 4, 6, 8}. These fillings extend to show (m, 3, 3) has multiplicity. The fillings of (m, 3, 3) in turn extend to show that (m, m, m), and in particular (4, 4, 4), have multiplicity for m ≥ 3. We now have that a composition starting with m ≥ 5 cannot be multiplicity-free unless it is listed in the theorem. The composition (4, 4, 2) has multiplicity from the pair of tableaux 6 4 3 1 6 5 2 1 9 8 7 5 , and 9 8 7 3 10 2 10 4 with descent set {2, 4, 6, 9}. This extends to give multiplicity in (4, 4, 3) as well, and we have already seen that (4, 4, 4) has multiplicity. 2.2.2 Reverse partition shapes Theorem 2.2.7. A reverse partition α is descent multiplicity-free if and only if it is one of the following: (i) (1k1 , 2k2 ) with k1 ∈ N0 and k2 ≤ 4, (ii) (1k1 , 2k2 , m) for m ≥ 3 with k1 ∈ N0 and 0 ≤ k2 ≤ 1, (iii) (1k1 , 2k2 , 3) with k1 ∈ N0 and k2 ≤ 3, (iv) (1k1 , 2, 3k3 ) with k1 ∈ N0 and k3 ≤ 2, (v) (1k1 , 2, 3, 4) with k1 ∈ N0 , (vi) (3, 3), (3, 4), (4, 4), or (4, 5). We again split the proof of the theorem into several lemmas: Lemma 2.2.8. For m ≥ 3 and k1 ∈ N, composition α = (1k1 , m) is multiplicity-free, and the possible descent sets for SCTs of shape α are of the form {i1 , i2 , . . . , ik1 } with 1 ≤ i1 < i2 < · · · < ik1 < m + k1 − 1. Proof. An SCT of shape α necessarily starts with filling two boxes in the bottom row. After this, boxes on top can be added at any time, so any of the remaining entries can end up in the first column, and these constitute the descents of the SCT. Lemma 2.2.9. For m ≥ 3, the composition α = (2, m) is multiplicity-free, and the possible descent sets for SCTs of shape α belong to one of the following two cases: 18 2.2. Results for partition and reverse partition shapes (i) {i} for 2 ≤ i ≤ m − 1, and (ii) {i, j} for 1 ≤ i ≤ j − 2 ≤ m − 2. Proof. If k boxes of the second row are filled before the box (1, 1), we have two ways to complete filling the diagram: • if 3 ≤ k ≤ m, we can fill the box (1, 2) immediately (if k ≥ 3), in which case the only descent is m + 2 − k in position (1, 1), or • if 2 ≤ k ≤ m − 1, we can first add ≥ 1 boxes to the second row before filling box (1, 2), in which case this box contributes the descent m + 1 − k − . Lemma 2.2.10. For m ≥ 3 and k ∈ N, the composition α = (1k , 2, m) is multiplicityfree, and the possible descent sets for SCTs of shape α belong to one of the following two cases: (i) {i1 , i2 , . . . , ik , ik+1 } with 1 ≤ i1 < i2 < · · · < ik−1 < ik − 1 ≤ m + k − 1, and (ii) {i1 , i2 , . . . , ik , ik+1 , ik+2 } with 1 ≤ i1 < i2 < · · · < ik−1 < ik < ik+1 − 2 ≤ m + k − 2. Proof. We must first fill the subdiagram (0, 2, n) for some 3 ≤ n ≤ m before the first of the prepended rows of length 1 is filled. After this the rest of the first column can be filled with any of the remaining entries (in ascending order, top to bottom), which all contribute a descent. Applying the last lemma, we get the descent sets • {i1 , i2 , . . . , ik−1 , m + k − n, a} with 1 ≤ i1 < i2 < · · · < ik−1 ≤ m + k − n − 1 and m + k + 2 − n ≤ a ≤ m + k − 1, • {i1 , i2 , . . . , ik−1 , m + k − n, a, b} with 1 ≤ i1 < i2 < · · · < ik−1 ≤ m + k − n − 1 and m + k + 1 − n ≤ a ≤ b − 2 ≤ m + k − 2. We can now prove the theorem. Proof of Theorem 2.2.7. The three lemmas deal with the second case since (m) is clearly multiplicity-free. To deal with the remaining cases, suppose α = (1k1 ) · γ falls into one of these categories, with γ not starting with a part of length 1 and k1 ∈ N. Lemma 2.1.8 dictates that we must fill the rest of the shape before any of the rows of length 1 are filled; consequently, the entries in the rows of length 1 are the same for every SCT of shape α, and (1k1 ) · γ has multiplicity exactly when γ 19 2.2. Results for partition and reverse partition shapes has multiplicity. It is easy to verify computationally that there is no multiplicity in the possibilities for the bottom part γ, so the whole shape is multiplicity-free. We now show that all other compositions of reverse partition shape have multiplicity. Theorem 2.2.1 has already classified the rectangle shapes (mk ) for all m, k ∈ N. The composition (24 , 3) has multiplicity from the two tableaux 3 2 3 2 4 1 6 5 6 5 , and 7 4 9 7 9 1 11 10 8 11 10 8 with descent set {1, 3, 4, 6, 7, 9}. The composition (2, 2, 3, 3) has multiplicity from the two tableaux 3 2 4 1 8 6 5 10 9 7 , and 3 2 6 1 8 7 5 10 9 4 with descent set {1, 3, 4, 6, 8}. The composition (2, 2, 3, 4) has multiplicity from the two tableaux 3 2 4 1 8 6 , and 5 11 10 9 7 3 2 6 1 8 7 4 11 10 9 5 with descent set {1, 3, 4, 6, 8}. The composition (2, 2, 4) has multiplicity from the two tableaux 3 1 3 2 5 4 , and 5 1 8 7 8 7 6 2 6 4 with descent set {1, 3, 5}, which extend to give multiplicity in (2, 2, m), (3, 3, m) and (4, 4, m) for m ≥ 4 by first adding boxes in the bottom row and then filling the rest of the shape. In particular, (3, 3, 4) and (4, 4, 5) have multiplicity. 20 2.2. Results for partition and reverse partition shapes The composition (1, 3, 3) has multiplicity from the two tableaux 3 1 5 3 2 , and 5 4 2 7 6 4 6 1 7 with descent set {1, 3, 5}. The composition (1, 3, 4) has multiplicity from the two tableaux 1 3 5 3 2 8 7 6 , and 5 4 1 8 7 6 4 2 which extend to give the descent set {1, 3, 5, 7} with multiplicity in (1, 4, 5) by next filling the last box in the bottom row and then the last box in the second row. These two fillings of (1, 4, 5) then extend to give the descent set {1, 2, 4, 6, 8} with multiplicity in (2, 4, 5) and the descent set {2, 3, 5, 7, 9} in (3, 4, 5). The composition (1, 4, 4) has multiplicity from the two tableaux 5 2 7 5 4 3 , and 7 6 4 3 9 8 6 1 8 2 1 9 with descent set {2, 5, 7}, which extend to give multiplicity in (2, 4, 4) and (3, 4, 4). The composition (k, m) has multiplicity for m > k + 1 ≥ 4: Row-fill the subdiagram (k − 3, m − 2), and fill the remaining subdiagram with the pair 5 2 1 ... 4 3 , and 5 4 2 ... 3 1 Lastly, the composition (m, m + 1) has multiplicity for m ≥ 5: Row-fill the subdiagram (m − 5, m − 2), and fill the remaining subdiagram with the pair 8 5 4 2 1 7 6 3 , and 8 7 5 2 1 6 4 3 All other reverse partition shapes are concatenations of the cases we have covered, so by Lemma 2.1.5 we are done. 21 2.3. Multiplicity-free compositions with no parts of length one 2.3 Multiplicity-free compositions with no parts of length one Lemma 2.1.9 tells us that when appending a staircase-like shape β to a composition α, the resulting composition will be multiplicity-free if and only if α and β are both multiplicity-free. If we can establish a complete list of compositions that do not split up as a concatenation α · β with β a staircase-like shape, then a classification of all multiplicity-free compositions directly follows. Even when the appended shape β is not staircase-like, the situation tends to remain somewhat well-controlled if β happens to start with some number of rows of length 1. We first start with a list of compositions where there are no such rows. As one might expect from the classification of partition and reverse-partition shapes, the number of parts remains very restricted. In fact, very few new shapes arise: Theorem 2.3.1. Multiplicity-free compositions that don’t contain a part of length 1 are: For m ≥ 2, (i) (2, m), (ii) (m, 2k2 ) with 0 ≤ k2 ≤ 3, (iii) (m, 2, 3), (m, 2, 2, 3), (iv) (m, 3), and the special cases (v) (2, 3, 2), (2, 3, 2, 2), (2, 3, 2, 3), (2, 3, 3), (2, 3, 4), (vi) (3, 4), (vii) (4, 4), and (4, 5). We must first show that compositions (m, 2, 3), (m, 2, 2, 3) are multiplicity-free. The rest of the compositions in this list have already been dealt with in Theorems 2.2.1 and 2.2.7, with the exception of the cases of (2, 3, 2), (2, 3, 2, 2), and (2, 3, 2, 3), which can be verified computationally. Lemma 2.3.2. (m, 2, 3) is multiplicity-free for m ≥ 2. Proof. We have already seen that (2, 2, 3) is multiplicity free in Theorem 2.2.7, so assume m ≥ 3. The first two boxes in the third row must be filled before anything else. We divide up the possible SCTs into categories based on how much of the rest of the diagram is filled before the last box in this row: 22 2.3. Multiplicity-free compositions with no parts of length one • If we start by row-filling the subdiagram (0, 0, 3), then m + 2 is a descent, while m + 3 is not. • If we start by row-filling the subdiagram (0, 1, 2) and then fill the last box in the bottom row, m + 3 is a descent, while m + 2 is not. • If we start by row-filling the subdiagram (1, 1, 2) and then fill the last box in the bottom row, m + 2 and m + 3 are descents, while m + 1 is not. The next box filled is necessarily m in position (1, 2), which is also a descent. • If we start by row-filling the subdiagram (k, 1, 2) for some 3 ≤ k ≤ m and then fill the last box in the bottom row, then m + 2 and m + 3 are descents, while m in position (1, 3) is not. Any two fillings that belong to different categories clearly have distinct descents. Furthermore, each of the fillings within one of these categories has a distinct descent set; this follows from simply observing that the part of the diagram not yet filled is a subdiagram of (m, 2, 0), which is known to be multiplicity-free from Theorem 2.2.1. Lemma 2.3.3. (m, 2, 2, 3) is multiplicity-free for m ≥ 2. Proof. This is very similar to the last lemma. We have already seen that (2, 2, 2, 3) is multiplicity-free in Theorem 2.2.7, so assume m ≥ 3. The first two boxes in the fourth row must be filled before anything else. We divide up the possible SCTs into categories based on how much of the rest of the diagram is filled before the last box in this row: • If we start by row-filling the subdiagram (0, 0, 0, 3), then m + 4 is a descent, while m + 5 is not. • If we start by row-filling the subdiagram (0, 0, 1, 2) and then fill the last box in the bottom row, m + 5 is a descent, while m + 4 is not. • If we start by row-filling the subdiagram (0, 1, 1, 2) and then fill the last box in the bottom row, m + 4 and m + 5 are descents, while m + 3 is not. • If we start by row-filling the subdiagram (1, 1, 1, 2) and then fill the last box in the bottom row, then m + 3, m + 4 and m + 5 are descents in the first column. The next box filled is necessarily m + 1 in position (1, 2), which is also a descent. 23 2.3. Multiplicity-free compositions with no parts of length one • If we start by row-filling the subdiagram (k, 1, 1, 2) for some 3 ≤ k ≤ m and then fill the last box in the bottom row, m + 3, m + 4 and m + 5 are descents, while m + 1 in position (1, 3) is not. Any two fillings that belong to different categories clearly have distinct descents. Furthermore, each of the fillings within one of these categories has a distinct descent set; this follows from simply observing that the part of the diagram not yet filled is a subdiagram of (m, 2, 2, 0), which is known to be multiplicity-free from Theorem 2.2.1. We can now prove the theorem: Proof of Theorem 2.3.1. The strategy here is to use the classification of partition and reverse-partition shapes: The only way to get new multiplicity-free compositions not containing 1 beyond those listed in Theorems 2.2.1 and 2.2.7 is to append or prepend parts to these shapes, since a new multiplicity-free composition would have to extend a multiplicity-free composition with two parts, all of which are part of this list. We only have to check the small number of cases where both the leading and trailing lists are multiplicity-free, and in all cases except appending and prepending parts to the composition (2, 3), it turns out that we cannot extend beyond the known multiplicity-free compositions from Theorems 2.2.1 and 2.2.7. Appending and prepending parts to the composition (2, 3) results in the list of multiplicity-free compositions above. The only possible way to get new multiplicity-free compositions beyond this list is again by appending or prepending parts, and at this stage, nothing new can be generated. We verify this now. Appending parts to (2, m): If m ≥ 5, Theorem 2.2.1 gives that (m, k) is multiplicity-free only for k = 2 or 3. The situation for m = 2 is covered in the next case. For m = 3, (3, k) has multiplicity for k ≥ 5 from Theorem 2.2.7, and we have that (2, 3, 2), (2, 3, 3) and (2, 3, 4) are multiplicity-free. For m = 4 we have that (4, 4) and (4, 5) are multiplicity-free as well, but (2, 4, 4) and (2, 4, 5) are known to have multiplicity from Theorem 2.2.7. For (2, m, 2) with m ≥ 4, first row-fill the shape (0, m − 2, 1) and then fill the remaining subdiagram with the pair of tableaux 2 1 4 ... 5 4 3 ... 5 3 , and 1 2 24 2.3. Multiplicity-free compositions with no parts of length one to get two SCTs with descent set {2, 4, m + 3}. For (2, m, 3) with m ≥ 4, first row-fill the shape (0, m − 1, 1) and then fill the remaining subdiagram with the pair of tableaux 3 1 3 1 . . . 4 , and 5 ... 2 2 5 4 which both give descent set {1, 3, 5, m + 4}. Prepending parts to (2, m): The compositions (k, 2, 2) and (k, 2, 3) are multiplicity-free for k ≥ 2 from Theorem 2.2.1 and Lemma 2.3.2, while multiplicity in (2, 2, m) with m ≥ 4 was demonstrated in the classification of partition shapes in Theorem 2.2.7. The pair of tableaux 3 1 3 2 5 4 , and 5 1 8 7 8 7 6 2 6 4 extend to demonstrate multiplicity in (k, 2, m) for k ≥ 2. Appending parts to (m, 2k2 ), 0 ≤ k2 ≤ 3: Since all two part compositions have been dealt with in Theorems 2.2.1 and 2.2.7, we only need to consider the case 1 ≤ k2 ≤ 3. As above, we have multiplicity in (m, 2, k) for m ≥ 2, k ≥ 4, while (m, 2, 2) and (m, 2, 3) are multiplicity-free. The composition (2, 2, k) has multiplicity for k ≥ 4 from Theorem 2.2.7, so (m, 2, 2, k) and (m, 2, 2, 2, k) do as well by Lemma 2.1.5, while (m, 2, 2, 3) is multiplicityfree by Lemma 2.3.3. Multiplicity in (m, 2, 2, 2, 2) was demonstrated in Theorem 2.2.1. The composition (2, 2, 2, 2, 3) has multiplicity from the two SCTs 3 2 3 2 4 1 6 5 6 5 , and 7 4 9 7 9 1 11 10 8 11 10 8 25 2.3. Multiplicity-free compositions with no parts of length one with descent set {1, 3, 4, 6, 7, 9}. These extend to give multiplicity in (m, 2, 2, 2, 3) for m ≥ 2. Prepending parts to (m, 2k2 ), k2 ≤ 3: Since all two part compositions have been dealt with in Theorems 2.2.1 and 2.2.7, we only need to consider the case 1 ≤ k2 ≤ 3. Prepending 2 to (m, 2) for m ≥ 4 is taken care of by the multiplicity in (2, m, 2) above, while (2, 2, 2) and (2, 3, 2) are multiplicity-free. The composition (k, m) has multiplicity for k ≥ 3 and m > 5 from Theorems 2.2.1 and 2.2.7, so (k, m, 2) has multiplicity as well. The compositions (2, 3, 2) and (k, 2, 2) for k ≥ 2 are multiplicity-free, while (k, 3, 2) has multiplicity for k ≥ 3 from Theorem 2.2.1. We have the remaining special cases where m = 4 or 5, arising from the fact that (3, 4), (4, 4) and (4, 5) are multiplicity-free, but (3, 5) is not. The composition (3, 4, 2) has multiplicity from the two pairs of SCTs 5 3 2 5 4 1 8 7 6 4 , and 8 7 6 9 1 9 3 2 with descent set {1, 3, 5, 8}, and 4 2 1 6 4 1 8 7 5 3 , and 8 7 5 9 6 9 2 3 with descent set {2, 4, 6, 8}. The composition (4, 4, 2) has multiplicity from the classification of partition shapes in Theorem 2.2.1. The composition (4, 5, 2) has multiplicity from the pair of SCTs 6 5 3 2 10 9 8 7 11 1 6 5 4 1 4 , and 10 9 8 7 2 11 3 with descent set {1, 3, 6, 10}. Consequently, it follows that k for k ≥ 2 can’t be prepended to (m, 2, 2) or (m, 2, 2, 2) with m ≥ 4 either, while we have that (2, 3, 2, 2) and (k, 2, 2), (k, 2, 2, 2) for k ≥ 2 are multiplicity-free, but (k, 3, 2, 2) and (k, 3, 2, 2, 2) for k ≥ 3 are not 26 2.3. Multiplicity-free compositions with no parts of length one by Theorem 2.2.1. Multiplicity in (2, 3, 2, 2, 2) is demonstrated in the process of appending parts to (2, 3, 2, 2) below. Appending parts to (m, 3): For m = 2, (2, 3, k) is multiplicity free for 2 ≤ k ≤ 4. The only remaining case that hasn’t already been handled by Theorems 2.2.1 and 2.2.7 is appending 4 when m ≥ 4. The multiplicity in (3, 3, 4) from two SCTs 5 3 2 5 4 2 7 6 1 , and 7 3 1 10 9 8 10 9 8 4 6 extends to (m, 3, 4) for m ≥ 3. Prepending parts to (m, 3): The compositions (k, 2, 3) for k ≥ 2 and (2, 3, 3) are multiplicity-free, while (2, m, 3) has multiplicity for m ≥ 4 from the case of appending parts to (2, m). The composition (k, 3, 3) has multiplicity for k ≥ 3 from Theorem 2.2.1 and (3, 4, 3) has multiplicity from the two SCTs 5 3 1 5 3 2 8 7 6 2 , and 8 7 6 10 9 4 10 9 1 4 which extend to give multiplicity in (3, m, 3) for m ≥ 4, and hence (k, m, 3) for k ≥ 3 and m ≥ 4. Appending parts to (m, 2, 3) and (m, 2, 2, 3): The composition (2, 2, 3, 2) has multiplicity from the pair of tableaux 3 2 4 1 8 7 9 6 5 , and 3 2 6 4 8 7 9 1 5 27 2.3. Multiplicity-free compositions with no parts of length one with descent set {1, 3, 4, 6, 8}, which extends to give multiplicity in both (m, 2, 3, 2) and (m, 2, 2, 3, 2) for m ≥ 2. As in Theorem 2.2.7, the composition (2, 2, 3, 3) has multiplicity from the pair of tableaux 3 2 4 1 8 6 5 10 9 7 , and 3 2 6 1 8 7 5 10 9 4 which extends to give multiplicity in both (m, 2, 3, 3) and (m, 2, 2, 3, 3) for m ≥ 2. As in Theorem 2.2.7, the composition (2, 2, 3, 4) has multiplicity from the pair of tableaux 3 2 4 1 8 6 , and 5 11 10 9 7 3 2 6 1 8 7 4 11 10 9 5 which extends to give multiplicity in both (m, 2, 3, 4) and (m, 2, 2, 3, 4) for m ≥ 2. From Theorem 2.2.7, (2, 3, k) has multiplicity for k ≥ 5, so (m, 2, 3, k) for m ≥ 2 does as well. Prepending parts to (m, 2, 3) and (m, 2, 2, 3): As above, (k, m, 2) has multiplicity for k ≥ 2 and m ≥ 4, while for m = 3, the composition (2, 3, 2) is multiplicity-free, and (k, 3, 2) has multiplicity for k ≥ 3 from Theorem 2.2.1. The case m = 2 has been covered in appending parts to (m, 2k2 ). Appending and prepending parts to (2, 3, 2): The composition (3, 2, m) has multiplicity for m ≥ 4, so (2, 3, 2, m) does as well, while (2, 3, 2, 2) and (2, 3, 2, 3) are multiplicity-free. The composition (m, 2, 3, 2) has multiplicity for m ≥ 2 as in the case of appending parts to (m, 2, 3). 28 2.3. Multiplicity-free compositions with no parts of length one Appending and prepending parts to (2, 3, 2, 2): The composition (2, 2, k) has multiplicity for k ≥ 4 from Theorem 2.2.7, so (2, 3, 2, 2, k) does as well. The composition (2, 3, 2, 2, 2) has multiplicity from the pair of tableaux 3 1 5 4 7 6 2 3 2 7 6 , and 8 5 10 9 10 9 11 8 11 1 4 with descent set {1, 3, 5, 7, 8, 10}. The composition (2, 3, 2, 2, 3) has multiplicity from the pair of tableaux 3 1 5 4 7 6 2 3 2 7 6 , and 8 5 4 10 8 10 1 12 11 9 12 11 9 with descent set {1, 3, 5, 7, 8, 10}. From the case of appending parts to (m, 2, 3), we know that nothing can be prepended to (2, 3, 2, 2). Appending and prepending parts to (2, 3, 2, 3): As in the case of appending parts to (m, 2, 3), the composition (m, 2, 3, k) has multiplicity for m ≥ 2 and k ≥ 2, so nothing can be appended or prepended here. Appending and prepending parts to (2, 3, 3): From the case of appending parts to (m, 2, 3), we know that nothing can be prepended here. From Theorems 2.2.1 and 2.2.7, (3, 3, k) has multiplicity for k ≥ 2, so nothing can be appended either. 29 2.3. Multiplicity-free compositions with no parts of length one Appending and prepending parts to (3, 4): From Theorem 2.2.7, the only parts that can be appended to (4) are (2), (3), (4) and (5). The compositions (3, 4, 2) and (3, 4, 3) have multiplicity as above, and the compositions (3, 4, 4) and (3, 4, 5) have multiplicity from Theorem 2.2.7. From the case of appending parts to (m, 3), we know that nothing except (2) can be prepended to (3, 4). Appending and prepending parts to (2, 3, 4): (2, 3, 4, 2) and (2, 3, 4, 3) inherit multiplicity from (3, 4, 2) and (3, 4, 3), and the other possibilities for appending parts are covered by Theorem 2.2.7. The composition (2, 2, 3, 4) has multiplicity from Theorem 2.2.7. There are two pairs of tableaux contributing multiplicity to (3, 2, 3, 4), one of which is 4 3 5 1 9 7 2 6 , and 12 11 10 8 4 3 7 1 9 8 2 5 12 11 10 6 with descent set {1, 4, 5, 7, 9}, which extends to give multiplicity in (m, 2, 3, 4) for m ≥ 3. Appending and prepending parts to (4, 4): From Theorems 2.2.1 and 2.2.7, we know that no parts can be appended or prepended. Appending and prepending parts to (4, 5): Theorem 2.2.7 gives that (m, 4, 5) has multiplicity for m ≤ 4 and (5, k) has multiplicity for k ≥ 5. Theorem 2.2.1 gives that (m, 4) has multiplicity for m > 4, so (5, 4) has multiplicity. We have already seen that the remaining cases (4, 5, 2) and (4, 5, 3) have multiplicity in the case of prepending parts to (m, 2) and (m, 3). We have now exhausted all of the possibilities for appending and prepending parts to the compositions listed. The first step in seeing how these can be extended is to eliminate the compositions that have multiplicity when prepended with a part of length 1: Lemma 2.3.4. If α is one of the compositions 30 2.4. Conjectured classification of multiplicity-free compositions (i) (m, 3) for m ≥ 3, (ii) (3, 4), (4, 4) or (4, 5), then (1) · α has multiplicity. Proof. As in Theorem 2.2.7, the composition (1, 3, 3) has multiplicity from the pair of tableaux 1 3 5 3 2 , and 5 4 2 7 6 4 6 1 7 which extend to give multiplicity in (1, m, 3) by filling in the rest of the second row. We know that the compositions (1, 3, 4), (1, 4, 4) and (1, 4, 5) have multiplicity from Theorem 2.2.7 as well. 2.4 Conjectured classification of multiplicity-free compositions We finish our discussion with some conjectures that, if true, would hopefully complete our classification of multiplicity-free compositions. For the most part, these should not be especially difficult to verify, but exhausting each case would be quite time-consuming. 2.4.1 Multiplicity-free compositions without a trailing staircase-like shape We give a conjectured classification of compositions not of the form α · β with β staircase-like. If β is not one of the compositions in Lemma 2.3.4, there is the possibility of extending a multiplicity-free composition listed in Theorem 2.3.1 by appending (1k1 ) · β for some k1 ∈ N. Ignoring the staircase-like shapes, which are always appendable from Lemma 2.1.9, we now list which of these extensions are believed to be viable: Conjecture 2.4.1. Let α be a multiplicity-free composition not having a part of length 1, as in Theorem 2.3.1, and let k1 ∈ N. Then we have the following: (i) α · (1k1 ) · (3, 2k2 ) is multiplicity-free for 0 ≤ k2 ≤ 2 if α = (m, 2, 2) for some m ≥ 2, and multiplicity-free for 0 ≤ k2 ≤ 3 if α = (2, 3, 2), (m), or (m, 2) for some m ≥ 2. 31 2.4. Conjectured classification of multiplicity-free compositions (ii) α · (1k1 ) · (3, 2, 3) is multiplicity-free for 0 ≤ k2 ≤ 2 if α = (2, 3, 2k2 ) or (m, 2k2 ) for some 0 ≤ k2 ≤ 2, m ≥ 2. (iii) α · (1k1 ) · (3, 2, 2, 3) is multiplicity-free if α = (2, 3), (m) or (m, 2) for some m ≥ 2. (iv) α ·(1k1 )·(4, 2k2 ) is multiplicity-free for 0 ≤ k2 ≤ 2 if α = (2), and multiplicityfree for 0 ≤ k2 ≤ 3 if α = (3), (4) or (5). (v) α · (1k1 ) · (5, 2k2 ) is multiplicity-free for 0 ≤ k2 ≤ 2 if α = (2) or (4). (vi) α · (1k1 ) · (m, 2k2 ) for m ≥ 6 is multiplicity-free for 0 ≤ k2 ≤ 2 if α = (2). (vii) α · (1k1 ) · (2, 4) is multiplicity-free if α = (2, 3) or (m) for some m ≥ 2. (viii) α · (1k1 ) · (2, 5) is multiplicity-free if α = (m) for some m ≥ 4. These compositions in this list are the only multiplicity-free compositions of the form α · (1k1 ) · β for some k1 ∈ N with α and β not containing a part of length 1. Remark 2.4.2. For small values of k1 , this conjecture has been verified by computation. It may be the case that the result follows from verifying the conjecture for k1 = 1; see Conjecture 2.4.8. If this conjecture is true, we see the curious phenomenon that for most multiplicityfree compositions of the form α · (1k1 ) · β with α and β not containing a part of length 1, the only compositions that can be appended to β without introducing multiplicity are of the form (3, 2k2 ) with k2 ≤ 3 or (3, 2k2 , 3) with k2 ≤ 2. The exceptions to this are the when β = (2), (3), (4) or (5). It turns out that the latter three cases are easy to deal with: Lemma 2.4.3. Let e1 , e2 , . . . , en ∈ N, and α = (1e1 , 2, 1e2 , 2, . . . , 1en ). We have that (i) (1, m, 1e1 , k) has multiplicity for m, k ≥ 3, (ii) (1, m) · α · (k) has multiplicity for m ≥ 3, k ≥ 4, and (iii) (1, m) · α · (2, k) has multiplicity for m ≥ 3, k ≥ 4. Proof. For (1, 3, 1e1 , 3), use the pair of fillings 1 5 .. . 3 3 2 4 , and 5 .. . 4 2 1 32 2.4. Conjectured classification of multiplicity-free compositions after building the rest of the shape in row order. This multiplicity then extends to (1, m, 1e1 , 3). For (1, 3, 1e1 ,4), (1, 3) · α · (4) and (1, 3) · α · (2, 4), use the pair of fillings 1 5 .. . 3 3 2 , and 4 5 .. . 4 1 2 after building the rest of the shape in row order. This filling extends to give our result by building the remaining subdiagram in row order. Much more can happen through appending parts after (1, 2), owing to the fact that compositions of the form (1e1 , 2, 1e2 , 2, 1e3 , . . . , 1e ) with e1 , e2 , . . . , e ∈ N have only one possible filling and thus serve largely the same role as (1k1 ): Conjecture 2.4.4. Let α be a multiplicity-free composition not having a part of length 1. Then for any e1 , e2 , . . . , e ∈ N, we have: (i) α · (1e1 , 2, 1e2 , 2, 1e3 , . . . , 1e , 4, 2k2 ) is multiplicity-free only if α = (2), (3), (4) or (5), in which case it is multiplicity-free if and only if 0 ≤ k2 ≤ 2. (ii) α · (1e1 , 2, 1e2 , 2, 1e3 , . . . , 1e , 5, 2k2 ) is multiplicity-free only if α = (2) or (4), in which case it is multiplicity-free if and only if 0 ≤ k2 ≤ 2. (iii) α · (1e1 , 2, 1e2 , 2, 1e3 , . . . , 1e , 2, 4) is multiplicity-free if and only if α = (2, 3) or (m) for some m ≥ 2. (iv) α · (1e1 , 2, 1e2 , 2, 1e3 , . . . , 1e , 2, 5) is multiplicity-free if and only if α = (m) for some m ≥ 4. Remark 2.4.5. Demonstrating multiplicity for the only if part is not especially difficult, but verifying that the compositions listed are multiplicity-free in general would be fairly tedious. The next conjecture would essentially finish the classification: Conjecture 2.4.6. Let α be a multiplicity-free composition and e1 , e2 ∈ N. Suppose that α · (1e1 , m, 2) is multiplicity-free for some m ≥ 3. Then we have that the following compositions are multiplicity-free: (i) α · (1e1 , m, 2, 1e2 , 3, 2, 2, 2), (ii) α · (1e1 , m, 2, 2, 1e2 , 3, 2, 2), 33 2.4. Conjectured classification of multiplicity-free compositions (iii) α · (1e1 , m, 2, 1e2 , 3, 2, 3), (iv) α · (1e1 , m, 2, 2, 1e2 , 3, 2, 3). Remark 2.4.7. This conjecture is suggested by the (computationally verified) fact that (1, 3, 2, 2) can be appended at least twice to any of the compositions in Theorem 2.3.1 satisfying the condition of the conjecture. Being able to append this shape indefinitely is expected based on how close to staircase-like it is: when the row of length 1 is filled, all lower rows must be filled with the exception of the last box in the row of length 3. An explicit proof of this would require a level of detail beyond our current scope. If it turns out that this shape cannot be appended indefinitely, discovering how many times it can be appended would serve the same purpose in classifying multiplicity-free compositions. If Conjectures 2.4.1, 2.4.4 and 2.4.6 are true, it seems that we would now have the structure of multiplicity-free compositions in hand: Conjecture 2.4.1 gives an initial classification for when two multiplicity-free compositions α and β have a multiplicity-free concatenation α · (1k1 ) · β . In most cases, the only way to continue appending parts is with (3, 2, 2, 2), (3, 2, 2, 3), (3, 2, 3) or some truncation of one of these three compositions. Lemma 2.4.3 and Conjecture 2.4.4 suggest what can happen in the case when β = (n) with 2 ≤ n ≤ 5. Conjecture 2.4.6 would give that if a multiplicity-free composition γ ends with (1, m, 2) or (1, m, 2, 2), then (1e1 , 3, 2) or (1e1 , 3, 2, 2) can be appended to γ ad infinitum as follows: We have that γ = α · (1, m, 2) or γ = α · (1, m, 2, 2) for some multiplicity-free composition α. In either case, by Lemma 2.1.5, the composition α · (1, m, 2) is multiplicity-free, so we are in the situation of Conjecture 2.4.6. We can then conclude that the compositions listed there are multiplicity-free; in particular, this means that γ · (1e1 ) · β is multiplicity-free for β = (3, 2) and (3, 2, 2) from Lemma 2.1.5. Repeating the process with γ · (1e1 ) · β in place of γ allows (1, 3, 2) or (1, 3, 2, 2) to be appended indefinitely. We would also implicitly have a classification of when the only way to extend a multiplicity-free composition is by appending a staircase-like shape. 2.4.2 Conjecture on inserting parts in the middle of a composition If the classification of multiplicity-free compositions in Section 2.4.1 is correct, we have the interesting consequence that replacing a part of length 1 with several parts of length 1 does not change whether a composition has multiplicity. We record this as a conjecture: 34 2.4. Conjectured classification of multiplicity-free compositions Conjecture 2.4.8. Let α and β be any compositions, and k1 ∈ N. Then α · (1) · β has multiplicity if and only if α · (1k1 ) · β has multiplicity. This was used as a heuristic to formulate the results in Sections 2.2 and 2.3, and has been easy to verify for many instances of α and β , but finding a simple proof in general seems troublesome. It seems that to extend multiplicity in α · (1) · β to multiplicity in α · (1, 1) · β , the strategy is to view a pair of SCTs with the same descent set as sequences of the operations of either prepending a new part of length 1 or adding a box to the end of the first part of length k for some k. In both sequences, insert an extra operation of prepending a part of length 1 just before the first box of the prepending part α would be added. Now both sequences build α · (1, 1) · β , and translating back to tableaux, these seem to give the same descent set for all cases that have been examined. If this can be verified, this part of the conjecture would follow by induction. Conversely, if α · (1, 1) · β has multiplicity from a pair of SCTs T1 and T2 , all cases examined show that the set of entries contained in the (0|α| , 1, 1, 0|β | ) subdiagram in T1 and the set of entries contained in the same subdiagram of T2 have at least one entry i in common. To project down to multiplicity in α · (1) · β , view T1 and T2 as sequences of operations and simply remove the operation that would have added the box containing i. If Conjecture 2.4.8 can be proven independently of the conjectures in Section 2.4.1, it would eliminate the main obstacle of extreme tedium involved in verifying the classification of multiplicity-free compositions. 35 Bibliography [1] Christine Bessenrodt. On Multiplicity-Free Products of Schur P-Functions. Annals of Combinatorics, 6:119–124, 2002. [2] Christine Bessenrodt, Kurt Luoto, and Stephanie van Willigenburg. Skew quasisymmetric Schur functions and noncommutative Schur functions. Advances in Mathematics, 226:4492–4532, 2011. [3] Christine Bessenrodt and Stephanie van Willigenburg. Multiplicity free Schur, skew Schur, and quasisymmetric Schur functions. Pre-print. To appear in Annals of Combinatorics., 2012. http://arxiv.org/abs/1105.4212v2. [4] Christian Gutschwager. On multiplicity-free skew characters and the Schubert Calculus. Annals of Combinatorics, 14:339–353, 2010. [5] James Haglund, Kurt Luoto, Sarah Mason, and Stephanie van Willigenburg. Quasisymmetric Schur functions. Journal of Combinatioral Theory, Series A 118:463–490, 2011. [6] Roger Howe. Perspectives on invariant theory: Schur duality, multiplicityfree actions and beyond: The Schur lectures. Israel Mathematics Conference Proceedings, 8:1–182, 1995. [7] Kristin Shaw and Stephanie van Willigenburg. Multiplicity Free Expansions of Schur P-Functions. Annals of Combinatorics, 11:69–77, 2007. [8] Richard P. Stanley. Symmetries of plane partitions. Journal of Combinatioral Theory, Series A 43:103–113, 1986. [9] John Stembridge. Multiplicity-Free Products of Schur Functions. Annals of Combinatorics, 5:113–121, 2001. [10] Hugh Thomas and Alexander Yong. Multiplicity-Free Schubert Calculus. Canadian Math Bulletin, 53:171–186, 2010. 36
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Towards a classification of descent multiplicity-free...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Towards a classification of descent multiplicity-free compositions Cheek, Caleb 2012
pdf
Page Metadata
Item Metadata
Title | Towards a classification of descent multiplicity-free compositions |
Creator |
Cheek, Caleb |
Publisher | University of British Columbia |
Date Issued | 2012 |
Description | This work studies combinatorics related to expansions of a quasisymmetric refinement of Schur functions into Gessel’s fundamental basis, with almost all results concerning whether an expansion is multiplicity-free. The combinatorial side of this problem concerns a certain composition poset, and whether there are two standard fillings of the same composition diagram with a given descent set. This thesis uses entirely combinatorial arguments, extending results by Bessenrodt and vanWilligenburg to work towards a classification of such descent multiplicity-free compositions. The main tools used regard the situation of appending or prepending parts to compositions. Compositions with multiplicity retain multiplicity when parts are appended or prepended, while multiplicity-free compositions stay multiplicity-free when a class of shapes called staircase-like are appended. A classification of compositions which are partitions or reverse partitions is achieved, leading up to a classification of compositions not containing a part of length one. This is used as the basis for a conjectured classification of multiplicity-free compositions without a trailing staircase. The conjecture would in turn imply a complete classification of multiplicity-free compositions. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-08-30 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-ShareAlike 3.0 Unported |
DOI | 10.14288/1.0073090 |
URI | http://hdl.handle.net/2429/43094 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2012-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-sa/3.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2012_fall_cheek_caleb.pdf [ 218.85kB ]
- Metadata
- JSON: 24-1.0073090.json
- JSON-LD: 24-1.0073090-ld.json
- RDF/XML (Pretty): 24-1.0073090-rdf.xml
- RDF/JSON: 24-1.0073090-rdf.json
- Turtle: 24-1.0073090-turtle.txt
- N-Triples: 24-1.0073090-rdf-ntriples.txt
- Original Record: 24-1.0073090-source.json
- Full Text
- 24-1.0073090-fulltext.txt
- Citation
- 24-1.0073090.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}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0073090/manifest