Schur-Positivity of Differences of Augmented Staircase Diagrams by Matthew Morin B.Sc., Simon Fraser University, 2003 M. Sc., University of British Columbia, 2005 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Doctor of Philosophy in The Faculty of Graduate Studies (Mathematics) The University of British Columbia (Vancouver) April 2010 © Matthew Morin 2010 Abstract The Schur functions {s} and ubiquitous Littlewood-Richardson coefficients c are instrumental in describing representation theory, symmetric functions, and even certain areas of algebraic geometry. Determining when two skew diagrams D , D 1 2 have the same skew Schur function or determining when the difference of two such skew Schur functions SD 1 2 is Schur-positive D 5 reveals information about the structures corresponding to these functions. By defining a set of staircase diagrams that we can augment with other (skew) diagrams, we discover collections of skew diagrams for which the ques tion of Schur-positivity among each difference can be resolved. Furthermore, for certain Schur-positive differences we give explicit formulas for computing the coefficients of the Schur functions in the difference. We extend from simple staircases to fat staircases, and carry on to dia grams called sums of fat staircases. These sums of fat staircases can also be augmented with other (skew) diagrams to obtain many instances of Schur positivity. We note that several of our Schur-positive differences become equalities of skew Schur functions when the number of variables is reduced. Finally, we give a factoring identity which allows one to obtain many of the non-trivial finite-variable equalities of skew Schur functions. — 11 Contents ii Abstract Table of Contents iii Acknowledgements v 1 Introduction 1 1.1 Partitions, Compositions, Ferrers Diagrams, and Skew Diagrams 1 1.2 Combining and Decomposing Diagrams 4 Tableaux 1.3 5 1.4 Symmetric Functions 6 1.5 The Littlewood-Richardson Rule 9 Identities for Schur Functions 10 1.6 Some Useful 12 1.7 A Brief History of Schur Functions 15 1.8 Overview of Schur-Positivity Results 2 Staircases with Bad Foundations 2.1 Regular Staircases 2.2 Fat Staircases 2.3 Sums of Fat Staircases 23 23 27 33 3 Hook Foundations 3.1 Schur Comparability / Incomparability 3.2 Expressions for Schur-Positive Differences 3.3 Hasse Diagrams for k> 1 43 43 60 73 Differences of Transposed Foundations 4.1 Single Part Partitions 4.2 Two Part Partitions 91 91 95 . 4 111 5 Complements in a Rectangle 5.1 Preliminaries 5.2 Staircases with Hook Complement Foundations 5.3 Sums of Fat Staircases 5.4 Miscellaneous Results 111 111 116 123 128 6 Reduction to Finite Variables 6.1 Differences of Transposed Foundations 6.2 Factoring in Finite Variables 133 133 136 7 Conclusion 144 Bibliography 146 . iv Acknowledgements I would like to thank my supervisor, Stephanie van Willigenburg, for her con tinual support, her remarkable ability to neatly turn a problem on its head, and her constant and vigilant attention to detail. Without her guidance, this thesis would be naught but a work-in-progress. I would also like to show my gratitude to all members of my thesis com mittee for accepting the responsibility of judging my dissertation. The will ingness to spend the time and effort for this endeavor is much appreciated. Financial credit must be given to NSERC for funding the past three years of my doctoral program. Life would have been much more difficult without the scholarship they generously awarded me. More thanks are due to UBC, for their support throughout my entire years of study and the many opportunities they have granted. The entire staff of the Mathematics department deserves praise for its ability to keep everything running smoothly and efficiently not just in the department as a whole, but down through each and every individual in the department. Finally, I must thank all my friends, family, and loved-ones for their non academic support. I could not be here now without your unwavering belief in myself and my abilities. Although you may not fully understand what it is I do, you have always shown pride in my desire to do it. V Chapter 1 Introduction 1.1 Partitions, Compositions, Ferrers Diagrams, and Skew Diagrams A partition A of a positive integer n, written A H n, is a sequence of weakly Ve call 1 A = n. \ ,A 1 , 2 decreasing positive integers A = (A , A,) with of length A is parts k and exactly we say k if A has each A 2 a part of A, and n and say that the size write 1(A) = k. When A I— n we will also write IA of A is n. j consisting of r j’s. Under We shall use jT to denote the sequence j, j ’k—1 7 1 , U’) for the partition = , k 1 (k this notation, we shall write A 2 parts of size two, ..., and rk parts of size k. 1 parts of size one, r which has r , . . . , A,) and p = (h,. . . , ,Lim), we let A U ,u 1 Given two partitions A = (A ,. 1 , .. . , A, /J 1 denote the partition that consists of the parts A , ltm placed order. weakly decreasing in ,.. . , ak) is a composition of n, written a = n, if each 2 ,a 1 We say a = (a 2 a = n. As with partitions, we call each a aj is a positive integer and a part of a, write a = n for the size of a, and if a has exactly k parts we say a is of length k and write 1(a) = k. If we relax the conditions to consider sums of non-negative integers, that is, allowing some of the a, to be zero, then we obtain the concept of a weak composition of n. If a = n we obtain a partition of n by reordering the a into weakly decreasing order. We may sometimes find it useful to treat partitions and weak composi tions as vectors with non-negative integer entries. VThen we write the vector ,. . . , z) we shall mean the infinite vector 3 ,z 1 ,z 2 z = (z — . . .). z ...,z,O,O,O,.. 3 1 z=(z , 2 , We shall only consider vectors with finitely many non-zero entries. Hence we 1 CHAPTER 1. INTRODUCTION shall oniy display vectors with finite length. In this manner we may unam biguously add vectors of different lengths. Thus, we have defined addition among partitions and weak-compositions. Further, given a positive integer i, we shall let e denote the i-th standard basis vector. That is, the vector that has its i-th entry equal to 1 and all remaining entries equal to 0. Given a partition A, we can represent it via the diagram of left justified rows of boxes whose i-th row contains A boxes. The diagrams of these type are called Ferrers diagrams, or just diagrams for short. We shall use the symbol A when refering to both the partition and its Ferrers diagram. Whenever we find a diagram D’ contained in a diagram D as a subset of boxes, we say that D’ is a subdiagram of D. Suppose partitions A .. .jtk) F-rn, with m < n, k <j, and ,ii 1 (t , A F-n and fL = 2 , 1 (A , 2 ...,A) A for each i = 1, 2,.. , k are given. Then t is a subdiagram of A, and a particular copy of is found at the top-left corner of A. We can form the skew diagram A/,u by removing that copy of p from A. Henceforth, when we say that D is a diagram, it is assumed that D is either the Ferrers diagram of some partition A, or D is the skew diagram A/j for some partitions A, ,u. . Example Here we consider the partitions A form the skew diagram A/si. [=iJr = (4, 4, 2) and = (3, 1), and H 2 1 to b 2 in a diagram D, we define a path from b 1 and b For two boxes b in D to be a sequence of steps either up, down, left, or right that begins at , and at no time leaves the diagram D. We say that a diagram 2 b, ends at b 1 and b 2 of D there is a path from b to D is connected if for any two boxes b 2 in D. If D is not connected we say it is disconnected. b Given any diagram D, the 1800 rotation of a diagram D is denoted by D°. Further, the conjugate or transpose diagram Dt is obtained by simply transposing the array of boxes along the main diagonal. When D is the Ferrers diagram of a partition A then the conjugate diagram Dt is also the Ferrers diagram of a partition called the conjugate partition and denoted At. It must be noted that most authors use the notation D’ and A’ for the conjugate diagram of D and conjugate partition of A. We hope our notation causes no confusion. 2 CHAPTER 1. INTRODUCTION Example Here we consider the partitions A i. 1 form the skew diagram A/ = (4, 4, 2) and i = (3, 1), and HH The conjugates, At shown below. = (3,3,2,2), = (2,1,1) and (A/ji)t ° ((A/j) ) Finally, we see the skew diagrams (A/i)° and t = = At/itt are ((A/)0)t. The number of boxes that appear in a given row or a given column of a diagram is called the length of that row or column. A hook is the Ferrers diagram corresponding to a partition A that satisfies A < 1 for all i > 1. Hence a hook has at most one row of length larger than 1. Example Here we see the hooks A = (4, 1, 1) and Li ‘A’ It 3 t = (5, 1). _ __ CHAPTER 1. INTRODUCTION 1.2 Combining and Decomposing Diagrams In this section we look at combining and decomposing skew diagrams in a few simple ways. 1 and D , denoted 2 1 and D 2 the concatenation of D Given two diagrams D 2 so that the top1 and D •D , is the skew diagram obtained by placing D 2 . Similarly, 2 right box of D 1 is immediately below the bottom-left box of D , denoted D 2 10D , is the skew diagram 2 1 and D the near-concatenation of D 1 is immediately 2 so that the top-right box of D obtained by placing D 1 and D . Finally, if the last column of D 2 1 and first left of the bottom-left box of D length i, then the near-concatenation of depth column of D 2 are both of , is the is the skew diagram obtained by 2 1 0D 1 and D , denoted D 2 i of D 1 is one step left and i 1 2 so that the top-right box of D placing D 1 and D . We note that 0 = 0. 2 steps up from the bottom-left box of D — 2 be the Ferrers 1 be the skew diagram (2, 2, 2)/(1, 1) and D Example Let D diagram (4,4,2). D 02 D D0D . 2 1 D , D 2 1 0D , 1 2 , and 1 2 Here we show the diagrams D I_ 1 02 D D 2 10D D 2 1 03 D D 2 Given a diagram D, the connected components of D are the maximally connected subdiagrams of D. Any skew diagram D decomposes into a finite ,D 1 ,. , D,. Conversely, given con 2 number of connected components D D, called ,D 1 ,. , Dk, we define the diagram D = 2 nected diagrams D the direct sum of the D, to be the skew diagram with connected components ,. , Dk such that the top-right box of D is one step left and one step 2 ,D 1 D 1 for i = 1, 2,. , k 1. We note that down from the bottom-left box of D =0o. . . . . . . . 4 . — CHAPTER 1. INTRODUCTION 2 1 = (2, 2, 2)/(1, 1) and D Example With D . 2 1 D example, we now show the diagram D = (4, 4, 2), as in the previous 2 1 D Tableaux 1.3 If D is a diagram, then a tableau—plural tableaux—T of shape D is the array obtained by filling the boxes of the D with the positive integers, where repetition is allowed. A tableau is said to be a semistandard Young tableau (or simply semistandard, for short) if each row gives a weakly increasing sequence of integers and each column gives a strictly increasing sequence of integers. We will often abbreviate “semistandard Young tableau” by SSYT and “semistandard Young tableaux” by SSYTx. When we wish to depict a certain tableau we will either show the under lying diagram with the entries residing in the boxes of the diagram or we may simply replace the boxes with the entries, so that the entries themselves depict the underlying shape of the tableau. The content of a tableau T is the weak composition given by v(T) where Vj = ...), u 2 , 1 (v , is the number of i’s that appear in T. Example Here we consider a semistandard Young tableau 7Ej with shape 1 = (2, 2, 2)/(1, 1) and content (1,0, 1, 2), and a semistandard Young tableau D 2 = (4,4,2) and content (2,2,3,2, 1). 7 of shape D 3 144 1124 2335 34 7 72 We may sometimes find it useful to take the transpose of a tableau T that we obtain a tableau of conjugate shape. In these cases we simply so transpose the entries of T along with the underlying shape D. In this way, we obtain a tableau 7 of shape Dt with c(Tt) = c(T). 5 CHAPTER 1. INTRODUCTION Similarly, given a tableau T of shape D, we may wish to focus on the entries of T that lie in some subdiagram D’ of D. In this way we obtain a 2 1 and D subtableau of shape D’. Also, given tableau 7j and 7 of shapes D 7j 1 D , 2 respectively, we may form the tableaux ‘Tj 7 of shape D 7 of 2 1 D , 2 D of shape of shape and 1 D 1 D , 7 07 2 shape D 7 O7 0 ® D 1 0D 2 is defined) in the obvious way. (when D Example For the SSYTx 7 and 7 in the previous example, we now create the tableaux 7 7, 7 0 7, 7 02 7, and 7 o 7. 1 2 3 1 1 2 4 2335 134 3 44 1124 12335 334 144 7i07 111124 323135 14434] 7037; 7027 Of these tableaux, only ‘Jj 0 7 and 7 02 7 are semistandard. 1.4 Symmetric Functions ,...) and the 2 In this section we consider an infinite set of variables x = (xi, x ring of formal power series C[x]. By S, we mean the group of permutations of the letters {1, 2,. , n}. ,...) C[xj by defining 2 ,x 1 We can let each ‘it E S act on elements f(x . . ,...) 2 X f(x(i), X(2),. . . X), n+1, Xn+2,. . (1.1) C[x] which are fixed ,...) 2 f(x x , We are interested in certain functions 1 by each ‘it e S, for every n E N. For instance, the n-th power symmetric function, pn(x) = j 1 is such a function. Two other functions with this property are the the n-th elementary symmetric function, e(x)= :: 2 xilxi . . xfl and the n-th homogeneous symmetric function, h(x)= 2 xilxi 6 Xi. CHAPTER 1. INTRODUCTION ,A) by the power symmetric function, Given a partition A = )2,. elementary symmetric function, and homogeneous symmetric function corre sponding to A, we shall mean Ho p(x) e(x) = 11ex, = and k h(x) Additionally, by the monomial symmetric function corresponding to A we mean m(x) = where the above sum is taken over all distinct monomial terms of the form x. We note that m()(x) p(x) and m(ln)(x) = e(x). • • • Each of p, e, h, and mA are invariant under the action described in Equation 1.1. Further, it turns out that each of the sets {p(x)j A I— n}, {eA(x) A I— n}, {hA(x)j A I— n}, and {mA(x) A I— n} are independent and span the same space of functions; that is, they are all bases of a common , is called the set of homogeneous symmetric 7 space. This space, denoted A functions of degree n and is usually defined as the span of the m, (x) for A F-n. For any tableau ‘T of content defined by xT ii = = ,...) we have the weight xT 2 (zi, v JJx”. Given this weight function, the Schur function corresponding to A is defined to be (1.2) s.x(x) = xT, where the sum is taken over all SSYTx ‘T of shape A. If Al = n, then sA(x) is a homogeneous symmetric function of degree n. As with the other symmetric functions, the set {sA(x) A F- n} is a basis of A. Further details can be found in [63]. 7 CHAPTER 1. INTRODUCTION to Finally, given a skew diagram A/ji, the skew Schur function corresponding )/i is x) s ( 1 = xT, (1.3) The skew Schur where the sum is taken over all SSYTx T of shape function sA/(x) is a homogeneous symmetric function of degree n = — Example For a single row = (n), the semistandard condition on a tableau of shape ) implies that the entries form a weakly increasing sequence. Thus we obtain s()(x) 2 xjx = h(x), = the n-th homogeneous symmetric function. For a single column t = (in), the semistandard condition on a tableau of shape ji implies that the entries form a strictly increasing sequence. Thus we obtain = S(in)(X) = en, il<I2<<in the n-th elementary symmetric function. ,i) (x). Thus we need 2 Example We wish to compute the Schur function S( 1). such a tableau and let Let = (2, of shape ) be SSYT inspect each to ‘T i, j, and k be the entries of T as shown below. Since the columns of T must strictly increase, we require <j. Thus since the rows of T weakly increase, we require i ,l)(X) 2 S( = that i < k, and, 4 XXjXi i<j, i<k = (xixxk) j i<k XiXjXk — j<i<k (xixk) = = j (x) e(l)(x)e( ) 2 8 — XXjXk — i<k j<i<k )(x). 3 e( CHAPTER 1. INTRODUCTION We note that when x is taken to be a finite set of variables (for example, when setting all x = 0 for each i > n), then sA(x) is often called a Schur polynomial. S’Ve shall henceforth drop reference to the variables x and just write sA in place of sA (x), and similarly with the other symmetric functions. 1.5 The Littlewood-Richardson Rule Since the set {sjA F— n} is a basis of A, any homogeneous symmetric func tion of degree n can be written as a unique linear combination of the sA. In particular, for any partitions p and v, ss (1.4) >csA, Al—n appear The coefficients where n = ji + v, for some coefficients in many other expressions (see Section 1.7) and are called the Littlewood Richardson coefficients. The Littlewood-Richardson coefficients also appear as the coefficients of the skew Schur function 5 A/p. That is, for any skew diagram A/u, sA/. (1.5) = where n = i-. In addition, the Littlewood-Richardson coefficients are non-negative integers and there is a certain collection of SSYTx that they count. Given a tableau T, the reading word of T is the sequence of integers obtained by reading the entries of the rows of T from right to left, proceeding ,r 1 ,. , is 2 from the top row to the bottom. We say that a sequence r = r lattice if, for each j, when reading the sequence from left to right the number of j’s that we have read is never less than the number of j+ l’s that we have read. — . . Theorem 1.5.1 (Littlewood-Richardson Rule) ([ 3]) is the For partitions A, , and ii, the Littlewood-Richardson coefficient number of SSYTx of shape A/i-i, content u, with lattice reading word. We note that the content of a tableau was defined as a weak composition, not a partition. Nevertheless, the lattice condition forces any tableau with lattice reading word to have a content that is in fact a partition. 9 ____ CHAPTER 1. INTRODUCTION Example Let us compute the skew Schur function S(4,3,2)/(2,2) by using Equa tion 1.5 and the Littlewood-Richardson rule. Thus we need to find all SSYTx (432) of shape (4, 3, 2)/(2, 2) with lattice reading word, then C( )v is the number 22 of these tableaux with content i’. We leave it to the reader to check that the following four tableaux are the only SSYTx of shape (4, 3, 2)/(2, 2) with lattice reading word. v= (4,1) Therefore S(4,3,2)/(2,2) 1j2 v= (3,2) = S(4,) + v= (3,1,1) ) 2 , 3 S( + 5(3,1,1) + v= (2,2,1) 5(2,2,1). For any f = aAs.X E A, we say that f is Schur-positive, and write > Further, we say that f is multiplicity-free if each 0. if each 0, aA f 1 aA E {0, 1}. Therefore, the Littlewood-Richardson rule shows that both s,s, and SA/ are Schur-positive. For f, g e A, we will be interested in whether or not the difference f — g is Schur positive. We shall write f > g whenever f — g is Schur-positive. If neither f — g nor g — f is Schur-positive we say that f and g are Schur-incomparable. Further, we will find it conveniellt to write D 1 2 if SD D 1 s 8 • 2 D If we consider the relation )— on the set of all Schur-equivalent classes defines a partial ordering. 3 = {D’sD = SD’}), then of diagrams (i.e. [D] on the set of This allows us to view the Hasse diagram for the relation these Schur-equivalent classes of skew diagrams. ‘- 1.6 Some Useful Identities for Schur Func tions In this section we list a few easy to state results that shall prove useful. The first two results are commonly know as Pieri rules. The origins of these result can be found in [54]. To state these two results we require the following two definitions. A row strip is a skew diagram with no two boxes in the same column and a column strip is a skew diagram with no two boxes in the same row. The Pieri rules can now be stated as follows. Theorem 1.6.1 We have SvS(n) = S) where the sum is over all partitions ) such that )/(v) is a row strip of size n. 10 CHAPTER 1. INTRODUCTION Theorem 1.6.2 We have SvS(ln) = where the sum is over all partitions ) such that A/(v) is a column strip of size n. The Pieri rules have been generalized in such work as [1], [5], and [52]. We now give two results that we shall use often. Theorem 1.6.3 [[69], Exercise 7.56(a)] Given a skew diagram D, = (1.6) D0. 5 A result on the Littlewood-Richardson coefficients of conjugate diagrams can be found in [30]. For products, we have the following identity. Theorem 1.6.4 The Schur function of any disconnected skew diagram is D then we have , 1 2 reducible. If D = D (1.7) = 1 D gives rise to a SSYT of shape D 1 and Proof Any SSYT of shape D 2 by taking the obvious subtableaux. Conversely, any a SSYT of shape D 1 and 7 of shape D 2 give rise to the tableau ‘Tj 7 of SSYTx 7 of shape D , which is clearly semistandard. 2 shape D 1 D • Lastly, we mention another expression for the product 2 1 D 5 Theorem 1.6.5 [[5], Chapter 1.5, Example 2.1 (a)] 1 and D , we have 2 For skew diagrams D SD = 5 1 SD 2 2 1 D + OD 1 D 5 2 (1.8) 1 and 7 of shape D 2 we let a be the Proof Given SSYTx 7j of shape D 1 and b be the entry of the bottom-left box entry of the top-right box of D < is If b then of D . 2 a Ti 0 7 a SSYT, and if a > b then Ti 7 is a SSYT, 1 0D 2 and D 1 D 2 arise in this fashion. and clearly all SSYTx of shape D . I 11 CHAPTER 1. INTRODUCTION A Brief History of Schur Functions 1.7 Schur polynomials and Schur functions have appeared in various mathemat ical contexts during the last two centuries. Their first definition was given in terms of certain bialternants. That is, as a quotient of alternants. Namely, u= ,. , tj), we may obtain the alternant 2 u given a composition 1 . a(xi,. . . ) 1 ,x . Ihir(1) 1 sgn(r)x = 1ir(l) . 1 rES , l}, and sgn(7r) is the 1 is the group of permutations of {1, 2, where the S partition of length 1 and using taking A Then, a sign of the permutation ir. 6 = (1 1, 1 2,. , 1, 0), the Schur polynomial can be defined as . — — . .. . aA+o These functions first appeared in a paper of Cauchy [15], dating 1815, in which he was able to prove that this rational function was in fact a polyno mial. The next noteworthy appearance of Schur functions is thanks to Jacobi [32] in 1841, in which the Schur functions were again defined as above and a form of the now-famous Jacobi-Trudy identity was given. This identity gives another method of computing s, and can be stated as follows. Theorem 1.7.1 Let A = ,A 1 (A , 2 s . . . , ), then 1 A = and 5t = where At is the conjugate of A and both determinants are I x 1. Throughout this time the Schur functions had not yet been given the name that we presently know them by. Issai Schur, born in 1875, also used the bialternant definition of S), in his dissertation [66]. However, his interest in Schur functions arose from their connection to the study of representation theory, a topic whose origins can be traced to a collection of papers by Frobenius [20, 21, 22] dating from 1896 to 1897. Although the definition of representations did not appear until Frobenius’ paper of 1897, his series of papers in 1896 introduced the character 12 CHAPTER 1. INTRODUCTION theory of finite groups, which is a fundamental aspect of represenation theory. Schur was one of Frobenius’ doctoral students, and he, together with notable others, furthered the development of representation theory and the theory of characters in his doctoral dissertation and in his subsequent work. In the study of characters of Sn-modules, there is a bijection taking the It was by this type of connection irreducible character xA to the function and homogeneous symmetric symmetric group of the between representations functions that Schur came to study the functions sA, which were later called Schur functions in his honour. For a detailed discussion of the pioneering work on representation theory, it is recommended that the reader consult Curtis [17]. This source includes a rich bibliography of several mathematicians who helped shape this field as well as provides an excellent survey of the development of representation theory. Other sources for the representation theory behind Schur functions can be found in [3] and [63]. Details on the symmetric function side can be found in [45] and [69]. More on the history of group characters can be foulld in [31]. Our preferred description of Schur functions is the combinatorial defini tion given by Equation 1.2. This description, together with Equation 1.4 and Theorem 1.5.1, allows us to work with Schur functions through purely combinatorial arguments. The equivalence between the combinatorial and the original definition of 5 A can be found in [12]. The first steps of this combinatorial description began with Kostka [36] decomposing the Schur functions into monomial symmetric functions via = Mitchell [50] was first to show that the Kostka numbers K were non negative. Finally Littlewood [42] posited that the Kostka numbers K counted the number of SSYTx of shape A and content i. The first version of the Littlewood-Richardson rule, Theorem 1.5.1, was given by Littlewood and Richardson [43]. The first complete proof of the statement was due to Schützenberger [67] in 1977. Short proofs can be found in [23], [60], and [77]. Some other objects that the Littlewood-Richardson coefficients enumerate can be found in [13], [55], and [80]. One of the early attempts to prove the Littlewood-Richardson rule led Robinson to an early form of the RSK (Robinson-Schensted-Knuth) algo rithm [61]. Schensted [65] independently developed the algorithm in order to enumerate permutations by the length of their longest increasing and de creasing sequences. Knuth [35] extended this algorithm to its commonly used 13 CHAPTER 1. INTRODUCTION form. Further extension to the RSK algorithm have been investigated and can be found in [46, 64, 79]. Further topics on the Littlewood-Richardson rule and the RSK algorithm are discussed in [72, 73, 75, 78]. Through the connection to representation theory, Equation 1.4 gives rise to the equation 1 = X X’ describing the multiplicities of the irreducible character and and the irreducible characters xA in the product of ‘, (S 0 SV) t= cS’, A in the induced tensor describing the multiplicities of the Specht module 5 5i product of the Specht modules S” and In the completely different setting of enumerative geometry, the same cal culations were being performed under the guise of Schubert Calculus, which was introduced by H. C. H. Schubert. In the cohomology ring of the Grass . and u,,, is given by 1 manian, the cup product of two Schubert classes cr 1 g U U, = c,oA. This was first proved by Carrell in [14]. Some studies of Littlewood-Richardson coefficients from this area include [11], [16], and [56]. Results specializing on multiplicity-free Schubert calculus can be found in [27] and [74]. Thus we see how the structure of the Schur functions plays an impor tant role in each of these areas. Equally important is the ability to com However, it is known that pute the Littlewood-Richardson coefficients the problem of computing the Littlewood-Richardson coefficients is #P complete [51]. Therefore it is unlikely that there any efficient algorithms to compute these coefficients. An estimate on the size of the Littlewood Richardson coefficients is given in [58]. A discussion on the many connec tions of Littlewood-Richardson coefficients to tableaux and the operations and algorithms on tableaux is given in [19]. A recent look at the possibility of factoring Littlewood-Richardson coefficients in special cases is researched in [33]. Other products on the Schur functions have also been studied. The Kro necker product, for instance, is examined in [2, 10, 62] Despite the difficulty in computing Littlewood-Richardson coefficients, there is much research into Schur function and skew Schur functions. Many 14 CHAPTER 1. INTRODUCTION 3 of Schur-equivalent recent results on determining the equivalence classes [D] skew Schur functions can be found in [8, 24, 26, 48, 59], and several results on the Schur-positivity of certain differences can be found in [6, 25, 34, 37, 47, 49, 57]. Each of these Schur-positive differences may be viewed as giving a set of inequalities that the corresponding Littlewood-Richardson coefficients must satisfy. In the next section we shall survey many of the known instances of Schur-positive differences and describe the Schur-positivity results that are proved in this thesis. Instances of Schur-positivity can lead to interesting results. For instance, a Schur-positivity result is used in [18] to characterize the eigenvalues of Hermitian matrix. However, the story does not end with Schur functions. There have been many analogues and generalisations of the Schur functions since their cre ation. There are the Hall-Littlewood polynomials, the Jack polynomials, and the Macdonald polynomials. Information on these polynomials can be found in [44] and [45]. There are generalizations into the realm of quasisymmetric functions. Some results in this area are discussed in [8], [29], and [39]. There are also Schur P-functions, Schur Q-functions, and k-Schur functions [71]. These new functions share many of the same properties as the original Schur functions. Also, we are interested in many of the same questions. For example, the possible equalities between a Schur and skew Schur function was given in [76] and the Schur Q-function analogue of this question is addressed in [4] and [28]. In [70], Stembridge determined which products of Schur func tions was multiplicity-free and Bessenrodt [7] classified the multiplicity-free products of Schur P-functions. Another multiplicity-free result on Schur P functions is given in [68], in which it is determined when a Schur P-function expressed in terms of regular Schur functions is multiplicity-free. Some re sults regarding the k-Schur functions can be found in [9] and [40]. Many new results of the classical Schur functions and of the more recent generalizations appear each year as attempts are made to better describe and understand their composition and their implications in the varied areas they appear. The breadth of open questions regarding these functions will serve to keep mathematical interest in this area open for a long time. 1.8 Overview of Schur-Positivity Results In this section we shall outline the results that are proved in the course of this thesis. However, we begin by surveying many of the Schur-positive results that have been proved in recent years. To state many of these results, 15 CHAPTER 1. INTRODUCTION we must make several definitions and discuss many ways of defining new partitions from given partitions. The definitions that are introduced in this section to describe these known Schur-positivity results will not be used in the remainder of this thesis. Before we begin, we shall first define a special type of diagram that will appear in several of these results. A ribbon is a connected skew diagram that does not contain the diagram (2, 2). Similarly, a weak ribbon is a skew diagram that does not contain the diagram (2, 2). We now begin by mentioning some of the known necessary conditions that are required for a difference of skew Schur functions to be Schur-positive. Given a skew diagram )/ with r rows. Then the k-th row overlap se quence is defined by rk(/) = (ar,. . . where a 2 is the number of columns occupied in common by rows i, i+1,. , i+ k 1. Then define rowsk)/) to be the partition obtained by placing the values of rk (A/it) in weakly decreasing order. Similarly COlSk (A/si) may be defined by inspecting the column overlaps of )/u. Also, one can define rectk,1)/L) to be the ilumber of k x 1 rectangular subdiagrams contained inside )/t. For partitions .A and u, we write ). ,u if . . — is 0 for any i > l(t). The relation defines , l(?), where for each i = 1, a partial ordering on the set of partitions called the dominance order. In [47], the following necessary conditions for Schur-positive differences are proved. . . . - Theorem 1.8.1 (Corollary 3.10, [7]) Let )/j and v/p be skew shapes. If sA/, 1 1. rowsk(A/I1) rowsk(v/p) for all k, 2. colsj(?../i) colsj(v/p) for all 1, and 3. rectk,l)/,u) — L’/p 5 >8 0, then rectk,1(v/p) for all k, 1. Given a skew diagram )/p, the base partition of )/i is denoted B/t) 0. The and is defined as the intersection of all diagrams v such that cover partition of A/ri is denoted by C(X/) and is the union of all diagrams 16 CHAPTER 1. INTRODUCTION v such that c L 0. In [25], it is remarked that 5 x/ Sv/p that B(A/) ç B(v/p) and C(v/p) ç C(A/). 0 requires These give two additional necessary conditions for the existence of a Schur positive difference. Alternative methods of computing the base and cover partitions are determined in [25], which gives a method of checking if these conditions are satisfied. Having looked at some necessary conditions, we now list a variety of instances of Schur-positivity. Many of these results are phrased as differences of products of Schur functions rather than differences of skew Schur functions. However, since any product of Schur functions can be realized as a skew Schur function via Theorem 1.6.4, these can all be restated as instances of Schur positive differences of skew Schur functions. We begin with two Schur-positivity results discussed in [6] involving the operation *. Conjecture 1.8.2 was first stated in [18] and the later general ized form, Conjecture 1.8.3, was put forth in [6]. Given an ordered pair of partitions ji), a new ordered pair (, u) = (*, ji*) is defined by taking Ak := — k+ — #{lI.u 1 — 1 + #{kPk “ — — k > 1 u k} for each k, and — l} for each 1. Conjecture 1.8.2 (Conjecture 5.1, /18]) For partitions A and we have * 3 S)*S, — Sj.S > 0. The definition of * can also be extended to pairs of skew shapes (/c, v/3) by taking v/ ( v)/( )* Conjecture 1.8.3 (Conjecture 2.9, /6]) For any skew partitions and ji/c (A,p) = ii//3, if (j/cv/J3)* then — S/aSvf5 >9 0. Some instances of Conjecture 1.8.2 and Conjecture 1.8.3 have been ad dressed in [6]. Namely, the following two results, Theorem 1.8.4 and The orem 1.8.5, have been proved. The first describes several pairs for which these Conjectures hold, while the second shows that the bounded height case reduces to checking Conjecture 1.8.2 for a finite number of pairs. 17 CHAPTER 1. INTRODUCTION Theorem 1.8.4 (Theorem 3.1, [6]) Conjecture 1.8.2 (or Conjecture 1.8.3) holds 1. For any pair A, i) of hook shapes. 2. For skew pairs of the form (/c, v//3), where ,a, v, c, o=/3. are hooks with 3. For skew pairs of the form (0, v//3), with v//3 a weak ribbon. Theorem 1.8.5 (Theorem 3.2, [6]) For any positive integer p, let v be a fixed partition with at most p parts. Then, the validity of Conjecture 1.8.2 for the infinite set of all pairs (j, v), with l(u) <p, reduces to checking the validity of the conjecture for the finite having at most p parts, and largest part bounded set of pairs (cr, ii), with as follows: p(vi+p). We shall now list several other operations on partitions that have given rise to Schur-positive differences. Given a partition A with each part even we define := (, ,. . Theorem 1.8.6 (Conjecture 1, [37]) For two skew shapes A/ i and v/p such that A + v and 1 even parts, we have S\//ASV/p >8 0. + p both have — A generalization of this result may be stated as follows. Theorem 1.8.7 (Theorem 11, [37]) Let A/it and v/p be any two skew shapes. Then we have — /ILSV/p 5 S 0. Given partitions A and ,u, we have the partition v = A U p obtained by listing all the parts of A and p together in weakly decreasing order. We then set sorti(A,p) = 5 , 3 (vj,v , ...) v and sort (A,p) = 6 2 2 (v , 4 , v . . Theorem 1.8.8 (Conjecture 2.7, [18]) Given partitions A and p, we have Ssortl(),)Ssort ( 2 )L) 18 — p s A 5 0. CHAPTER 1. INTRODUCTION This result may be generalized to skew shapes as follows. Theorem 1.8.9 (Corollary 12, [37]) Let A/ti and v/p be skew shapes. Then we have p,v)/sorti ort ,p) ,)/sort s 5 ( 2 ( A/LSv/p s 0. 5 — 1 (A Ai+n, Ai+ Given a partition A, let A” n, .). In this way the parts 2 A[i,?] for i = 1,. . of A are distributed among the partitions . . . Theorem 1.8.10 (Conjecture 6.4, [41]) For integers 1 m < n and a partition A, we have m fl fJ S[i,m] S[i,n] > 0. — A generalization of this result to skew shapes can also be given. Theorem 1.8.11 (Theorem 13, [37]) be the par i(’), be n skew shapes, let A = U 1 A()/ Let A(’)/i( ), 1 and tition obtained by the decreasing rearrangement of the parts in all we have Then = U. ..., Given two partitions A and AV i AA ji, > 0. we can define A V ji := (max{A , 1 := (min{A , 1 and A A ji by , Ii2},...) and 2 max{A ii}, , Ji2},. 2 min{A . i and v/p, the operators V and A can be 1 Then, given skew diagrams A/ defined on pairs of skew diagrams via (A/ii) V (v/p) := (A V v)/( V p) and ) A (v/p) := (A A v)/(i A p). (A/ i 1 u and v/p be any two skew 1 Theorem 1.8.12 (Conjecture 4.6, [38]) Let A/ shapes. Then we have SA/Sii/p 19 0. CHAPTER 1. INTRODUCTION Theorem 1.8.6 was first conjectured in [53], Theorem 1.8.8 was first con jectured in [18], Theorem 1.8.10 was first conjectured in [41], and Theo rem 1.8.12 was first conjectured in [38]. In [37], Theorem 1.8.12 was proved and was then used to prove each of Theorem 1.8.7, Theorem 1.8.9, and The orem 1.8.11, which in turn imply each of Theorem 1.8.6, Theorem 1.8.8, and Theorem 1.8.10, respectively. We have seen many operations that construct examples of Schur-positive differences. A seperate problem to investigate involves finding families of skew diagrams for which all instances of Schur-positive differences within these families can be determined. One result of this type occurs in [49], in which the collection of multiplicityfree ribbons is inspected. Using results of [27], multiplicity-free ribbons are classified as those ribbons with at most two rows of length greater than one and at most two columns of length greater than one. Then, among the col lection of multiplicity-free ribbons of a given size, the Hasse diagram which describes all Schur-positive differences and Schur-incomparabilities among these diagrams is explicitly described. Moreover, the Hasse diagram is es sentially a product of two chains. We now begin to inspect another collection of ribbons for which the ques tion of Schur-positivity is completely answered. It is not difficult to see that the skew diagram )./i’ is uniquely determined by the row overaps rows 1 (/t) and rows /t), thus we may identify the skew Schur function using the 2 overlap notation = 2 /i)rows 1 {rows ( A/t)}. In the case when A/si is a ribbon we have = {c11()_1}, where o is the composition given by the row lengths of )/ u. In this situation 1 we use the notation := = {c11)_1} and call ra a ribbon Schur function. In [8], it was shown that the collection {rA},H forms a basis of A. In [34], the following theorem was proved, which identifies the Schur-positive differences among this collection. Theorem 1.8.13 (Theorem 3.3, [3]) 20 CHAPTER 1. INTRODUCTION Let A and be partitions of n, then r if and only if,u -< A and 1(A) = — r), 0 l(,u). More Schur-positive differences were discovered in [34], and are easiest to state in terms of this overlap notation. We begin by considering the following hypothesis on compositions a and r. Hypothesis 1.8.14 Let a and and 1(r) = t> 0, and let a- and satisfy the following conditions: 1. The lengths of a- and 2. 3. as T ‘ be compositions such that 1(a) = s > 0 be sequences of non-negative integers that are s and t respectively; 1 when s > 0; = 1 when t > 0; } for 1 <i < s, and 4 4. ö <min{a, aj ‘j <min{r, rj} for 1 <i <t. Under this hypothesis, [34] proves that the following differences of skew Schur functions are Schur-positive. Theorem 1.8.15 (Theorem 3.1, [34]) b > 2 then we Assume a, r, a-, and satisfy Hypothesis 1.8.14. If a have {a,a,b,rja-,1,5} {a,a+ 1,b— 1,rja-,1,’} >30 and — {a, a, ra-, n—1 1 — ,a 2 {a, a + 1, a — 1, -ja-, n—1 1 } We now turn to describing the results and the flow of this thesis. We begin in Chapter 2 by defining staircases and fat staircases. We then describe how we augment these staircases with a skew diagram called the foundation by attaching the skew diagram to the staircase via a parame ter k. The augmented diagrams of this type are called staircases with bad foundations and will remain the focus for nearly all of this thesis. In Section 2.3 we define what it means for a diagram to be a sum of fat staircases and we prove Theorem 2.3.1 that, for each sum of fat staircases D, provides a collection of Schur-positivity results. Namely, we obtain an instance of Schur-positivity for each choice of the foundation. The remainder 21 CHAPTER 1. INTRODUCTION of Section 2.3 attempts to determine conditions for a diagram D to be a sum of fat staircases. In Chapter 3 we fix a fat staircase and a value k 0 and, for a given hook length, consider all possible hook foundations. We determine the structure of the entire Hasse diagram, which describes which pairs of the staircases with hook foundations have Schur-positive difference and which are Schur incomparable. In Section 3.1 we describe the Hasse diagram for values 0 k < 1 via Theorem 3.1.1, Theorem 3.1.2, Theorem 3.1.3, Theorem 3.1.4, and Theorem 3.1.5. In Section 3.3 we extend these results to describe the Hasse diagram for values k > 1 by proving Theorem 3.3.1, Theorem 3.3.2, Theorem 3.3.3, Theorem 3.3.4, Theorem 3.3.5, and Theorem 3.3.6. In Section 3.2 the expression for each Schur-positive difference for values 0 < k < 1 are computed by Theorem 3.2.2 and Theorem 3.2.3. In Chapter 4 we inspect the case of differences of fat staircases with bad foundations in which the foundations of the two diagrams are transposes of each other. In Theorem 4.1.1 and Theorem 4.2.1, we show that the differ ence is Schur-positive when one foundation is taken as either a single row or any two row partition. Also, when reducing to finitely many variables, we determine the largest number of variables for which this difference is zero. Most of the results of the earlier chapters are extended in Chapter 5 to yield results for fat staircases with complementary foundations. In particular, for a given fat staircase and hook length, Theorem 5.2.1 describes the Hasse diagram for the collection of fat staircases with hook complement foundations and the Schur-positive differences is calculated by Theorem 5.2.2 and The orem 5.2.3. Theorem 5.4.3 gives a collection of Schur-positive results from each sum of fat staircases D. Further, Theorem 5.3.1 and Theorem 5.3.2 allow us to construct many examples of sums of fat staircases. Finally, in Chapter 6 we once again consider reducing Schur functions to finitely many variables and prove several equalities of skew Schur functions that arise in this setting. The majority of our results make use of Lemma 2.2.2 and Lemma 2.2.3, which are proved in Section 2.2, and allow us to prove these results of Schur positivity by focusing solely on fillings of the foundation. These lemma pro vide much simplification while considering these skew Schur functions. 22 Chapter 2 Staircases with Bad Foundations 2.1 Regular Staircases A Ferrers diagram is a staircase if it is the Ferrers diagram of a partition of the form \ = (n,n 1,n 2,...,2,1) or if it is the 1800 rotation of such a diagram. Both these diagrams are referred to as staircases of length n and respectively. For what follows we will also will be denoted by S, and define _i = = 0. — — Example Here we see the two staircases of length 5: 65 If S, C ) as Ferrers diagrams then we say that \ contains a staircase of size n. In these cases we may create the skew diagram A/6. Example Here we see that the partition ) = (8, 5, 4. 2, 1) contains a staircase of size 3 and the corresponding skew diagram )/ö3. 23 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS I I A In this example A actually contains a staircase of size 4 and a staircase of size 5, but the skew diagrams obtained by removing these staircases are not connected. Definition Given n 1, k 0, and a partition A containing a staircase 6 k—l such that skew diagram A/t 1 A ii + k, then we k_1 is connected and k 5 can create a skew diagram called a staircase with a bad foundation, denoted S(A, k, n), by placing A/6k1 immediately below L such that the rows of the two diagrams overlap in precisely A 1 k positions. We call the subdiagram A/ök_1 the foundation of S(A,k,n). — We use the terminology “bad foundation” since if we imagine the diagram S(A, k, n) being pulled downward by a gravitational force then, for most choices of the foundation A, the foundation would fail to support S(A, k, n) properly, causing the diagram to tip over to the right. In the staircase with bad foundation S(A, k, n), k is the distance to the left of / that A extends before the copy of 6 k1 is removed. The requirement k < A , guarantees that the top row of the skew diagram A/Sk_l is non1 empty. The diagram S(A, k, n) is connected if k <A 1 and has two connected components, A/k_1 and if k = A . We also note that the skew diagram 1 S(A, k, n) can be written in the form P/ n+k—1, where a is a partition. 6 , Example For k = 0 we have 6 and A overlap in A 1 places. = 0, and k—1 = Thus S(A, k, n) consists of the foundation A left-justified with the stair case L. For example, with n = 5, k = 0, and A = (5, 4, 2) we have the following staircase with bad foundation: S(A,0,5) 24 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS 1 places. and .\ overlap in For k = 1 we have 6 = 0, and k1 = shifted one foundation ,\ with its diagram n) SA, 0, is the Thus k, n) 1, and ) = (5, 4, 2) we have the to the left. For example, with n = 5, k following staircase with bad foundation: — S,1,5) A Example Here we show the staircase with a bad foundation 8, 4,5), where = (8, 5, 4, 2, 1). S(A,4,5) In this instance the conjugate of A, At = (5,4, 3, 3, 2, 1, 1, 1), also gives rise to a staircase with a bad foundation S(At, 4, 5). , 4, 5) t S(A 25 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS One of the advantages in computing the skew Schur functions of staircases with bad foundations is that, when using the Littlewood-Richarson rule, the /S portion of the diagram can be filled in only one way. This can be seen 6 is a Schur algebraically from Theorem 1.6.3 since s = s = s, where s function. The unique filling of Z?1 obeying the semistandard conditions and the lattice condition is easily found to be the filling shown below. 1 1 1 1 n—4n—3n—2 1 2 n—3n--2n--1 2 3 n-2n-1 fl Another advantage in computing the skew Schur function of a staircase with bad foundation is the following fact, which arises from the structure of the unique content, v = = (n, n 1, , 2, 1), just mentioned. . — . . Lemma 2.1.1 Let S(A, k, n) be a staircase with bad foundation and ‘T be a SSYT of shape S(\, k, n) whose reading word is lattice. Then the entries in the first row ofthe foundation A/ökl of T form a strictly increasing sequence. Proof Let ‘T be a SSYT of shape k, n) whose reading word is lattice. As discussed previously, the Littlewood-Richardson rule allows only one way of filling the / portion of the shape k, n). The content of this filling of is(n,n—1,...,2,1). Let R be the first row of the foundation, and suppose that R contains 1 since the second value in R is immediately the value j twice. Then j below a value that is greater than or equal to 1 and the columns of ‘T strictly increase. Also, if j > 1, then when reading ‘T the lattice condition will be violated once we have read both j’s. Therefore no value j can be repeated in R, and hence the first row of the foundation of ‘T contains no repeated values. 26 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS 2.2 Fat Staircases In the previous section we saw that in creating any SSYT of shape S(A, k, n) with lattice reading word, the following two properties held. Namely, 1. the entries of / are uniquely determined, and 2. the entries in the first row of A/ok_i are distinct. In this section we look into what other shapes besides the staircase can we append a foundation, so that we still have the analogous properties. Instead of Z, we begin by looking at a general skew diagram D = p/ps. Also, instead of removing 0 k—l from A, we consider removing an arbitrary partition ic A. Then we want to append the diagram A/ic to the bottom of D. Namely, for a given k, we place A/ic immediately below D such that the rows of the two diagrams overlap in precisely A ic 1 k positions. Then k is the distance to the left that the first row of A/ic extends from the last row of D. We represent this new skew diagram by S(A, Ic, D; k). Now given S(A, ic, D; k), we are interested in what conditions will guarantee that, when creating any SSYT S(A, Ic, D; k) with lattice reading word, the filling requires that — — 1’. the entries D are uniquely determined, and 2’. the entries in the first row of A/ic are distinct. We now look at which skew diagrams S(A, ic, D; k) satisfy these properties. Suppose a given skew diagram S(A, ic, D; k) satisfies 1’ and 2’. Then, by 1’, any SSYT S(A, ic, D; k) with lattice reading word has the same content for the subtableau of shape D. Let ii be this unique content. Since any SSYT of shape D with lattice reading word can be extended to a SSYT of shape S(A, ic, D; k) with lattice reading word, 1’ implies that there is only one SSYT of shape D with lattice reading word, and this tableau has content v. Therefore 5 D = s,, where v is a partition by the Littlewood-Richardson rule. We now make use of the following result. Theorem 2.2.1 [76, Theorem 2.1] For partitions A, u, ii 1 sA/, = s if and only if A/p 27 = 11 or CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Hence, if S(;k, D; k) satisfies 1’, then D = ii or D = 110 where v is a partition. We now inspect property 2’. The proof of property 2 (i.e. Lemma 2.1.1) relied on the the fact that the first row of )/ök.i extended at most 1 box was and the fact that the content of to the left of the staircase the partition 6, which is the sequence of consecutively decreasing integers 1,. , 2, 1). In fact, if the first row of )/i extends at most 1 box (n, n to the left of the diagram D, where D = 11 or D = v° for v equal to any sequence of consecutively decreasing integers ending in 1 with repetitions allowed, then the same method proves that 2’ holds. That is, all partitions 1)°—’,. ,2°’, 1a1), where each 11 given by sequences of the form (n°, (n cvj > 1. This partition arises as the content of the tableaux of shape D = (n°’,(n— 1)° 1,...,2a2,11) and D = (fln,(n_ 1)aTh_1,...,22,1a1)0. We shall denote these two diagrams by — . . . — (n°, (n — 1)°—’, . . . , 2°, . 11) and = (n°,(n— 2, )0, )n_1,..., 1 Q 2 1 This composition c has a = , c) is a composition. (c, = j where j = l(O) = l(za) is the length of these diagrams. We have just showed that for diagrams D = Oa and D = /. and 0 < k < 1 we have that S(), i, D; k) satisfies 1’ and 2’. Conversely, if either k> 1 or ,, D; k) v > 1 for some i, then if either D = ii or D v°, where 11 j1 cannot satisfy 2’. This follows since the value 1 can be placed in the first row of .A/ic a total of k times and the value i can be placed in the first row of are precisely v times. Therefore D = O and D = a total of 11 j1 the diagrams in which we are interested. or D = L for some We call a skew diagram D a fat staircase if D = The numbers c, count the number of rows of D with i boxes, composition = for each i. Using this notation the regular staircases may be expressed as semistandard note unique the that respectively. We and 6(m) = (1), filling of La (O, respectively) has c as its largest entry. We choose the terminology “fat staircase” for describing these staircases with repeated rows in analogy to the usage of “fat hook” in [70] in which a ’). 2 A fat hook is defined as a diagram of the form where c = . . . — — . 28 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Example Here we see the fat staircases 6(1,2,2) 6(1,2,2) and (3,1,2,3) k, n) was of the form IL/ön+k_1, where 6 Just as the diagram n+k—1 is , where 67 7 a staircase, it would be nice if S, ,c, c; k) was of the form i/6 ,ç 1 and = 6 for some com k is a fat staircase. This requires that 0 can be written as S(\, 6, ; k) form of this position 13. Thus the diagrams for 0 < k < 1. We shall be interested in the more general case of a founda tion )/t and k 0. Therefore we make the following definition and use the following simplified notation. k a with ) Given a composition c, k > 0, and partitions X, 4 placing .A/i by diagram obtained 1(a) we now define S\, , c; k) to be the such that the rows of the two diagrams overlap in immediately below k positions. We call S\, t, c; k) a fat staircase with bad precisely )4 i is called the foundation of S(\, ,u, a; k). 1 foundation. The subdiagram A/ If ,u = 6 for a composition /3, then we write /3, ; k). When we do not wish to cut out any diagram t, we shall write p = 0 and simply use ; k) in place of S(?, z, c; k). The reason we write /3, c; k) instead of writing S, /3, c; k) is , 2 c to avoid confusion in the cases when the compositions o = and /3 = (/3 /32,...) are weakly decreasing, and could be misinterpreted as representing diagrams of partitions. For example, consider the diagrams S((2, 1), (2, 2); 1) and S((2, 1), (2, 2)1; 1) shown below. The first uses the di agram D = (2, 2), whereas the second uses the diagram D = (2,2). — — — — S((2, 1), (2, 2)1; 1) S((2, 1), (2, 2); 1) 29 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Example Here we show that the partition A contains the fat staircase 5, for A (7, 7, 5, 3, 3, 2) and 3 (1,2,2). We also display the skew diagram A/6j. (5(1,2,2) A ç A Now we show the fat staircase with bad foundation S(A, , c; 1) for (7, 7, 5, 3, 3, 2), = (1,2,2), and c = (3,1,2,3). = S(A, c; 1) We have seen that the fat staircases with bad foundations S(A, t, ; k) 1. Moreover, we have the following result k satisfy 1’ and 2’ when 0 when considering any k 0. Lemma 2.2.2 Let S(A, ,u, ; k) be a fat staircase with bad foundation for some k > 0 and T be a SSYT of shape S(A, t, c; k) whose reading word is lattice. If = (cr ,. , cj, then the entries in the first row of the foundation 1 of T consist of values taken from the set . . Rak={1+fl+1_i =12...n}U{ 30 {} CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Furthermore, the value 1 can occur at most k times and the rest of the values can appear at most once. Proof Let R be the first row of the foundation of 7 and t e R. Since ‘T is a SSYT, the columns strictly increase. Thus t = 1 is allowed 1 since it is precisely in that case that the first value in R if and only if k of &. Furthermore, since there are only k boxes from an entry is not below the first row of the foundation of T that extend out from , there can be at most k l’s in R. If t > 1 then, when reading the row R from right to left, the lattice than there 1 in condition implies that there is at least one more t , 11), the only are t’s in zic. Since the content of & is (n°, (n 1)’,.. instances when this occurs are when t = cn+ij for j = 1, 2,.. . , n. Therefore every entry of R is an element of RQ,k. Further, if a value t > 1 appeared twice in R, then the lattice condition would be violated. Hence t 1, can appear at most once in R. each t I — — . The next result tells us when we may obtain a SSYT of shape S(A, i, c; k) with lattice reading word from a SSYT of shape )/i) /. with lattice read 1 and 1 $ D denotes the disjoint union of the diagrams D ing word, where D . 2 D be partitions, and k > 0 Lemma 2.2.3 Let c be a composition, ). and with lattice k < l(o). If T is a SSYT of shape )/t such that ) row of )/t, then reading word such that there are at most k 1 ‘s in the first the tableau of shape S\, ,u, c; k) obtained from T by shifting the foundation )/ to the right is also a SSYT with lattice reading word. — — Proof Let T be a SSYT of shape )./i & with lattice reading word and let T, be the tableau of shape S\, a, c<; k) obtained from T by shifting the foundation ) to the right. Since shifting A/ to the right does not affect the order in which the entries are read, T has a lattice reading word. Also, the rows of T weakly increase since they are the same as the rows of T. Further, to check that the columns of T, strictly increase, we need only check that they strictly increase at the positions where the two subdiagrams L and are joined. Let R denote the first row of )/ and ci = (, . . . , aj. As in the proof of Lemma 2.2.2, the lattice condition on T implies that the entries of R consist of values of R,k. Further, the value 1 can occur at most k times and the rest of the values of R are distinct. Let q be the number of times 1 appears r be the entries of R. 1 2 r in R, so that k > q. Further, let r 31 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Since r 1 = j n we have 1. Consider the case k rq = min(R,k) and for each 1 the = (j + 1)-th smallest value of R,k = = rq = 1, we have 1+ jrrl Since k > q, for each 1 j rk n we have rj+q 1+ n+1-i i=1 As illustrated in the diagram below, the entry r+k is beneath boxes. From the unique fillillg of , the entry of & directly above r+k is >lrl n+1—i fl—i j II r T2 rk ri+ 4 +) 2 T 32 +, 3 r CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Thus the columns strictly increase. Therefore T is a SSYT with lattice reading word, as desired. Now consider the case when k = 0. Then for each 1 <j <n we have J r > j-th smallest value of R,k 1+ boxes, so the entry of 3 is beneath precisely Also, the entry r 3 is L, directly above r cn+i. Thus the columns strictly increase. Therefore This a SSYT with lattice reading word, as desired. • Consider the Example Let c = (2, 2, 1), = 0, ) = (3, 2), and k = 1. with lattice reading word and only one 1 in the first SSYT T of shape ) left. This gives rise to the SSYT of shape S, c; 1) row of ) shown on the with lattice reading word shown on the right. 1 2 1 3 2 4 1 3 5 2 6 3 2.3 Sums of Fat Staircases Suppose a diagram D = p/ic is such that SD = :: vfat staircase That is, for every v that is not a fat staircase, we have c, = 0. When this happens we say that D is a sum of fat staircases. For each fat staircase v we 33 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS = ii. That is, c(v) is the number let c(zi) be the composition such that compositions these we can rewrite SD as Then using of parts of i’ equal to i. D= 8 v=fat staircase Example Let p=(4,3,3,3,3,3,3), i,j,i) S( , 2 3 , 4 SD = (3,2,1,1) + + ic= (2,2,2, 1, 1), and D=p/,. Then i,i,i) S( , 2 , 3 ) 313 S( + i,i) S( , 2 , 3 + Thus, when computing the Schur function of D, we are interested in the following diagrams. D E ) 3 , 2 L( ‘(3,1,3) (3,2,1,1) For a sum of fat staircases D and a value k By assumption, we have , D; k). 0, we consider the diagram CvS(). = zi=fat staircase When we compute the skew Schur function SS(A,,D;k) we notice that, since the contents that the subdiagram D is strictly above the foundation arise from the fillings of D are precisely the fat staircases 5, for each v with [sJ (SD) # 0. For each of these fillings of D, we then need to extend them by 34 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS filling the foundation )/ such that the resulting tableaux are SSYTx with lattice reading words. Thus, when computing the Schur function of S(A, , D; k), we are inter ested in the possible fillings of the following diagrams. -I- The next result summarizes the relationship between these fillings. Theorem 2.3.1 Suppose a diagram D p/ii is such that . 11 C,S SD = v=fat staircase Then for each partition ) and t with u ), and for each k 0 we have SS(Aq,D;k) s Proof Since D is a sum of fat staircases, the content of each SSYT of shape D with lattice reading word is some fat staircase ii. To prove the iden tity, we consider the map that takes a SSYT T of shape S(A, i, D; k) with lattice reading word and c(D) = v to the tableau T’ of shape S, u, a(zi); k) with content ii and filling the copy of obtained by filling the copy of )/ identically to its filling in T. 35 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS We claim that each tableau T’ is also a SSYT with lattice reading word. Given such a tableau T’, consider the corresponding tableau T’ of shape Then T’ is a SSYT since both of the subtableaux of shape are semistandard. Further T’ has a lattice reading word A/ and is since checking the lattice condition within the subtableau of shape trivial, and then, by the construction of T’, the lattice condition after this point simply becomes identical to the lattice condition for T. Therefore ‘T’ is a SSYT with lattice reading word. Further, the first row of the subtableau A/ of T’ coiltams at most k l’s since T was a SSYT. Hence, by Lemma 2.2.3, T’ is also a SSYT with lattice reading word, exactly as claimed. Thus, for each SSYT T of shape $, , D; k) with lattice reading word and c(D) = v we obtain a SSYT T’ of shape S(A, ,u, cv(v); k). Now fix an 1 T are both SSYT of shape S(A, , D; k) image T’ and suppose that T with lattice reading word such that T = T’ = T. Let SX, p, c(v); k) be 1 the shape of T = T’ = T. Then the filling of the foundation A/[L in T , and the content of 2 is the same as the filling of the foundation A/si in T 1 and T . Since there are only c SSYT 2 the subdiagram D is v for both T of shape D with lattice reading word and content v, there are at most c, distinct SSYT of shape p, D; k) with lattice reading word that could map to T’. This implies that SS(Aqj,D;k) s as we desired. > I Example Let D=(2,2,2,2,l)/(1,l), )=(2,2),=ø, andk=l. Then SD = 8(2,2,2,1) + ,l,l,l) 2 S(2, = ) 13 S( is a sum of fat staircases. Here we display D, D ) 3 L(i, + (1,3), (32) and L( ). 2 , 3 (3,2) We are now interested in the diagrams S(\,D;l), S(A, (1,3)1; 1), and S(A, (3, 2)1; 1) for ) = (2, 2). 36 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS S(?, (3, 2); 1) S(), (1, 3); 1) S(A, D; 1) We can compute that SS,D;1) + = 5(3,3,2,2,1) + 5(3,2,2,2,1,1) 5(3,3,2,1,1,1) + + ,i,i,i,i) 2 , 3 S( + 5(3,2,2,2,2) + 5(2,2,2,2,2,1) + 5(2,2,2,2,1,1,1) ,i,i,i,i,i) , 3 S( and SS(A,(1,3);1) + SS,(3,2)<;1) + 25(3,3,2,1,1,1) + 5(3,3,1,1,1,1,1) ,l,l) + S( 2 , 3 ,i,i,i,i) 2 , 3 ) + 2S( 2 , 3 + S( ,l,i,i), , 2 + 5(2,2,2,2,2,1) + S( = l) 2s( , 2 , 3 ®j so we see that ® SS(A,D;1) s SS,(1,3);l) + SS,(3,2)1;1), as predicted by Theorem 2.3.1. ®j We now proceed to examine which skew diagrams D are sums of fat staircases. The following results are concerned with adding or removing columns to a skew diagram on the left or right side of the diagram. We recall 1 and D 2 of depth i. That 2 denotes the near-concatenation of D 1 D that D 2 are both of length greater 1 and first column of D is, if the last column of D 1 2 is the is the skew diagram obtained by D than or equal to i, then D 1 is one step left and i 1 1 and D 2 so that the top-right box of D placing D box of In other . 2 D words, the last column of steps up from the bottom-left 2 overlap in exactly i boxes. 1 and the first column of D D — Lemma 2.3.2 Let c be a column and D be a skew diagram that is not a sum 2 = c D be obtained from D by 1 = D ® c and D of fat staircases and let D 1 nor D 2 is a sum of fat the addition of a single column c. Then neither D staircases. 37 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS 2 is not a sum of fat staircases. Proof We shall begin by proving that D Since D is not a sum of fat staircases there is a SSYT T of shape D and lattice reading word whose content is v, where v is not a fat staircase. That is, v 3 v+ + 2 for some j. Let n be the length of the column c. We create a tableau T’ of shape 2 and lattice reading word by filling c with the numbers 1,2,. , n and by D 2 as D is filled in the tableau T. Then T’ is semistandard filling the rest of D and has a lattice reading word. Further, c(T’) = v + (in). There are three cases to consider. If j < n, comparing the j-th and (j + 1)-th entries of this content gives . c(T’) If j = Vj +1 n, comparing the j-th and = c(T’) = Vj vj+i +1 vj = c(T’)+i + 2. (j + 1)-th entries of this content gives vj+ And if j > n, comparing the j-th and = +3 . c(T’)+i + 3. +3 (j + 1)-th entries of this content gives 1+2 v = c(T’)+i + 2. In all cases we see that c(T’) is not a fat staircase. Hence D 2 is not a sum of fat staircases. Then, since SDo = 5 D is also not a sum of fat staircases, the above shows that c ® D° is not a sum of fat staircases. Now, since 1 = 5 SD DGc = S(DGc)o = ScoDo, • 1 is not a sum of fat staircases. we find that D Corollary 2.3.3 If D is not a sum of fat staircases and D’ is obtained from D by the addition any number of columns, then D’ is not a sum of fat stair cases. Proof Let D’ be a diagram obtained from D by adding, in order, the columns , C 1 C 2 0 and, for each i = 1,.. , n, let D be the subdiagram , Cn. Let D = D of D’ consisting of D and the columns c ,. , c. Then using Lemma 2.3.2 1 repeatedly we find that D is not a sum of fat staircases for each i = 1,. , n. Since D = D’, we are done. . . . . . . . . • Corollary 2.3.4 If D is a sum of fat staircases and D’ is a connected subdi agram of D obtained by removing columns, then D’ is a sum of fat staircases. 38 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Proof This is precisely the contrapositive of Corollary 2.3.3 with the roles of D and D’ reversed. I Therefore every diagram D that is a sum of fat staircases can be viewed as a column extension of a smaller diagram D’ that is also a sum of fat staircases. Knowing this, for a given diagram D that is a sum of fat staircases, we now consider what length of columns can be added to D and how much can a column overlap with D if we wish the new diagram to also be a sum of fat staircases. Towards this end, we have the following result. Lemma 2.3.5 Let c be a column, D = p/si be a sum of fat staircases, and D’ be given by either D’ = c® D or D’ = D ® c. If D’ is also a sum of fat for each ii with staircases, then we have 1(c) + 1 R (),l and i + 1 0 c0. = c GD. As in the proof of Lemma 2.3.2, Proof We shall consider the case = D Ø c can then be obtained by rotating diagrams the second case by 180. 0. Since c 0, there Suppose 1(c) + 1 e R(),l for some ii with is a SSYT T of shape D with lattice reading word and content v. Now we create a tableau T’ of shape D’ by filling c with the values 1, 2,.. 1(c) and filling D as in the tableau T. Then T’ is clearly a SSYT with lattice v + (11(c)). Since 1(c) + 1 e RQ(V),I, we have reading word. Further, c(T’) o(v) , 1 _ (n(”)’,n 0 1(c) = c(v)+i_ for some k, where z’ Thus . . — c(T’) = = v + (i) n — 1, (v) 0 c 1 _ . , n+1 , n+2 . — k n+1k n — n — ., ka(v)0_k (v)n( ii)_ 1 ( = + (n + (t’) 1 , 0 . . . — kn_k,.. ., Thus c(T’) is not a fat staircase, and so D’ is not a sum of fat staircases. Therefore, if D’ is a sum of fat staircases, then we require that 1(c) + 1 Ra(v),l for each v with c,, $ 0. 0 Similarly, suppose that i+1 E R(),l for some v with 0. Since c, 0, there is a SSYT T of shape D with lattice reading word and content v. We create a tableau T’ of shape D’ by filling c with the values 1, 2, i, 1(u) + 1(v) + 1(c) i and filling D as in the tableau T. Again, T’ is 1,1(v) + 2,. 1(c)_i). a SSYT with lattice reading word. Further, c(T’) = ii + (U) + (01(v), 1 . . . , — 39 .. , CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Since i + 1 e (nv)n, (M),_1, 1 c(T’) = — = — v+ we have i () + n— (O(1/)n (n + a(v)i) 1 for some k, where = ii = Thus 1(c)_i) 1 n(v)1, 1 Q(l/)_i n + 1 ka(v)n+1_k, n 1(c)_i) + (01(v), 1 — k(M)n+1_k, , n + 2 , . . — — — c(v)l+1(c)_i). 2a(v)2, 1 Thus c(T’) is not a fat staircase, and so D’ is not a sum of fat staircases. Therefore, if D’ is a sum of fat staircases, then we require that i + 1 0. Ra(v),l for each v with c • Example Consider the diagram D = (2, 2, 2, 1, 1, 1)/(1), seen below. We have SD = S( ,2,l,1) , 2 + ,i,i,i,) = (23) , 2 S( + ). 42 S( Therefore, when adding a column, we must avoid lengths and overlaps that are one more that an element of ),i 2 , 4 ),i U R( 3 , 2 R( = {1, 4, 6} U {1, 3, 7}, if we wish our new diagram to also be a sum of fat staircases. For instance, if we add a column of length 6 to the diagram, then since ),i the resulting diagram is not a sum of fat staircases. 2 , 4 6 + 1 E R( ),i U R( 3 , 2 We show a tableau that demonstrates this when the overlap i = 4. 40 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Since the content of this tableau is i’ = (3, 3, 2, 2, 2, 2), the new diagram = (16) ®. D is not a sum of fat staircases. It is important to note that although the conditions 1(c) + 1 R),i and ‘i + 1 Rc(v),1 are necessary in Lemma 2.3.5, they are by no means sufficient conditions. ‘ Theorem 2.3.6 If D is a sum of fat staircases then the columns of D have distinct lengths. Proof Let D be a sum of fat staircases. Suppose D has n columns c , 1 , c and, for each j, let m 3 be the number of columns of length j. We create a tableau T of shape D by filling each column c with the entries 1, 2,. , l(cj). Then T is a SSYT with lattice reading word and content = 2(l1(c)) 3 is the number of columns of D of length I, Thus, for each j, zi greater than or equal to j. Therefore we have . . . . = 1 + m, _ 3 v (2.1) for each j. Since D is a sum of fat staircases, ii is a fat staircase. Therefore Equation 2.1 implies that 0 < rn 1 for each j. In other words, the columns of D have distinct lengths. • Example Considerthe diagram D = (5,4,4,3,3,3,2, 1)/(3,2,2, 1,1), which has two columns of length 3. Filling each column c of D with the entries 1, 2, 3,. , 1(c) gives the following tableau of content i = (5, 4, 4, 2, 1). . . 41 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Since ii is not a fat staircase, D is not a sum of fat staircases. We finish this chapter by proving the converse of Theorem 2.3.6 in the case of a diagram with two columns. Lemma 2.3.7 If D is a connected diagram with two columns and these columns have distinct lengths, then D is a sum of fat staircases. Proof Let D be a connected diagram with two columns of distinct lengths. Let T be a SSYT of shape D with lattice reading word and let u be the content of T. Since there are only two columns in T and the entries of each column strictly increases we have v < 2 for each i. Hence, if D is not a sum of fat staircases then there must be a SSYT T of shape D and lattice reading word with content i = (2”), for some n. Since the columns of T strictly increase, this implies that both columns are of length n, contrary to assumption. Therefore D is a sum of fat staircases. I 42 Chapter 3 Hook Foundations In this chapter we consider fat staircases with bad foundations using two simple families for the foundations. In Section 3.1 we shall look at SA, ; k) for hook diagrams A. We shall be able to completely describe which pairs of ,D 1 2 satisfy 8 these fat staircases with hook foundations D 0 and 2 SD 1 D which pairs are Schur-incomparable. We also give a Schur-positivity result using a diagram D that is a sum of fat staircases. In Section 3.2 we will give an explicit formula for computing the Schur positive differences of fat staircases with hook foundations that were dis cussed in Section 3.1. — 3.1 Schur Comparability / Incomparability Recall from the introduction, that we write D 1 >— D 2 whenever 5 1 —8 D 2 D 0, and if we consider the relation ? on the set of all Schur-equivalent classes of diagrams (i.e. [D] 8 = {D’jsD = SD’}), then defines a partial ordering. This allows us to view the Hasse diagram for the relation >- on the set of these Schur-equivalent classes. For the sake of convenience, we write D in place of [Dj . 8 43 CHAPTER 3. HOOK FOUNDATIONS Example Here we show the Hasse diagram for on the collection of stair foundations S(A, (or (i); cases with bad 0, 7) 0) in the fat staircase notation), for ) varying over all hooks of size 7. A line drawn from a diagram 2 in an upwards direction indicates that SD 1 to a diagram D D 0. 1 — 5 2 D note that the diagrams along the top are all Schur-incomparable. We That is, they form an anti-chain with regards to >-. Also, the diagrams along the right are all comparable. That is, they form a chain with regards to >—. 44 CHAPTER 3. HOOK FOUNDATIONS Now, if we consider hooks A of size 6, we will obtain the following Hasse diagram. Again, the diagrams along the top are all Schur-incomparable and the diagrams along the right are all comparable. When working with hooks, we shall find it convenient to describe each hook by its arm length and leg length. Hence, we let 1 u be the hook (.ua, 1’’) and A be the hook (Aa, P”’). In this chapter we shall use a fixed fat stair case , where c = (cr , €2, 1 Thus n is the length of the bottom row , of the staircase . . . . 45 CHAPTER 3. HOOK FOUNDATIONS The following results summarise all the ? relationships between diagrams of the form S, ; k) when A is a hook of fixed size h < n+k and 0 < k < 1. n + k is needed to guarantee that SA, c; k) is a skew The restriction h diagram for every hook A of size h. Theorem 3.1.1 and The u with Aa, ILa For each pair of hooks A, 1 orem 3.1.2 each prove one side of the Schur-incomparability of this pair, thus describing the antichain structure displayed along the top of the Hasse diagrams in the previous examples. For each pair of hooks A, u with Aa < Ita, Theorem 3.1.3 shows k). This describes the chain structure displayed k) S(, that S(A, c; Js c; along the right of the Hasse diagrams in the previous examples. Theorem 3.1.4 and Finally, for each pair of hooks A, [t with Aa, I-’i if and only if S(A, S(i, ; k). Theorem 3.1.5 show that Aa t’i c; k) This describes the relationships between the diagrams displayed on the right with the diagrams displayed along the top in the previous Hasse diagrams. Ei, <Eii, ‘— Before we begin, we review some facts regarding any SSYT of shape S(A, c; k) with lattice reading word. Any such tableau will have & filled 1)-’,. , 2, 1’). This content led us to with content 6 a = (n°, (n define the set . — . =1_k2_k...n} of size n + k and largest element ci + 1. This set gives the values of the foundation A which can be read immediately after reading If we read some other value immediately after reading , then the lattice condition will be violated. Hence, when reading the entries of the foundation, in order to read some value x 0 Ra,k without violating the lattice condition, we must first read some value r e Rc,k and read each of r + 1, r + 2, 1 before , x reading x. . . . . — Let us finally begin. We start by looking at the antichain structure. Theorem 3.1.1 Let A and it be distinct hooks with Aj = j,a = h n+k and and let 0 k 1. Then we have S(it c; k) S(A, a; k). Aa < ita Proof We shall show that there exists a SSYT T of shape S(A, c; k) with lattice reading word such that there is no SSYT of shape S(it c; k) with lattice reading word having the same content. This is sufficient to prove the theorem. 46 CHAPTER 3. HOOK FOUNDATIONS Let r 1 < r < Since Aa < Ita and A < rj IiI, we have A1 > be the values of R,k. We can create a SSYT of shape A by filling the boxes of A as follows. . 1 r c 1 r_ +1 1 +A It is easy to check that the resulting tableau of shape A & has lattice reading word since each of the entries in the first row of A are from RQ,k. Thus Lemma 2.2.3 provides us with a SSYT ‘T of shape S(A, c; k) with lattice reading word, where A is filled as shown above. Since , we have l(S(jt, a; k)) = oj + 1 1 uj < k + A . Therefore no 1 < A SSYT of shape S(t, c<; k) with lattice reading word can contain the entry . Thus no SSYT of shape S(p,, a<; k) with lattice reading word can 1 c +A have the same content as T. Hence, it follows that SS(;k) 8 S(A,c;k) s 0. — I Theorem 3.1.2 Let A and i be distinct hooks with A = = h < n+k and and let 0 < k < 1. Then we have S(A, ; k) S(j, ; k). Aa <fLa ri Proof Let r 1 < r 2 < < rfl4 be the values of R,k. We can create a SSYT of shape i by filling the boxes of p as follows. 1 r 2 r ra + 1 Since we are using distinct values of R,k, it is easy to check that the resulting tableau of shape [LL has lattice reading word. Thus Lemma 2.2.3 provides us with a SSYT ‘T of shape S(, c; k) with lattice reading word, where is filled as shown above. We now wish to count all SSYT of shape S(i, c; k) (shape S(A, c; k), respectively) with content v = c(T). Since & has a unique way of being filled, we must find all semistandard fillings of i (A, resp.) with the values , r 1 r , 2 , rk. Since r 1 < r 2 < < rh, the value r 1 must appear in the top-left corner of j (A, resp.). Further, once we choose 1 (Aa 1, resp.) . . . — 47 — ______ CHAPTER 3. HOOK FOUNDATIONS (first row of )., of the values r 2 <r 3 < <rh to appear in the first row of remaining r’s must appear in the first column and the order resp.), then the of all these values is uniquely determined by the semistandard conditions. Therefore the number of SSYTx of shape S(, ; k) = ic’/p’ with lattice reading word and content v = c(T) is given by ,‘ (h—i 1 [t = — and the number of SSYTx of shape S(, c; k) = i’/p with lattice reading word and content v = c(T) is given by ,, Cp h — Since )a ‘a > Pa < — (h—i i\ ?a1 we have h + 1 a < 1 and we obtain > a + I-a Therefore we have hAaj>/aij, (3.1) for each i. Therefore (h—i)! (h — — — ia)!(iia — 1)! (h_i). (h)a)!(Aa1)! aAa1 ri h\i = cpvx > cv, /ta1 where we have used Equation 3.10 in the final step. Since we have found a content i’ with c,, > we can conclude that ss(,<;k) SS(,1;k) 0. — I We now depart from looking at the hooks .)., t satisfying Aa < [La < Instead, we turn to the hooks )., [L satisfying < /ta. The following theorem shows that we have the chain stucture that was evident in the examples. ri. [ 48 CHAPTER 3. HOOK FOUNDATIONS h < n + k and Theorem 3.1.3 Let ). and ,u be hooks with j) = 1. Then we have S(;\, k) k c; S(j, ; k). a <Ia and let 0 ri Proof To prove the result, we shall consider any content v such that a SSYT of shape S(i, ; k) with content v and lattice reading word exists. First we shall show that there is also a SSYT of shape S(A, ; k) with content v and o; k) = ,i/p and S(j, cv; k) = lattice reading word. Then, letting shall show that the Littlewood-Richardson and we for partitions ,c, ic’, p, p’, coefficients for these two diagrams and this content satisfy cL, Having shown that this inequality holds for any content ii for which a SSYT of shape S(, c; k) with content v and lattice reading word exists, this will imply that ss(,a;k) SS(u,o;k) s 0. Let v be a content such that there is a SSYT 7j of shape S(t, c; k) with content v and lattice reading word. By Lemma 2.2.2 we know that the 1 < a < first row of ji contains a strictly increasing sequence a < where each a e R,k. Also, since the columns of 7 strictly increase, the first column of ) contains a strictly increasing sequence a < a < . Since 1 can only be filled in one way (in both < a, where a = a shapes S(t, c; k) and ; k)), in order to obtain a tableau of shape 1 a S\, a; k) and content i’ we only need to show how to place the values of ,...,aa}U{a {ai,a , 2 , 3 ...,aj} a in If 1(v) > Ic + 1 for this particular content ii then there are entries of 7 greater than a + 1. Since & has content öa, the lattice condition implies that c + 2 appears in [t. Since each a e Rc,k, we have a < c + 1 for each i and so a = I°d + 2 for some j > 1. The lattice condition and the fact that the column strictly increases gives that = 1 a = 1 a = aI+tj—j+2. Again, by the lattice condition, it is clear that any SSYT of shape ; k) 1 a with lattice reading word and content v must also have these values a, a+ , 1 49 CHAPTER 3. HOOK FOUNDATIONS as the last , we have 1 <A — gives j+ — 1 entries of the first column of A. Since Aa < 1 j + 1. This gives, j+1<A /ta — (3.2) IM—j+lA1, so these entries do fit in this column. Note that if 1(u) < a + 1, then this 1 is empty and we do not have to worry sequence of values a, a+ ,. , a 1 about placing any entries larger than al + 1. Let M be the multiset {a ,a 1 ,. , a} U {a, as,. , a_ 2 }. Then M is 1 the remaining entries that we still need to place in A to obtain a tableau of shape S(A, a; k) and content v. We have IM = ILa + j 2 and max(M) = ,.. .,aa} 0 2 We note that R al + 1. Let R = {ai,a since Lemma 2.2.2 , 2 a . a, , a} shows a, , a,La}fl{a, aula E R,k, which { implies aa < al + 2 = a. Thus R is the set of values that appear in both the first row and the first column of t. Since the values of R all appear in the first row of , Lemma 2.2.2 gives that R ç For any SSYT of shape S(A, c; k) with lattice reading word and content v, Lemma 2.2.2 shows that the values in the first row of A are distinct, so, when creating a filling of A, the values in R must also appear in both the first row of A and the first column of A. Consider A {a ,a 1 ,.. , aa}—R and A’ = {a, a,. , a_ 2 }—R. Since 1 we know that the values of R must appear in both the first row of A and first column of A, A U A’ contains the remaining values of M that need to be placed in A. In other words, A U A’ is the set of all values aj + 1 that can appear in exactly one of the first row of A or the first column of A. Since Aa > we have Aa > A . Thus we have R <t 1 1 <A 1 <Aa. Now because (3.3) Aa, . . . . . . — . . . . . . . . we can extend the values of R to an increasing sequence b 1 <b 2 < < b by choosing Aa R additional values from (AUA’)flR,k. There are enough values to choose from since there are — Ita — > Aa (3.4) — values of (A U A’) 0 R,k present in the first row of i. The sequence of b’s is strictly increasing since (A U A’) n R = 0. Now M {b ,.. , b} C M R contains w = jMj Aa = [La +j —2— Aa 1 distinct values, each no greater than l + 1. That is, they are an increasing sequence c 1 <c 2 < <cm, where ci,, < al + 1. We have . — 1 A — — = [La+IMAa 50 CHAPTER 3. HOOK FOUNDATIONS — 1+(/a+j2Aa)+(jti_j+1) = so we may fill A as shown below. 1 b 2 b bAa Cl 2 C cw 1 a+ By the definitions of R and the sequence of b, it is clear that b 1 =a 1 = aç. Thus, a . Since the sequence of c is strictly increasing and since 1 1 < c we have od+1 < That is, the first column of A is increasing. We also had so the first row of A is increasing. Hence this filling gives us a SSYT T of shape A L and content ii. We now check that T has a lattice reading word so that we may apply Lemma 2.2.3 to obtain the desired tableau 7 of shape S(A, a<; k). Suppose that T does not have a lattice reading word. Then, when reading the foun dation A of T, we must reach a point where the lattice condition failed. Let x be the value that, when read, caused the lattice condition to fail. The lat tice condition could not have failed when reading the first row of A since the values in the first row of A were distinct values chosen from R,k. Therefore this x appears somewhere in the first column of A. We consider the the two cases x E Ra,k and x RQ,k. Consider the first case, x e Rc,k. If a value of R,k appears only once in the foundation then reading this value cannot violate the lattice condition. Thus, since the lattice condition failed at this x, this x cannot be the first 51 CHAPTER 3. HOOK FOUNDATIONS time that x was read in A. Since the columns strictly increase, the previous x must have appeared in the first row of A and, since the values in the first row are distinct, this is the only other x in A. Since the content of A is the same as the content of p, these two x’s appear in p as well. Using the fact that ‘Jj has a lattice reading word, together with the content of , we find that the value x —1 appeared in p. Thus the value x —1 also appears in A. Now, since the rows and columns of A strictly increase, either the x 1 appears in the first column of A above the entry x, or the x 1 appears in the first row of A left of the entry x. In either case the x 1 is read before the second x is read and the lattice condition will not fail when reading this second x, contrary to our assumption. — — — We now look at the second case, where x R,k. Again, the x we are interested in appears in the first column of A. There cannot be a second x in A since the column strictly increases and x 0 R,k implies that no other x was placed in the first row of A. As before, x must have appeared in p and, in particular, it also appears somewhere in the first column. Since 7j has a lattice reading word we must read a sequence of values t, t + 1, t + 2, x 2, x 1 in p, where t E before we read the x, and we may assume that none of the values t + 1, t +2, ..., x 2, x 1 are from Ra,k. Hence each of the values t, t + 1, ..., x 2, x 1 also appear in A. None of the values t + 1, t + 2, ..., x 1 can appear in the first row of A since the first row was chosen from Ra,k. That is, each value t + 1, t + 2,. . , x 1 appears in the first column of A. Also, since the rows and columns of A strictly increase, either the t appears either in the first column of A above the entry t + 1, or the t appears in the first row of A. In either case the entire sequence t, t + 1, 2, x 1 is read before the x is read in A and the lattice condition ., x does not fail at x, contradicting our assumption. Since T has a lattice reading word, we can now apply Lemma 2.2.3 to obtain the SSYT 7 of shape S(A, c; k) with lattice reading word and con tent xi. Therefore from any SSYT 7 of shape S(p, cv; k) with lattice reading word and content z-’ we can create a SSYT 7 of shape S(A, c; k) with lattice reading word and content xi. — — — — — — — . — — — Let c be the number of SSYT of shape S(A, c; k) with lattice reading word and content xi, and be the number of SSYT of shape S(p, ; k) with lattice reading word and content xi. We shall show that the sets R and AuA’ that were described above are completely determined by the content xi. That is, without starting with a specific tableau, but only starting with the desired content of a SSYT of some fat staircase with hook foundation with lattice reading word, we show how to determine R, the set of values that 52 CHAPTER 3. HOOK FOUNDATIONS must appear in both the first row and first column of the foundation, and determine AU A’, the set of values less than or equal to c + 1 that can oniy appear in one of the first row or the first column of the foundation. Since L is uniquely filled, from ii we can determine the content of the foundation (A, respectively) needed to create a SSYT of shape S([I, a; k) (S(A, c<; k), resp.) with lattice reading word and content v. From the content of the foundation we can determine the values a, a+ greater than c+1. , 1 Since Lemma 2.2.2 shows that the entries in the first row of the foundation strictly increase, any value that appears twice in the foundation must appear in both the first row of u (A, resp.) and first column of (A, resp.). These values, together with the minimum value in the content of the foundation, give the set R. Then A U A’ is the values in the foundation that are less than or equal to c + 1 but are not in R. After determining the remaining entries of the first row of t (first row of A, resp.), the rest of the foundation is ulliquely determined. Now, to actually form a SSYT of shape S(i, c; k) (S(A, c<; k), resp.) with lattice reading word and content ii, we only need to choose the remaining ILa RI (Aa RI, resp.) values from the set (A U A’) fl R,k to place in the first row of ii (first row of A, resp.). Therefore the number of SSYTx of shape , c; k) = ic’/p’ with lattice reading word and content v is given by 1 S( . — . . — Cp_ I” (AUA’)flR,kI [LaIRI — and the number of SSYTx of shape S(A, c; k) word and content v is given by — ( = ic/p with lattice reading (AUA’)flR,kI AaIRI >jij>j—1,wehave 1 SinceAA 0 >j —1 Aa. (3.5) Thus, for each i we have [LaRj [1a_jR_+(j_1_Aa) (ILa_Rj)+(j_1_jR)_(AaR)_j IAI+IA’IAaIRI)j (A U A’) fl R,kI (Aa RI) — — — That is, [La — RI — (Au A’) fl R,kI for each i. 53 (Aa RI) — i, (3.6) CHAPTER 3. HOOK FOUNDATIONS Therefore — CPV — (AuA’)nR,kl! (l(AuA’) flR,kl (Aa IRD)!(Aa j(AuA’)nR,kl! (j(A U A’) fl R,kl (ILa l))!(Ita — — - - aa1 X CPII,X - IRD! IRD! l(AUA’)flRck(AalRD ILaAa1 — - — /ialRH TT i=O — ILaRli ri l(AUA’)flRc,kl(AatRDj > where we have used Equation 3.6 in the final step. Since this inequality holds for all contents ii for which there was a SSYT of shape S(p c<; k) with lattice reading word and content ii, we have SS(,;k) SS(1;k) s 0. • — Finally, we turn to the hooks A, satisfying Aa, ii ri. = h < n + k and Theorem 3.1.4 Let A and p be hooks with Al = $(, <; k). then $(A, k) 1. If and let 0 < k Aa > Aa, ; ri Proof We are given that Aa i’i and we wish to show that S(A, cv; k) >S(jt, c; k). We claim that proof of Theorem 3.1.3, with a few equations verified under the current hypotheses, also proves this theorem. Given the SSYT of shape S(i, cv<; k) with lattice reading word and con tent v, in order to create the SSYT of shape S(A, c; k) with lattice reading word and content ii we needed to check that Equation 3.2, Equation 3.3 and , RI <Aa, and 1 Uj j + 1 <A Equation 3.4 held. Namely, we required that 1 RI > Aa IRI. Since the first two equations were satisfied, we were able to fit the required values into the first row and first column of A. Further, since Ita RI A RI, there were enough values to fill the first row of A, and therefore we could construct the tableau with all the desired properties. In order to show Equation 3.2 holds for the assumptions of this theorem, < A . In order to show Equation 3.3 holds for the 1 we note that In order to Uj < Aa. assumptions of this theorem, we note that RI < 1 we note that of this theorem, the assumptions for show Eiation 3.4 holds Aa. Therefore we can create a SSYT of shape S(A, ; k) with lta lattice reading word and content ii whenever there exists a SSYT of shape S(u, c; k) with lattice reading word and content ii. — — — — ri 54 CHAPTER 3. HOOK FOUNDATIONS Next, the proof of Theorem 3.1.3 checked that, for each of these con tents ii, the number of SSYT of shape S(A, c; k) with lattice reading word and content v is greater than or equal to the number of SSYT of shape SCu, c; k) with lattice reading word and content ii. To prove this, we first required that Equation 3.5 held. Namely, we required that Aa > j 1. We used this equation to show that Equation 3.6 held for each i, which gave us the desired inequality for the Littlewood-Richardson numbers. In order to show Equation 3.5 holds for the assumptions of this theorem, we note that 1. Therefore the inequality for the Littlewood-Richardson Aa > j > j here numbers holds as well, which proves that — — S5(A,o1;k) — S(,o;k) s 3 0. I be hooks with A = = h < n + k and Theorem 3.1.5 Let A and 1. IfS(A,;k) S(,;k), then Aa i. and let 0 k Proof Towards a contradiction, suppose Aa <IM. 1 < r < As before, we let r < Tfl. be the values of Ra,k. We can create a SSYT of shape [1 by filling the boxes of i as follows. 1 r 2 r r r,La+1 r,La+2 rh Since we are using distinct values of R,k, it is easy to check that the resulting tableau of shape jiL has lattice reading word. Thus Lemma 2.2.3 provides o<; k) with lattice reading word, where p is us with a SSYT T of shape filled as shown above. We now wish to count all SSYT of shape S(, c; k) (shape S(A, c; k), respectively) with content ii = c(’T). Since & has a unique way of being filled, we must find all semistandard fillings of (A, resp.) with the values Since r 1 < r < 1 must appear in the ,T 1 r ,. 2 < Th, the value r , rh. top-left corner of i (A, resp.). Further, once we choose 1 (Aa 1, resp.) of the values r 2 < r < u (first row <Th to appear in the first column of 1 remaining must appear in of A, resp.), then the r’s the first row of (first column of A, resp.) and the order of all these values is uniquely determined by the semistandard conditions. Therefore the number of SSYTx of shape S(j, c; k) = ti’/p’ with lattice reading word and content ji = c(’T) is given by . . — K’ Cpu) = (h—i 1 111 — 55 — CHAPTER 3. HOOK FOUNDATIONS and the number of SSYTx of shape S(A, o<; k) word and content ii = c(T) is given by = ic/p with lattice reading (h—i h < we have h + 1 > Aa + Since \a < )‘a > p 1 and we obtain jig. Therefore we have — — (3.7) h)aj>iij, for each i. Therefore (h—i)! — ? 1 C, — — — (h — — 1)! (hi). x (ha)!(\ai)! u 1Licz1 = > 1? c , where we have used Equation 3.7 in the final step. Since we have found a content ii with c 1? > , 1? we can conclude that SS(A,;k) c SS(i,a;k) s 0, which is a contradiction. Therefore we have “a 1M I — We finish this section with a result for the difference where D is a sum of fat staircases and ) is a single row. Theorem 3.1.6 Let D = Ss(\t,D;1) — p/si be such that SD = > uzfat staircase , 1? C,S and ) be a single row. Then we have SS(t,D;1) — SS(,D;1) s Cv(SS(At,a(v);1) 56 — SS((v);i)) s 0. CHAPTER 3. HOOK FOUNDATIONS Proof Applying Theorem 2.3.1 shows that CvSS(A,c(v)<;1), SS(A,D;) s so we have S8(A,D;1) s (3.8) CySS(A,(v);l). — We now intend to show that SS(t,D;1) (3.9) CvSSt,c(v)1;1). = Then, adding Equation 3.8 and Equation 3.9 will give that SS(,D;1) — Cy(SS(At,(v);l) SS(A,D;1) s — SS((v);1)). To prove Equation 3.9, we first note that Theorem 2.3.1 shows that SSt,D;1) s > CvSS(At,(v)<;1). We now recall how the proof of Theorem 2.3.1 proceeded. The proof looked at the map that took a SSYT T of shape S(.At, D; 1) with lattice reading word and c(D) = v to the tableau T’ of shape S(\t, o(v); 1) whose foundation \t was filled identically as in T. Then for each such image T’ the proof showed that 1. T’ was a SSYT with lattice reading word and c(T’) 2. there are at most c, distinct SSYT of shape map to T’. = c(T), and s(At, D; 1) that could Further, the possible tableau of shape $t, D; 1) mentioned in 2 were the tableaux of shape S(At, D; 1) where the filling of ) was identical to the filling of )‘ in T’ and the filling of D was one of the c, semistandard fillings of D with lattice reading word and content ii. We now check that each of these preimages of T’ is a SSYT of shape S(At, D; 1) with lattice reading word. Let T be a preimage of T’. Then the subtableau of ‘T of shape D is semistandard and has lattice reading word since, as just mentioned, it is one of the c, semistandard fillings of D with lattice reading word and content 11. We also have that the foundation ) of T is semistandard since it is filled 57 CHAPTER 3. HOOK FOUNDATIONS indentically to the foundation of T’, which was semistandard. Further, since ) is a single column and k = 1, the foundation of S(At, D; 1) does not appear directly below any box of D. Therefore T is a SSYT. Also, ‘T has a lattice reading word since D has a lattice reading word and, since we have c(D) = c(/()), after reading D the lattice restrictions on T are identical to the lattice restrictions on T’, which has a lattice reading word. Hence, we have shown that each of these c preimages of T’ is a SSYT of shape $)t, D; 1) with lattice reading word. This proves Equation 3.9. That is, S5(At,D;1) = CvSS(At,(v)l;1). We may now combine Equation 3.8 and Equation 3.9 to obtain SS(,D;1) — Cj,(S8(t,a(j,)<;1) SS(A,D;1) s Now, using Theorem 3.1.4 on each pair S8(At,a(v);1) — — SS(,a(v)<;1)). Ss(At,(v)<;1), SS(A,(v);1) gives 0, SS(\,(v)1;1) for each fat staircase a(v). Therefore, we now have that S8,D;1) — SS(A,D;1) s — SS(),(v);l)) s 0. I Example Once again we consider the example with p = (4, 3,3, 3, 3,3,3), = (2, 2, 2, 1, 1), and D = p/n. We have previous seen that D is a sum of fat staircases. Namely, we have SD = ,i,i,i) 2 3 , 4 S( = ) 3211 S( + + ,i,i,i) 2 , 3 S( (313) + S(3,3,2,2,2,1,1) + We now wish to apply Theorem 3.1.6 to this diagram D using ). = (3). ), 3 1 2 , 3 , and ,i, L( ) We are interested in appending A to D and each of L\( At , and ,i, L( ) 3 to D and each of (2,3,2) and also in appending ). Therefore, we are interested in the following diagrams. 3 , 2 L( 58 CHAPTER 3. HOOK FOUNDATIONS Theorem 3.1.6 states that SS(t,D;1) v(Ss(t,a(zi);1) S3(,D;1) s — SS(A,(z,);1)) s 0. In fact if we compute both Cj, (Ss t,(v)<;1) — 1 (Ss(At,(3,2,1,1);1) SS(,a(v) ;i)) i, i;i) , (sspt,( ) + 13 + 1 (ss(At,(2,3,2ya;1) — — and SS(At,D;1) then the difference is given by (Ss(t,D;1) — SS(A,D;1)) — = i,i,i) S( , 2 3 4 , 5 + ( i,i) S( . 2 4 , 5 + C,(ss(At,(v)<;1) . ,i, 2 4 5 S( ) 1 , 59 — — S8(A,(3,2,1,1);1)) i ,3);1)) SS,( , 3 SS,(2,3,2y;1)) CHAPTER 3. HOOK FOUNDATIONS Further, one can also check that Cy(5S(,(ziy;l) 3.2 — SS(A,c(,,))) s 0. Expressions for Schur-Positive Differences We now wish extend the proof of Theorem 3.1.3 to give an exact formula for the difference ssp,;k) SS(u,c;k). In order to state this result we shall find it helpful to think of weak compositions as vectors with non-negative integer , z 1 , z 2 ,. . . , z,) we shall mean 3 entries. When we write the vector z = (z ,z 1 , z 2 ,. . . ‘Zn, 0, 0,0, .. .). We shall only consider 3 the infinite vector z = (z vectors with finitely many non-zero entries and hence we shall only display vectors with finite length, but in this way we unambiguously may add vectors of different lengths. Given a positive integer i, we let e denote the i-th standard basis vec tor. That is, the vector that has its i-th entry equal to 1 and all remaining entries equal to 0. Further, for A being a finite set of positive integers, we let eA = ZaEA ea be the indicator vector of A. Given C C A, C is called a maximal interval ofA ifC is of the form C = {c,c+ 1,c+ 2,...,c+j} 2 of A ,A 1 where c 1, c + j + 1 A. We say that two maximal intervals A 1 fl A 2 = 0. It is clear that any finite set A of non-negative are disjoint if A integers can be decomposed into a finite collection of maximal disjoint inter ,A 1 ,.. . , Am}, and that this collection is unique. Finally, when we 2 vals {A write min(A) we mean the minimum of the set A in the usual sense. That is, min(A) is the smallest number in A. We begin with the following lemma. — — Lemma 3.2.1 Let zi(B, C) a fat staircase, 0 < k < 1, and h = ö+ eB 1. Then h-IBI-IC) + ec + (01, 1 is a partition for each pair of sets B, C satisfying • BC{2—k,3—k,...jnd+1}, CCBflRa,k—min(B), • +1EBifB+Cjh—1, 3 where the B 3 are the maximal disjoint intervals of B, • if B = U= 1B then min(B) E R,k for each j, and 3 where the C 3 are the maximal disjoint intervals of C, • if C = U 1C then min(Cj)—1 EB—Cforeachj. 60 CHAPTER 3. HOOK FOUNDATIONS Proof To begin with, 6 is a partition. We shall think of 6, as being the content of & and show that we can read the remaining h values of ii(B, C) while maintaining the lattice condition. This will prove the result. Adding the content eB corresponds to reading the values of B = U= . 3 1B Since each J3 is a set of consecutively increasing numbers and each min(B ) e 3 R,k, the lattice condition is maintained while reading each of these maximal disjoint intervals. Therefore the lattice condition is maintained while reading all of B. Next, adding the content ec corresponds to reading the values of C = . Since C ç B, this is the second time we are reading each of these 3 1C U values. The fact that each value is in R,k allowed us to read all these values the first time. Now, since each C 3 is a set of consecutively increasing numbers and we have previously read a min(C ) 1 e B C, the lattice condition is 3 maintained while reading each of these maximal disjoint intervals. Therefore the lattice condition is maintained while reading all of C this time. We note that we have not yet added any values greater than al + 1. Finally, adding (O11+’, lh—IBH-IcI) corresponds to reading the sequence al + 2, al + 3,..., i + h Bl IC! + 1. This sequence is non-empty only if BI + CI <h, and in this case we have al + 1 e B. Since al + 1 e Ra,k the lattice condition is maintained while reading these values. Since the reading word is lattice, this implies that — — v(B, C) is a partition. — — = öa + eB + ec + (O’, lh-IBI-IC1) • We can now state a formula for the differences discussed in Theorem 3.1.3. Theorem 3.2.2 Let A and 1 u be hooks with A = p = h < and letO<k<1. Then f1Aa<1ta S,o;k) 8 where the — ((B C) flRa,kl AaC11 — partitions v(B, C) that aB,cs(B,C) 1 ) ((B — — C) flR,kl aCH1 arise are given by zi(B, C) = 6 + and the = S5(jy1;k) coefficients aB,c are given by aB,c— the — n eB + ec 1HBHI0I), + (O’, 1 sum is over all sets B, C such that 61 1 + k and CHAPTER 3. HOOK FOUNDATIONS • BC{2—k,3—k,...,cI+1},CCBflR,k—min(B), • Cj + 1 • B fl Rc,ic, • BI+ICI<h, and c+lEBif Bl+C<h—1, 3 are the maximal disjoint intervals of B, • if B = U= 1 B where the B then minB) e R for each j, and 3 are the maximal disjoint intervals of C, • if C 3 where the C 1C U then minC) 1 B C for each j. — — Proof From the proof of Theorem 3.1.3 we saw that, for a given content ii, a SSYT of shape <; k) with lattice reading word and content 1 exists i, ; k) with lattice reading word and content 1 whenever a SSYT of shape S( v exists. Furthermore, when such tableaux exist, we saw that the number of SSYT of shape S(\, c; k) = tc/p with lattice reading word and content 11 is given by I j(AUA’)flR,kI AaIR and the number of SSYT of shape S(t, c; k) word and content ii is given by — ( = ic’/p’ with lattice reading (AuA’)flRa,k [tajR where, for the given content ii, R was the set of values that must appear in both the first row and first column of the foundation of each diagram, and A U A’ are the values less than or equal to °i + 1 that must also appear in the foundation of each diagram but are not in R. We recall that all but one element of R appear twice in the foundation. Namely, all but the smallest value of R, which is necessarily the top-left entry of each foundation. Let v be such that s,, appears in the difference with non-zero coefficient. We consider the following two cases. Case 1: There is a SSYT of shape S(t, c; k) and content reading word. ‘i with lattice Case 2: There is no SSYT of shape S(, c; k) and content v with lattice reading word. 62 CHAPTER 3. HOOK FOUNDATIONS Case 1 will give rise to the terms s where there is a SSYT with content xi and lattice reading word of both shapes S(p, c; k) and $(A, ; k). Case 2 will give rise to the terms s where there is a SSYT with content ii and lattice reading word of shape S, c; k) but not of shape S(p, ; k). We will see that in each case there exists sets B and C with the desired properties such that v(B, C) = xi and aB,c gives the correct coefficients in the difference. Further, we will see that in Case 1 we also have the properties that C + 1 and Ita lB fl Ra,kI, p and in Case 2 we have the property that either p < C + 1 or I.ta> lB fl R,kl. Therefore, in each case, we shall show that for each term s in the difference there are sets B and C with the properties listed in the statement of the theorem together with these extra properties. Then, conversely, in each case, we shall show that for each pair of sets B and C with the properties listed in the statement of the theorem together with these extra properties on p we will obtain a term Sv(B,c) in the difference. Case 1: Since there is a SSYT of shape S(p, a; k) with content xi and lattice read ing word, Theorem 3.1.3 implies that there is also SSYT of shape S, c; k) with lattice reading word and content xi. Since the content of /. is fixed, the contents of the foundations are equal. If we let C be the values less than or equal to I +1 that appear twice in the foundation we obtain RI = id + 1. Further, if we let B be the set of all values less than or equal to ic + 1 that appear in the foundation, we have B—R = AUA’. Since Lemma 2.2.2 shows that the first row of each foundation strictly increases, each value of C must appear in both the first row and the first column of each foundation. Thus for each content xi we obtain a pair B, C. We now show that the sets B and C have the properties listed in the statement of the theorem together with the two extra properties of this case. By the definition of B we have B ç {1, 2,..., ic + 1}. When k = 0 every box in the foundation occurs below some box of z. Hence, since the columns strictly increase, the value 1 cannot appear in the foundation for k = 0. Thus B C {2,3,...,ij+ 1} fork = 0. Therefore, forD < k < 1. we have BC{2—k,3—k,...,ial-+-1}. 63 CHAPTER 3. HOOK FOUNDATIONS Since the multiset of values B U C all appear in each foundation, we have B+IC<h. Further, if jB + C h 1, then there are entries in each foundation that do not belong to either B or C. By the definition of B and C, these entries must be greater than or equal to cj +2 and then the lattice condition implies that c + 1 must appear in the foundation. That is, — ifB+IC<h—1 then oi-i-leB. Since the values of R appear in the first column of A and appear in the first column of we have Rj < A , p which, since R = C + 1, gives 1 jC +1 < A 1 and jC + 1 III. Since Lemma 2.2.2 shows that each entry of the first row of A and the each entry of first row of p is in R,k we have BflRc,kl Aa and BflRa,k Pa. Decompose C = U 1 C, for disjoint C,. Then, by the definition of C, for each C, min(C,) e C appears twice in the foundation but min(C,) 1 C does not. The lattice condition implies that min(C,) 1 appears in each foundation. Thus we have — — min(C,)—1 eB—Cforeachj. The smallest entry in the foundation is b = min(B), and, as previously mentioned, this value appears in the top-left corner of each foundation. Since both the first row and first column strictly increase, b occurs only once ill each foundation. Hence b C. Since every value of C appears in the first row of the foundation, Lemma 2.2.2 shows that C Ra,k. Also, the definition of B and C implies C C B. Thus we obtain Cc BflR,k—min(B). Now decompose B = U= 1 B, for disjoint B. Since min(B,) 1 B for each j, each value min(B,) 1 does not appear in either foundation. Hence, the lattice condition requires that — — min(B,) e for each 64 j. CHAPTER 3. HOOK FOUNDATIONS Therefore for each content ii we obtain B and C with the desired proper ties. Also, h BI Cl denotes the number of values > c + 2 that appear in the foundation, and the lattice condition shows that these must be the a+h values kl + 2, c + 3, Bl Cl + 1. Altogether, the entries of /, B, C, and the values c + 2, ll + 3, ..., c + h BI CI + 1 make up the entire content v. Hence the content v can be expressed as — — . . ., — — — & + eB + cc + (0’, ih-IBI-ICI) = — ii(B, C). Conversely, for any sets B and C with the properties in the statement of the theorem together with the two extra properties, we show that there exists a SSYT of shape S(p, c; k) with lattice reading word and content v(B, C) = ö, + eB + ec h-IBI-ICI) 1 + (01, To this end we begin by creating a filling of p with content eB + ec + (0101+1, iHBHIC). The steps of creating the tableau are the same as in the proof of Theorem 3.1.3, but are now phrased in terms of the sets B and C. First, we place the h— B— IC values kl+2, c+3,..., o+h— B ICI+1 at the bottom of the first column of p. This adds (0kH’, lh—IBHCI) to our content. We then place min(B) in the top-left box of p and place the values of C in both the first row and first column of p, which we can do since p > p ICI+1. Then we choose PaICH1 values from (B—C—min(B))flR,k, to fill the which is possible since lB fl R,kj p and C U {min(B)} C remaining Pa CI 1 boxes in the first row of p. We place the remaining values of B C — min(B) in increasing order in the remaining boxes of the first column of p. This gives a semistandard filling of p. Moreover, we have C once. This adds placed each entry of C twice and each entry of B ec + eB_c = eB + ec to the content. Together with the unique filling of L, 2 this gives a SSYT T of shape S(p, ; k) and content v(B, C). — — — — — We now show that T has a lattice reading word. Suppose not. Then, when reading the foundation p of T, we must reach a point where the lattice condition failed. Let x be the entry that, when read, caused the lattice condition to fail. The lattice condition could not have failed when reading the first row of p since the values in the first row of p were distinct values chosen from Ra,k. Therefore this x appears somewhere in the first column of p. We consider the the two cases x e R,k and x RG,k. Since the lattice condition failed at Consider the first case, x e this x, this x cannot be the first x to appear in p. Thus there was a previous x in the first row of p. Hence x e C = U . So x e C, for some j. Let 3 1C 65 CHAPTER 3. HOOK FOUNDATIONS ). Then t 1 e B C appears exactly once in and each of 3 t = min(C Since the first row and , x C appear twice in the values t, t + 1, first column of i strictly increase, we must read the t 1 before reading the second copy of any of the values t, t + 1,. , x, but then the lattice condition does not fail at x, contrary to our assumption. Now consider the second case, x Rc,k. Since x R,k, Lemma 2.2.2 the first row. Since the tableau is semistandard implies that there is no x in this implies that there is only one x in the tableau. If x < + 1, then Then x E B = U= B. Thus x B for some i. Let t = min(B) e 1 1, —1 also appears in the tableau and, since values value t, , x each of the t+ the first row and first column of t strictly increase, they are read before x. Thus the lattice condition does not fail at x, contrary to assumption. If 1. Therefore cj + 1 e B. Further, x > + 1, then B + C < h Bj the values in t greater than °d + 1 are precisely the h IC values 1, and these all appear the bottom h B C at + + 2, c + 3,..., kI + of the first column of p. Since the o + 1 is read prior to these, the lattice condition could not fail at x, contrary to assumption. — . . — . — . . . . . — — — — — Therefore, in Case 1, the contents v for which there exists a SSYT of shape S(, a; k) with content v and lattice reading word are enumerated pre cisely by the contents v(B, C), where B and C satisfy the properties listed in the statement of the theorem together with the two extra properties. Theo rem 3.1.3 showed that, for these v, there is also a SSYT of shape S, c<; k) with content v and lattice reading word. Furthermore, for S(ji, ; k) = ic’/p’ and ; k) = ic/p, we have that — - — — - (I’ (AuA’)nR,k ILaIRI ( (B—R)nR,kI ( (B—C)nR,k{—1 JLaCH1 1LaH1 and Cp(B,c) — ( I(AUA’)11?cx,k — — — — ( ‘\ — - ( I1 I(B1?)11?a,k .aCH1 (BC)flRa,k11 )aICH1 66 CHAPTER 3. HOOK FOUNDATIONS This shows that aB,c are the correct coeffiecients for the terms that arise in Case 1. Sv(B,C) Case 2: In this case there is no SSYT of shape S(t, c; k) with lattice reading word and content v. However, we are assuming that content v is such that the Schur function s appears in the difference with ion-zero coefficient. Therefore there is a SSYT of shape S()i, c; k) with lattice reading word and content v. Following the same reasoning as in Case 1 we find that there exists sets B and C such that • BC{2—k,3—k,...,Io+i},CCBflRa,k—min(B), • +1 • • IB+CH h, and Iod+1 EBif B+C< h—i, 3 are the maximal disjoint intervals of B, 3 where the B • if B = U 1B ) e R for each j, and 3 then min(B • if C = IJL 1 C, where the C, are the maximal disjoint intervals of C, then min(C,) 1 e B C for each j, — — Furthermore, given such sets, the only two ways there could not exist a SSYT of shape S(i, c; k) with lattice reading word and content v(B, C) is • there was not enough room in one of the first row or first column of to fit all of C and min(B), or t • after placing min(B) and the values of C in the first row of , there were not enough elements of (B C min(B)) fl R to fill the rest of the first row of j. — — Since I-ti < ILa, the first case implies that R,k fl B, the second case implies that uj < C + 1. Since min(B) U C C B fl Rc,k <1ta. Therefore all the desired properties are satisfied. Conversely, if we are given any sets B and C satisfying the properties listed in the statement of the theorem together with either < Cj + 1 or following the same method as in Case 1 we can show I BflRcx,k </La, then by 67 CHAPTER 3. HOOK FOUNDATIONS there is a SSYT of shape $)j, c; k) with lattice reading word and content v(B, C). Moreover, since either p < Cl + 1 or lB fl Ra,kl < Pa, either there is not enough room in the first column of p to fit all of C and min(B) or Lemma 2.2.2 shows that there are not enough values of B to fill the first row of p while satisfying the conditions for a SSYT with lattice reading word. That is, there is no SSYT of shape S(p, ; k) with lattice reading word and content v(B, C). Therefore the contents v for which there exists a SSYT of shape c; k) with content v and lattice reading word but there is no SSYT of shape S(p, a; k) with content v and lattice reading word are enumerated precisely by the contents v(B, C), where B and C satisfy the desired properties of this case. Again, for S(p, c; k) = ic’/p’ and S(A, ; k) = ic/p, we have that — Cp(B,c) — I I(AUA’)flRa,kl — — - l1 (‘ l(BC)flRa,k11 palCH1 and ( — Cp(B,c) — l(AUA’)flRa,kl RI I(B—C)flRk}—1 — ( — - AaICH1 but now, since p > lB fl R,kl where C U {min(B)} iialCH1 > l(BC)flRa,k11, and so — CpI(B,c) — ( I(B—C)flR,kI—1 Pa — CI — 1 c B fl R,k, we have —o — This shows that aB,c are the correct coefficients for the terms arise in Case 2. Thus the formula given for SS(,a;k) 5 Scu,a;k) is correct. — Sv(B,C) that • We now give the formula for the Schur-positive differences discussed in Theorem 3.1.4. Theorem 3.2.3 Let ,\ and p be hooks with Al = and let 0< k <1. If Aa then Aa,pi SS(A,a4;k) — SS(,c;k) 68 = ll = aB,cs(B,c) h < n + k and CHAPTER 3. HOOK FOUNDATIONS where the coefficients — ( aB,c— by aB,c are given I(B—C)flR,kH1 (I(BC)flRa,k1 AaCH1 aICH1 the partitions v(B, C) that arise are given by v(B, C) öa + eB + cc + (O1’, lh-IBI-C), and the sum is over all sets B, C such that • Bc{2—k,3—k,...,jc+1}, CcBnR,k—min(B), • C)+1 BflRa,i, • B+CIh, and a+1 e B ifB+C< h—i, 3 where the B, are the maximal disjoint intervals of B, • if B = U’= 1B min(B) for each j, and then E • if C = U 1 C, where the C, are the maximal disjoint intervals of C, then min(C,) 1 e B C for each j. — — Proof The proof follows as in the proof of Theorem 3.2.2. The only condition on B and C that is different in the statement of this theorem is that we now insist that C + 1 )a instead of jC + 1 This is because Aa < A and all the values of R = C U min(B) must appear in the first row of A. For each v that does appear in the difference, there is one of the two following cases. Case 1: There is a SSYT of shape S(ji, c; k) and content zi with lattice reading word. Case 2: There is no SSYT of shape S(p, reading word. c<; k) and content i’ with lattice As before, in each case there exists sets B and C with the desired prop erties such that v(B, C) = v. This time we can see that in Case 1 we must also have the properties that Pa C + 1 and I-ia B fl and in Case 2 we must also have that either [La < Cj + 1 or 1a> B 69 fl R,kj. CHAPTER 3. HOOK FOUNDATIONS Then the proof that, in each of Case 1 and Case 2, the sets B and C with these desired properties enumerate all partitions v that arise in the difference follows exactly as in the proof of Theorem 3.2.2 using Theorem 3.1.4 in place of Theorem 3.1.3 when appropriate. Also, it once again easy to see that, in each case, the numbers aB,c are the correct coefficients of ii(B, C) in the difference. • Example Let a (1,1,1,1), ) = (2,1,1), interested in the following two diagrams. = SQ, a; 0) For this a, k, we have R,k SS(A,1;O) = — = (3,1) and k = 0. We are S(t, a<; 0) {2, 3, 4, 5}. Thus Theorem 3.2.3 gives SS(,&;O) = aB,cs(B,c), where • B C {2, 3,4, 5}, C C {3, 4, 5}, • lCj+12Bl, • lBl+jCl<4,and5EBiflBl+lCI<3, • if B = U= 3 where the B 3 are the maximal disjoint intervals of B, 1B then min(B ) e R for each j, and 3 • if C = U 3 where the C 3 are the maximal disjoint intervals of C, 1C then min(C ) 1 E B C for each j. 3 — — The condition Cl + 1 < 2 gives Cl < 1, and this implies that C is empty, or C is a singleton. If C = {c} is a singleton then IBI + Cl < 4 gives that lBl<3.SinceCCBandmin(C)—1B,wehave{c—1,c}CB.Also, if we assume BI = 2 then BI + IC! < 3, so we require that 5 e B, which implies that C = {5}. Hence, for singleton sets C, we have either 1. C = {3} or C = {4} and BI = 3, or 70 CHAPTER 3. HOOK FOUNDATIONS 2. C = {5} and B <3. If C = {3}, then {2, 3} C B, so the possibilities for B are the sets {2, 3, 4} B, so the possibilities for B are the and {2, 3, 5}. If C = {4}, then {3, 4} sets {2, 3, 4} and {3, 4, 5}. In each of these four cases we can compute aB,c — — ( (B—C)nR,kJ—1 (j(B—C)nR,kj—l taCH1 AaICH1 )_ 2—1 2—1 2—1—1)3—1—1 ( = - (i ( (1 - =1-1 =0. If C = {5}, then {4, 5} C B, so the possibilities for B are the sets {4, 5}, {2,4,5} and {3,4,5}. When B is either {2,4,5} or {3,4,5} we once again obtain ((B—C)nR,kI--1 I I(B—C)flR,k—1 aB,c AaCH1 /aCH1 )_ ( 2—1 “ ( 2—1 3—1—1 2—1—1) — — — — — - (1 (1 - =1-1 =0. When B = aB,c {4, 5} we have — — — — - ( (B—C)flR,k—1 ( (B—C)nR,k—1 aCH1 aCH1 )_ 1 1—1 ‘\ ( 1—1 2—1—1 )3—1—1 (o (0 - =1-0 1. = 71 CHAPTER 3. HOOK FOUNDATIONS This completes the cases when C is a singleton. The only other cases occurwhenC=O. Therefore the possible sets B are {2,5}, {3,5}, {4,5}, {2,3,5}, {2,4,5}, {3, 4, 5}, and {2, 3,4, 5}. When B is one of {2, 5}, {3, 5}, or {4, 5} we have — aB,c — — — - ((B—C)nR,k—1 N (I(B—C)flR,kH-1 iaICH1 aCH1 ( 2—1 N 1 2—1 2—0—1}3—0—1 (iN (1 - =1-0 when B is one of {2, 3, 5}, {2, 4, 5}, or {3, 4, 5} we have aB,c — ( ,k—1 0 (B—C)nR ( N XaICH1 — — — - N (I(B—C)flR,k—1 ialCH1 ( 3—1 3—1 2—0—1)3_0_1 (2N (2 - =2-1 =1, and when B is {2,3,4,5} we have aB,c — ( (B—C)nR,k—1 — — - N aICH1 — I N (B—C)flR,kI—1 i-’aCH1 1 4—’ 4—’ 2—0—1)3—0—1 (3N I (3 - =3-3 =0. 72 CHAPTER 3. HOOK FOUNDATIONS Thus we have SS(,1;O) — SS(,c;O) aB,cs(B,c) = = 1S({ } 5 , 4 },O) 5 , 2 ,{5}) + 1S({ + 1S({ },O) + lSv({ 5 , 3 },O) 5 , 4 + 1S({ },O) + lSti({2,4,5},Ø) + 1S({3,4,5}.O) 5 3 , 2 = + S(4, , 2 , 3 2,1) +S( , 3 , 4 i,i,i) S( , 2 , 4 l,1,1,l) + + S( , , 4 2,2,l,l) + S( , 3 , 4 3,l,,l,l) + S(4,3,2,2,l,l,l) S( , 3 , 4 3,2,,l), where we have omitted the details of computing v(B, C) for each B, C. For an example of this, we have zi({4, 5}, {5}) (1,1,1,1) + e + bE{4,5} = = 3.3 e + (Os, 14_2_1) c{5} (4,3,2,1)+ (o,O,o,1,1)+(o,o,o,o,1)+(o,o,o,o,o,1) (4,3,2,2,2,1). Hasse Diagrams for k> 1 In Sections 3.1 and 3.2, we required that 0 < k < 1. For these two values the Hasse diagram we obtained in Section 3.1 was identical and we could explic itly compute the Schur-positive differences in the diagram. As a byproduct, we could then express D as a skew shape of the form D = That is, the partition removed from 1 u was a fat staircase. This fact will become necessary for our results in Chapter 5. However, we can generalize the hook foundation results of this chapter by relaxing the restriction on k. We return to the case of fat staircases with hook foundations. As before, we let ,tt be the hook ([ta, 1’), ) be the hook (a, 1’) and & be a fat staircase, where c = (ui, c ,. , 2 Now we consider any k satisfying 0 < k h, where h is the size of the hooks under consideration. We shall summarise all the relationships between diagrams of the form S, c; k) when A is a hook of fixed size h < n + k and 0 < k < h. The restriction h < n + k is needed to guarantee that S(A, c; k) is a skew diagram for every hook A of size h. We impose the restriction k < h since, for k h, every diagram of the form S(A, ; k), when A is a hook of fixed size k, is disconnected. Thus, for each k > h, the skew Schur function of . . 73 CHAPTER 3. HOOK FOUNDATIONS these diagrams factor as SS(A,o1;k) = S)S. In particular SSf),cy1;k) = SS.,c;h) for all k so there is no change among the differences for k h. Further more, we shall see that for k h, none of the differences is Schur-positive. Let us begin with the following example. Example For each 0 k < 6 we show the Hasse diagrams for on the collection of staircases with bad foundations S(A, c; k) for some o = (,. . . , c) where n> 6, and A varying over all hooks of size 6. SS(,o;/c) S( ,o;k) 8 S5(tJ,c;k) i i v;k) k=0,1 SS(H iii i,c;k) 11111 ,c;k) 74 CHAPTER 3. HOOK FOUNDATIONS S3(,&;/c) SS(JQi;k) S(fl,&;k) 8 Ss( i i hc;k) k=2 I I I SS(j I I I I I k) S(,c;k) 8 SS(J&a;k) SS(IJ,a1;k) I I k=3 SS(H III i,a;k) 1 I I I I I Ss( 75 CHAPTER 3. HOOK FOUNDATIONS SS(,c;k) SS( ,cx;k) SS(J1,cx;k) SS(U I k=4 S.5(H ,c;k) 1 SS( SS(,cy1;k) SS(Jo1;k) I I I ,c;k) SS(LJ,c1;k) I I a;k) k=5 SS(H iii i,;k) 1 SS( 76 liii ,c;k) CHAPTER 3. HOOK FOUNDATIONS SS(,c1;k) SS(jc1;k) SS(D,c1;k) SS( I k>6 I I I i,&;k) SS(i 11111 For 0 k 1 we have the same structure of the Hasse diagrams that was discussed in Section 3.1. As k increases, fewer of the relations remain satisfied. Finally, when k 6, there are no Schur-positive differences among these diagrams. We note that the chain structure that was prevalent among the diagrams on the right for 0 k 1 also lost its structure as k increased. In particular, when k = 4, each of the three diagrams on the right still was comparable to at least one of the others, but the three no longer formed a chain. The following results summarise all the ? relationships between diagrams of the form S, c; k) when A is a hook of fixed size h < n+k and 0 < k < h. For each pair of hooks A, with Aa, ILa Theorem 3.3.1 and The orem 3.3.2 each prove one side of the Schur-incomparability of this pair, thus describing the antichain structure displayed along the top of the Hasse diagrams in the previous example. For each pair of hooks A, ,u with < Aa < ILa, Theorem 3.3.3 and Theorem 3.3.4 shows that S(A, ; k) >- S(i, c; k) if and only if Aa p + k 1. This describes the relations among those diagrams displayed on the right of the Hasse diagrams in the previous example. Finally, for each pair of hooks A, i with Aa, ,u <j Theorem 3.3.5 and Theorem 3.3.6 shows that when 1 < k < h we have ‘\a > p + k 1 if and [ii, — ], — 77 CHAPTER 3. HOOK FOUNDATIONS if and only if S, c; k) , <; k), and when k 1 S( 0 we have Aa > only if S(A, c; k) ?r S(j, 1; k). This describes the relationships between the diagrams displayed on the right with the diagrams displayed along the top in the previous Hasse diagrams. Let us finally begin. We start by looking at the antichain structure. = h Theorem 3.3.1 Let A and t be distinct hooks with Aj = n+k and < k < h. Then we have and let 0 S(, k) S(A, </2a c; c; k). ri Proof We shall show that there exists a SSYT T of shape SA, c; k) with lattice reading word such that there is no SSYT of shape S(t, c; k) with lattice reading word having the same content. This is sufficient to prove the theorem. Let r 1 = Since Aa < /La and Al = [II, we have A > = = rk = 1 and let rl+k < r2+k < greater than 1. We < Tfl be the values of can create a SSYT of shape A by filling the boxes of A as follows. .•• 1 r rk rl+k r2+k +1 rAa_1 1 Ic + A Using the unique filling of L, it is easy to check that the resulting tableau of shape A Li,- has lattice reading word since each of the entries in the first row of A are from Rc,k and the entry 1 appears k times. Thus Lemma 2.2.3 provides us with a SSYT T of shape S(A, c; k) with lattice reading word, where A is filled as shown above. Since p < A , we have l(S(,u, c; k)) = c + j < c + A. Therefore no 1 SSYT of shape S(u, c; k) with lattice reading word can contain the entry c +A . Thus no SSYT of shape S(ji, c; k) with lattice reading word can 1 have the same content as T. Hence, it follows that SS(L,;k) S8(X,1;k) s 0. — I Theorem 3.3.2 Let A and be distinct hooks with Al = and let 0 < k < h. Then we have S(A, a<; k) Aa <Ia ri = h n+k and S(i, a; k). Proof The proof for k = 0 was proved in Theorem 3.1.2. Thus we consider the case when k > 0. We let r 1 = = < rfl+k be the rk = 1 and let r+k < r2+k < values of R,k greater than 1, where we note n + k h. We can create a SSYT of shape jt by filling the boxes of u as follows. ... 78 CHAPTER 3. HOOK FOUNDATIONS 1 r rk rl+k r2+k Ta+l rh 2 = 1 and rl+k < Since r = r < < rh are distinct values = check that resulting of R it is easy to the tableau of shape p & has ,k, 1 lattice reading word. Thus Lemma 2.2.3 provides us with a SSYT T of shape S(p, c; k) with lattice reading word, where p is filled as shown above. We now wish to count all SSYTx of shape S(p, c; k) (shape $(A, c<; k), respectively) with content ii = c(’T). Since & has a unique way of being filled, we must find all semistandard fillings of p (A, resp.) with the values , r 1 r ,. 2 Since r 1 = = 1 and T1+k < r2+k < , rh. < rh, = rk the values r , r 1 ,. 2 , rk must appear as the first k values of the first row of p (A, resp.). Further, once we choose p k (Aa k, resp.) of the values , rh to appear in the first row of p (first row of A, resp.), then r1+k, r2+k, the remaining r’s must appear in the first column and the order of all these values is uniquely determined by the semistandard conditions. Therefore the number of SSYTx of shape S(p, c; k) = i’/p’ with lattice reading word and content v = c(T) is given by . . . . — — . p’ii = (h—k ‘\ Pa k — and the number of SSYTx of shape S(A, ; k) word and content ii = c(T) is given by = ic/p with lattice reading (h—k CPv=k\Aa_k h <ri, — Since Aa <Pa we have Aa+pa < h+1 < h+k. Therefore we have k and we obtain Aa > Pa — hAai>pakj, for each i. Therefore jçl = (h — (h—k)! pa)!(pa — k)! 79 (3.10) CHAPTER 3. HOOK FOUNDATIONS IL LII — = — li). (h_Aa)!(Aa_k)!X fjj/ ‘1 TT — [Lak [Lak2 > cv, where we have used Equation 3.10 in the final step. Therefore SSu,1;k) s 0. I SS(A,i;k) — 1. We now depart from looking at the hooks ;\qL satisfying a <[La Instead, we turn to the hooks A, [L satisfying i 5 Aa <[La. The following theorems describe the relations among the diagrams we displayed on the right in our examples. r ri Theorem 3.3.3 Let A and t be hooks with Al = [LI = Ii < n + k and k h. 1fAa [Li+k—1 thenS(A,ci;k) >- S(i,c;k). Aa <[La, and letO Proof To prove the result, we shall consider any content v such that a SSYT of shape S([L, c; k) with content v and lattice reading word exists. First we shall show that there is also a SSYT of shape S(A, c; k) with content i’ and lattice reading word. Then, letting S(A, c; k) = ic/p and S([L, c; k) = i’c’/p’ for partitions ic, ic’, p, and p’, we shall show that the Littlewood-Richardson coefficients for these two diagrams and this content satisfy CL) : Having shown that this inequality holds for any content v for which a SSYT of shape S([L, c; k) with content v and lattice reading word exists, this will imply that SS(A,;k) Ss(,a1;k) s 0. — Let ii be a content such that there is a SSYT 7j of shape S([L, ; k) with content v and lattice reading word. By Lemma 2.2.2 we know that the first row of contains at most k l’s. Let q be the number of l’s in the first row of . In the case that q = 0, then we may follow the proof of Theorem 3.1.3 to show that the inequality holds on the Littlewood-Richardson coefficients on these contents. Thus we consider the case q > 1. We write a 1 = a 2 = = aq = 1. Then the rest of the first row of consists of a strictly increasing sequence aq+1 < aq+2 < < a where each aq+j Ra,k with aq+j > 1. Also, since the columns of 7 strictly increase, the first column of contains a strictly increasing sequence aç < a < < a , where a = a 1 1 = 80 CHAPTER 3. HOOK FOUNDATIONS 1. Since L can only be filled in one way (in both shapes S(i, c; k) and SEA, c; k)) and the values a , 1 a must be placed in the first q positions in the first row of either foundation, in order to obtain a tableau of shape S, c; k) and content ii we only need to show how to place the values of } in 1 { a+i, aq+2,. , a} U {a, a,. a ..., . . . . , If 1(v) > + 1 for this particular content 11 then there are entries of 7j greater than cij + 1. Since & has content öa, the lattice condition implies Since each a E R,k, we have a that 2 < °i + 1 for each + 2 appears in i and so a = c + 2 for some j. The lattice condition and the fact that the column strictly increases gives that . = k+3 = Again, by the lattice condition, it is clear that any SSYT of shape 8, ; k) with lattice reading word and content v must also have these values a, a+ , 1 1 as the last 4 a 1 u j + 1 entries of the first column of A. Since Aa < ILa gives Ii < A , we have ,u j + 1 <A 1 1 j + 1. Since j 2 this gives, — — — (3.11) p—j+1Aj, so these entries do fit in this column. Note that if 1(v) < aj + 1, then this sequence of values a, a+ 1 is empty aild we do not have to worry ,.. a 1 about placing any entries larger than k + 1 into A. (In such a case we may consider j = ILi + 1.) Let M be the multiset {aq+i, aq+2,. a,} U {a, as,. a_}. Then M is the remaining entries that we still need to place in A to obtain a tableau of shape S(A, c; k) and content v. We have Ml = ILa + j 2 q and max(M) = cI + 1. Let R = {aq+1,aq+2,.. .,aa} fl }. We 1 ..,a_ note that R = {aq+i, aq+2,. a} fl {a, a, } since Lemma 2.2.2 1 a shows a,a e R,k, which implies a, < c + 2 = a. Thus R is the set of values (except 1) that appear in both the first row and the first column of 1 tt. Since the values of R all appear in the first row of Lemma 2.2.2 gives that R Rc,k. For any SSYT of shape $(A, <; k) with lattice reading word and content v, Lemma 2.2.2 shows that, besides 1, the values in the first row , . . . . , . , — . . , . . . , , c 81 — CHAPTER 3. HOOK FOUNDATIONS of A are distinct, so, when creating a filling of A, the values in R must also appear in both the first row of A and the first column of A. } R. 1 Consider A = {aq+i, aq+2,. , a,J R and A’ = {a, as,. , a Since we know that the values of R must appear in both the first row of A and first column of A, A U A’ contains the remaining values of M that need to be placed in A. In other words, A U A’ is the set of all values < +1 row A or the first column A. appear exactly one of the first of of that can in We wish to show that (3.12) R <Aaq . . . — . — 1 holds. If q = 0, then R < j < p + 1 < A q. Now, Aa = tt is 1 which is not in R, hence we have when q 1 the top-left entry of 1 < </1 where we have used the fact that Aa /M+k1. R <Aak Aaq, Now, because Equation 3.12 holds, we can extend the values of R to < b by choosing Aa Rj an increasing sequence bq+i < bq < q additional values from (A U A’) fl R,k. There are enough values to choose from since there are — — — (3.13) values of (A U A’) fl R,k present in the first row of ji. The sequence of b’s is strictly increasing since (A U A’) fl R = 0. Now M {bq+i,...,b} C M R contains w = q) = (Aa Ita +j 2 Aa distinct values, each no greater than cj + 1. That is, they are an increasing sequence c 1 < c 2 < < c,,,, where c < c + 1 and c 1 > 1. We have — — — — 1 A = = Ia+IMa 1+(pa+j_2Aa)+(iii_j+1) = 1 so, letting b = = = bq = 1, we may fill A as shown below. b 1 1 c 2 c 2 b ... c 1 a+ 82 bAa — CHAPTER 3. HOOK FOUNDATIONS Since the sequence of cj is strictly increasing and since 1 c > 1 and c wehave c+1 < That is, the first column of A is increasing. We also have ”bql 2 bib and bq+i <bq+2 < so the first row of A is weakly increasing with q < k l’s. Hence this filling gives us a SSYT T of shape A L and content ii. We now check that T has a lattice reading word so that we may apply Lemma 2.2.3 to obtain the desired tableau 7 of shape S, c<; k). Suppose that T does not have a lattice reading word. Then, when reading the foun dation A of T, we must reach a point where the lattice condition failed. Let x be the value that, when read, caused the lattice condition to fail. The lattice condition could not have failed when reading the first row of A since the lat tice condition places no restriction on the number of l’s and the remaining values in the first row of A were distinct values chosen from Rc,k. Therefore x> 1 and this x which violated the lattice condition appears somewhere in the first column of A. We inspect the the two cases x e R,k and x R,k. Consider the first case, x e Ra,k. If a value of appears only once ifi the foundation then reading this value cannot violate the lattice condition. Thus, since the lattice condition failed at this x, this x cannot be the first time that x was read in A. Since the columns strictly increase, the previous x must have appeared in the first row of A and, since the values in the first row are distinct, this is the only other x in A. Since the content of A is the same as the content of 1 u, these two x’s appear in /L as well. Using the fact that 7j has a lattice reading word, together with the content of Z, we find that the value x 1 appeared in 1 u. Thus the value x 1 also appears in A. Now, since both the rows and columns of A must weakly increase, either the x 1 appears in the first column of A above the entry x, or the x 1 appears in the first row of A left of the entry x. In either case the x 1 is read before the second x is read and the lattice condition will not fail when reading this second x, contrary to our assumption. We now look at the second case, where x R,k. Again, the x we are interested in appears in the first column of A. There cannot be a second x in A since the column strictly increases and x R,k implies that no other x ‘ — — — — — 83 CHAPTER 3. HOOK FOUNDATIONS was placed in the first row of A. As before, x must have appeared in i and, in particular, it also appears somewhere in the first column. Since 7j has a lattice reading word we must read a sequence of values t, t + 1, t + 2, x 2, .x 1 in t, where t e R, before we read the x, and we may assume x 2, x 1 are from R,k. Hence that none of the values t + 1, t + 2, x 2, x 1 also appear in A. None of the each of the values t, t + 1, appear in the first row of A since the first x 1 can 2, 1, t values t + + x 1 appears row was chosen from R,k. That is, each value t + 1, t + 2,. in the first column of A. Also, since both the rows and columns of A must weakly increase, either the t appears in the first column of A above the entry t + 1, or the t appears in the first row of A. In either case the entire sequence x 2, z 1 is read before the x is read in A and the lattice t, t + 1, condition does not fail at x, contradicting our assumption. Since T has a lattice reading word, we can now apply Lemma 2.2.3 to obtain the SSYT 7 of shape S(A, c; k) with lattice reading word and con tent v. Therefore from any SSYT ‘Jj of shape S(z, c; k) with lattice reading word and content v we can create a SSYT 7 of shape S(A, c; k) with lattice reading word and content z-’. — — ..., ..., ..., — — — — — . ..., — . , — — Let be the number of SSYTx of shape S(A, o; k) with lattice reading word and content v, and c be the number of SSYTx of shape S(i, c; k) with lattice reading word and content v. We shall show that the sets R and AuA’ that were described above are completely determined by the content v. That is, without starting with a specific tableau, but only starting with the desired content of a SSYT of some fat staircase with hook foundation with lattice reading word, we show how to determine q, the number of l’s in the foundation; R, the set of values larger than 1 that must appear in both the first row and first column of the foundation; and A U A’, the set of values less than or equal to c + 1 that can only appear in one of the first row or the first column of the foundation. Since L is uniquely filled, from v we can determine the content of the foundation 1 u (A, respectively) needed to create a SSYT of shape S(,u, c; k) (S(A, c; k), resp.) with lattice reading word and content v. From the content of the foundation we can determine q, the number of l’s in the foundation, and the values a, a+ + 1. Since Lemma 2.2.2 shows ,... greater than 1 that the entries greater than 1 that appear in the first row of the foundation strictly increase, any value greater than 1 that appears twice in the founda tion must appear in both the first row of ,tt (A, resp.) and first column of (A, resp.). These values give the set R. Then AU A’ is the set of values in the foundation that are both greater than 1 and less than or equal to c + 1, but 84 CHAPTER 3. HOOK FOUNDATIONS are not in R. The first row of t (first row of ), resp.) must contain q l’s and the values in R. After we determine the remaining entries of the first row of (first row of )., resp.), the rest of the foundation is uniquely determined. Now, to actually form a SSYT of shape S(u, ; k) (S(A, c; k), resp.) with lattice reading word and content ii, we only need to choose the remaining to place [La q RI P’a q IRI, resp.) values from the set (AU A’) fl in the first row of i (first row of ), resp.). Therefore the number of SSYTx of shape S([L, c; k) = ii’/p’ with lattice reading word and content ii is given by (A u A’) fl RQ,k I Cp_ ( — — — — and the number of SSYTx of shape S, ; k) word and content ii is given by — I = ic/p with lattice reading I(AUA’)flR,kI aqRI Since)a)j >[Ljj—1,wehave O>j1m\a. (3.14) Thus, for each i we have [LaqRi [LaqRi+(j1\a) ([La_jRI)+(j_l_IRI)_(Aa_R)_i_q > I(AUA’)flRk_(Aa_IRI)_i_q. That is, [La — q — RI — i (Au A’) fl RQ,kI (a — RI) — i — q, for each i. Therefore — CPV — I(AUA’)nR,kI! (I(AUA’)flRQ,kI (aq IR))!(Aaq_ IRD! (AuA’)nR,kj! — — - (I(AUA’)flR,kI ([Laq R))!([L-q- RI)! ILaAa1 x fJ (A U A’) fl Ra,kI 85 — (Aa — RI) — — q (3.15) CHAPTER 3. HOOK FOUNDATIONS aa1 _CP!VX TT (AuA’)nR,k(Aa—jR—i—q > where we have used Equation 3.15 in the final step. Since this inequality holds for all contents v for which there was a SSYT of shape S(i, ; k) with lattice reading word and content ii, we have SS(,o;k) SS(j,;k) s 0. • — Theorem 3.3.4 Let A and u be hooks with jA = < A < iLa, and let 0 < k < h. If S(A, c; k) Aa iii + k—i. Proof Since ri Aa <Ita, where A = ri < = h < n + k and S(, c<; k), then h, we have Aa < In the case k = 0 we only need to show that Aa IM 1, which is true since Aa and [Lj We turn to the case 1 k h. Towards a contradiction, suppose Aa <k + Lj —1. As before, we let r 1 = rk = 1 and rk+1 < rk+2 < < be the values of Ra,k greater than 1. We can create a SSYT of shape i by filling the boxes of 1 tt as follows. — ... 1 r 2 r rk rk+1 ra+l 2 ra+ Th Since we are using k l’s followed by distinct values of R,k, it is easy to check that the resulting tableau of shape t has a lattice reading word. Thus Lemma 2.2.3 provides us with a SSYT T of shape S(t, ; k) with lattice reading word, where j is filled as shown above. We now wish to count all SSYTx of shape S([t, c; k) (shape S(A, c; k), respectively) with content v = c(T). Since has a unique way of being filled, we must find all semistandard fillings of p (A, resp.) with the values ,r 1 r , 2 Since r = 1 = , rh. , 2 , r 1 = Tk = 1, the values r rk must appear in the first k positions of the first row of p (A, resp.). Further, once we choose Pi 1 (Aa k, resp.) of the values rk+1 < rk+2 < < rh to . . . ..., — — 86 ______ CHAPTER 3. HOOK FOUNDATIONS appear in the first column of ,u (first row of )s., resp.), then the remaining r’s must appear in the first row of t (first column of ), resp.) and the order of all these values is uniquely determined by the semistandard conditions. Therefore the number of SSYTx of shape S(ji, c; k) = a’/p’ with lattice reading word and content v = c(’T) is given by , = (h—k IM 1 I4 — and the number of SSYTx of shape S, c; k) word and content v = c(T) is given by jç = ic/p with lattice reading (hk CPV=\,)a_k Since <A <r1 a <ita, where [Li+Aa <Ai+\a This gives h — ) > ,u — = h, we have h+1. 1 and we obtain hAaj>/j1j, (3.16) for each i. Therefore (h—k)! +1)!( (h—k— — 1 1)! cp,v (hk). (hAa)!\ak)! = c1)x > cv, j p—1—i where we have used Equation 3.16 in the final step. Therefore SS,<;k) 0, which is a contradiction. Therefore we have S5(<;k) 1. /M + k — I Finally, we turn to the hooks A, 4 u satisfying Aa, ii 87 ri. CHAPTER 3. HOOK FOUNDATIONS Theorem 3.3.5 Let A and u be hooks with = Ifi < k < h and Aa S 8 >, ;k). ( then S(;\,c;k) 1 Ifk=O andAa > Proof The case k = h < n + k and 0 was proved in Theorem 3.1.4. For 1 < k < h we are given that ‘\a + k—i and we wish to show that i, ; k). We claim that proof of Theorem 3.3.3, with a few 1 S( SA, c; k) equations verified under the current hypotheses, also proves this theorem. Given the SSYT of shape S([L, c; k) with lattice reading word and con tent 1/, ill order to create the SSYT of shape S(A, c; k) with lattice read ing word and content ii we first needed to check that Equation 3.11, Equa tion 3.12 and Equation 3.13 held. Namely, we required that [Li j + 1 <As, Rj q. Since the first two equations Rj q Aa Aa q, and [La were satisfied, we were able to fit the required values into the first row and first column of A. Further, since [La q Aa jR q, there were of enough values to fill the first row A, and therefore we could construct the tableau with all the desired properties. In order to show Equation 3.11 holds for the assumptions of this theorem, . In order to show Equation 3.12 holds for the 1 A we note that [Li assumptions of this theorem, we note that — — — — — — — — — — In order to show Eqjation 3.13 holds for the assumptions of this theorem, > Aa. Therefore we can create a SSYT of shape we note that [La S(A, ; k) with lattice reading word and content ii whenever there exists a SSYT of shape S([L, c; k) with lattice reading word and content Next, the proof of Theorem 3.3.3 checked that, for each of these con tents v, the number of SSYTx of shape S(A, c; k) with lattice reading word and content ii is greater than or equal to the number of SSYTx of shape To prove this, we first S([L, ; k) with lattice reading word and content required that Equation 3.14 held. Namely, we required that Aa > j 1. We used this equation to show that Equation 3.15 held for each i, which gave us the desired inequality for the Littlewood-Richardson numbers. In order to show Equation 3.14 holds for the assumptions of this theorem, we note that — Aa[Li+k1 j1+k1 j1. Therefore the inequality for the Littlewood-Richardson numbers holds here as well, which proves that — SS(j,;k) 88 s 0. • CHAPTER 3. HOOK FOUNDATIONS Theorem 3.3.6 Let A and be distinct hooks with ) If 1 <k < h andS(A,c;k) If k = 0 and S, cr; k) >— $(i, c; k), then Aa [tj. ri. Proof The case k = = = h < n+k and 0 was proved in Theorem 3.1.5. k h. Towards a contradiction, suppose We turn to the case 1 Aa < k + IM 1. 1 = r 2 = = 1 and r 1 < As before, we let r < rfl < = be the values of Ra,k greater than 1. We can create a SSYT of shape JL by filling the boxes of as follows. — 1 r 2 r r r rk+1 Th Since we are using k l’s followed by distinct values of R,k, it is easy to check that the resulting tableau of shape t & has a lattice reading word. Thus Lemma 2.2.3 provides us with a SSYT ‘T of shape S(i, c; k) with lattice reading word, where u is filled as shown above. We now wish to count all SSYTx of shape S(i, c; k) (shape SA, c; k), respectively) with content ii = c(T). Since L has a unique way of being filled, we must find all semistandard fillings of (A, resp.) with the values 1 = r ,r 1 r ,. , rh. Since r 2 2 = , r 1 , 2 = rk = 1, the values r , rk must appear in the first k positions of the first row of i (A, resp.). Further, once 1 (Aa k, resp.) of the values rk+1 < rk+2 < we choose [Lj < rh to appear in the first column of (first row of A, resp.), then the remaining r’s must appear in the first row of jt (first column of A, resp.) and the order of all these values is uniquely determined by the semistandard conditions. Therefore the number of SSYTx of shape S(, c; k) = ic’/p’ with lattice reading word and content v = c(’T) is given by . . ... — — = (h—k 1 — and the number of SSYTx of shape S(A, c; k) word and content v = c(’T) is given by (h—k CPV=k\Aa_k 89 = ii/p with lattice reading CHAPTER 3. HOOK FOUNDATIONS <r1, we have h+1 Since Aa,i Aa+i. If we have h+1 = = Using the fact then this implies that h is odd and A = = = well. Therefore as A = = h implies A 1 = that ) = = However, we are only interested in distinct hooks A and i. Thus, among distinct pairs A and 1 u, we cannot have h + 1 = Aa + /Jj. <[, we have h + 1 > Aa + This gives , with Aa, for A Thus 1 and we obtain h Aa > ri ri — — 1j, 1 hAaj>/1 (3.17) for each i. Therefore — cp,v — (h—k)! +1)!( (h—k— — 1 1)! (h k)! (h_Aa)!(Aa_k)!X h — i)a+k2 =c pv i. It — Aa — — Aa — i i X i—O > cv, where we have used Equation 3.17 in the final step. Therefore ss(A,;k) 0, which is a contradiction. Therefore we have Aa I-’i + k 1. SS(,i,c;k) I 90 Chapter 4 Differences of Transposed Foundations In this chapter we shall oniy work with the regular staircase We shall use the notation S, k, n) for a staircase with bad foundation as defined in Section 2.1. We shall look at differences of skew Schur functions of the form SS(Xt,k,n) SSc),k,n), where ) is restricted to be a partition with one part or two parts. In both cases the difference is seen to be Schur-positive. Further, we find a simple expression for the difference in the case when ) has a single part, from which we can see that the difference is multiplicity-free. — 4.1 Single Part Partitions The Schur-positivity and formula stated in the following result are a special case of Theorem 3.2.3. We see fit to re-examime this special case since the formula for the difference is easy to state and compute and the difference is seen to be multiplicity-free. Theorem 4.1.1 Let n be a positive integer, 0 < k < 1, and ) be a partition consisting of a single part such that ) <k + n. Then 1. SSt,k,n) 2. SS(At,k,n) 3. SS(At,k,n) n+2 Ss,k,n) — Ssp,k,n) s n+1 SS(A,k,n), 0, and if;\ )t• Furthermore, we have SSt,k,n) — SS(,k,n) = AC{2—k,3—k,...,n} 91 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS where zí(A) = + e + multiplicity-free. Example Let n two diagrams. = 4, ) = (On, In particular, 1”—I’). (3), and k SS(t,k,n) — SS)..,k,n) ‘S 0. We are interested in the following = $t,o,4) S,0,4) Theorem 4.1.1 gives ) 4 SSt,O, — ) 4 Ss(,o, = Sv(A) A C {2,3,4} Sv(O) = + Sv({2}) S(4,3,2,i,1,1,i) + + }) 3 Sv({ + S(4,4,2,i,1,1) Sv({4}) + S(4,3,3,i,i,i) + S(4,3,2,2,i,i), where we have omitted the details of computing v(A) for the various A. For an example of this computation, we have = e + (Ok, 13_i) 4+ S aE{2} = = (4,3,2,1)+ (0,1,0,0)+(0,O,0,0,1,i) (4,4,2,1,1,1). Proof (of Theorem 4.1.1) 1. To prove the Schur-positivity of S5(At,k,fl) S,k,n) we show that any 5 SSYT Ti of shape SA, k, n) with lattice reading word gives rise to a SSYT 7 of shape $)t, k, ri) with lattice reading word and the same content. We then show that we can recover Ti from 7. Consider any SSYT Tj of shape S(A, k, n) with lattice reading word. Lemma 2.1.1 implies that the foundation ) contains a strictly increasing sequence ai < a 2 < 1 where aA <a n + 1 by the lattice condition. 1 — 92 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS Since a 1 < a 2 < , we can create a SSYT of shape )t by transpos 1 <aA ing the entries of the foundation A. Thus we have a SSYT of shape A Suppose the tableau did not have a lattice reading word. Then, since the content of was (n,ri— 1,...,3,2,1) and a < n+ 1 for each i, we would require two of the a to be equal. Since the a are distinct, this tableau does have a lattice reading word. Then, we may apply Lemma 2.2.3, we obtain a SSYT 7 of shape S(At, k, n) with lattice reading word. Furthermore, we may recover 7j from 7 by transposing the entries of the foundation A of 7. This completes the proof that ssp.t,k,n) SS(A,k,n) s 0. — 2. As discussed in the introduction, using the Littlewood-Richardson rule to compute the skew Schur functions in n + 1 variables reduces the usual Littlewood-Richardson rule to considering only those fillings that use num bers from the set {1, 2,. , n + 1}. We now show that we can reverse the process described in the proof of 1 when we restrict to fillings using these numbers. So we take any SSYT 7 of shape S(At, k, n) with lattice reading word whose entries are from the set {1, 2,.. , n + 1}. Therefore, the foun dation At consists of a strictly increasing sequence a 1 < a < < a 1 and 1 <ri + 1. a As before, we can check that the tableau of shape A has lattice reading word. If not, then since the content of L was (n, n 1, , 3, 2, 1) and a < n + 1 for each i, we would require two of the a to be equal. Since the a are distinct, this tableau does have a lattice reading word. We may now use Theorem 2.2.3 to obtain a SSYT Ti of shape SS(,k,n). Also, we can recover the tableau 7 from ‘Ti by transposing the entries of the foundation A. This shows that SS,k,n) SS(At,k,n) 0 as functions in This and 1 completes the proof that n + 1 variables. SSt,k,n) n+1 SS,k,n). .. . — . . . — 3. At then A If A 1 2. Therefore At consists of a column of length A , 1 where 2 < A 1 < n + k. We shall fill the last two spaces of the column with n + 1 and n + 2, and then fill the remaining A 1 2 spaces with 2 1 k, 3 k,. , A 1 k. That is, we fill the column with the entries 2 k,3 k,...,A 1 —1 k,n + 1,n + 2. This filling gives rise to a SSYT of shape S(At, k, n) with a lattice reading word. Further, no SSYT of shape S(A, k, n) with the same content can have a lattice reading word since the lattice condition implies that the n + 1 lies to the right of the n + 2 and this violates the fact that the row weakly increases. — — — . . — — — — — This completes the proof of 1, 2, and 3. We now show that the formula 93 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS stated for Sspt,k,n) SS,k,n) is correct. From 2 we know that the only terms s with non-zero coefficient that appear in the difference have 1(v) n + 2. n + 2. No SSYT of shape S(A, k, n) Let ii be any partition with 1(v) with lattice reading word and content v exists since the lattice condition requires that both the values n + 1 and n + 2 appear in A, but the lattice condition also requires the n + 1 appears to the right of the n + 2 and this violates the fact that the row weakly increases. Any SSYT of shape s(At, k, n) with lattice reading word and content ii must contain both the values n + 1 and ii +2 in At. These appear one above the other in At. The lattice condition implies that any values below the entry ii + 2 in At, assuming there are any, must be the values n + 3, n + 4, until the end of the column is reached. The values of At above the entry n + 1 form some set A C {1,2,...,n}. In fact, for k = 0 we must have A C {2, 3,. , n} since there is an entry 1 directly above At. Hence, in either The order that these values appear in At , n}. case, A ç {2 k, 3 k, is uniquely determined since the column must strictly increase. Since there 1 entries in At and we know that both n + 1, n + 2 e At, we have are only A 1 2. A jA 1 2 gives rise to , n} with IA <A Furthermore, any A C {2 k, 3 k, S(At, reading word that contains A k, n) with lattice a unique SSYT of shape in its foundation. Namely, we fill the first IA boxes of At with the values of A — A. The 1 withn+1,n+ 2,...,n+ A t —A boxesofA 1 andtheremainingA — A 1 tAI). Sfl+eA+(OhI, > ri+2, Since 1(v(A)) content of this filling is v(A) there is no SSYT of shape S(A, k, n) with lattice reading word and con tent v(A). Since all SSYT of shape S(At, k, n) with lattice reading word and content v, for 1(v) > n + 2, arise in this manner, we have — . . — — . . . — — S5(At,k,n) — . — . . — SS(A,k,n) AC{2—k,3—k,...,n} IAI)i—2 as claimed. Now, if we have two sets A and A’, with v(A) = v(A’), then looking at the first n rows of these partitions gives that S, + eA = ö, + eAl. Hence eA = CA’, so we obtain A = A’. This shows that no distinct subsets contribute to the same term s. Therefore the difference is multiplicity-free. I We note that for A a partition with one part, the difference S5(At,k,n) since this SS\,k,n) will still be multiplicity-free if we use any fat staircase only adds more restrictions to which values can appear in the foundation. However, since the expression for the difference in the case of fat staircases is more complex, we choose not to examine the matter here. — 94 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS 4.2 Two Part Partitions We now turn to the case of partitions with exactly two parts. In Theo rem 4.2.1 the condition A > 1 is present to prevent A from being a single column. We wish to exclude this case since the previous section already inspected the difference when the foundations were a row and column, re spectively. Theorem 4.2.1 Let n be a positive integer, 0 < k < 1, and A is a partition 1 <k + n. Then with two rows such that 1 <A 1. SS(A,k,n) — Ss,k,n) s 2. S(,\t,k,n) 5 3. SS(t,k,) n+2 5 S(A,k,n) n+1 SS(A,k,n), 0, and if A At. Proof 1. Consider any SSYT 7j of shape S(A, k, n) with lattice reading word, where 1. Then the entries of the foundation A have the following relations. 0 k <•<aA 2 a1<a2<•<aA 1 A A •.. A <b <•••<b 1 b 2 2 The fact that a 1 <a 2 1 follows from Lemma 2.1.1, and the rest of <aA the relations follow from the definition of a SSYT. We also have the condition 1 > 1 when k = 0. a The relations a 1 < a < 1 show that there is no repeated value < a in the first row. Further, if there is a repeated value j in the second row, then j > 1 aild the lattice condition shows that a j 1 occured in the first row, and that another j could not have occured in the first row. Therefore, if there is a repeated value in the foundation of 7, then it only appears twice. We shall create the desired tableau 7 of shape S(At, k, n) in four steps that we shall describe presently. In Step 1 we will transpose the foundation of 7, giving us a tableau T of shape At, where T is not necessarily semistandard. In Step 2 we will check whether or not n + 2 appears in our tableau T. If it does, we will swap its position so that it will be read after reading an n + 1. This gives — 95 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS us a tableau T’ of shape A which still may not be semistandard, but will not violate the lattice condition when reading the value n + 2. In Step 3 we will fix any places in T’ where a column is not strictly increasing by rotating certain blocks of entries. After completing this step, we will have a SSYT TI’ of shape A. In Step 4 we will append T” to /, creating a SSYT 7 of shape $(\t, k, ii). During Step 4, we will have shown that 7 has a lattice reading word. Finally, we check 7 can be recovered from 7. Step 1: Transpose Foundation (7 —+ T) Let us consider the tableau T that is obtained by transposing the entries of the foundation of 7j. Then T is a tableau of shape X. 1 a < b A iA A A _1 2 aA < 1 _ 2 b < 2 b A 2 a A A A 1 a Step 2: Fix Potential n + 2 Lattice Problems (T —* T’) The tableau T cannot be immediately extended to a tableau of shape k, n) with lattice reading word if there was both a n + 1 and a n + 2 in T. Since 7j had a lattice reading word, the tableau T can have at most one n + 2, which must occur at the bottom of the second column. Further, having an n + 2 requires an n + 1 in the first column of T, which must also appear at the bottom. We split into three cases and define a tableau T’ of shape )t in each case. In each case we display the resulting tablueau T’. 96 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS 1 <n + 1 and b 2 <n + 2 then T’ 1. If a 2. If aA 1 = 2 n+ land b = = T. n+2, then (a) If X > A 2 then T’ = T with aA 2 swapped. 1 and b (b) If Ai = T with a 2 and b 1 swapped. _ 2 )2 then T’ 1. 1 a 2.(a) 2.(b) 1 b 1 a 1 b 1 a 1 b A iA A A A A A iA A iA A A 1 _ 2 b 1 _ 2 a _ 2 b aA _ 2 1 A A A A 2 b 2 aA n+1 1 _ 2 b 1 _ 2 a < < A < A A A A 1 a n+2 < < < n+1 A < ri + 2 The lattice condition implies that there was oniy one n + 2 in the second column and only one n + 1 in the first column. Thus, the inequalities shown above are accurate. Now, when readillg any of these resulting tableaux T’, we shall always read an n + 1 before we read the ri + 2. Step 3: Fix Strictly Increasing Problems (T’ —+ T”) We first recall that each entry in the second column of T’ is at least 2. Further, if we had the entry 2 repeated in the second column of T’, then the semistandard condition on ‘Tj would have required two of the a equal to 1. However, we know that the a are distinct, hence we cannot have the entry 2 being repeated in the second column of T’. Let j be such that 3 <j <n + 1 and suppose that the pair of entries appear in the second column ofT’. That is, one j appears immediately below another j. Since 7j has a lattice reading word, a j — 1 must have appeared in the first column of T’. Since the first row of ‘Ti and hence the first column of T’ strictly increases there can only be one j — 1 in this column. We now consider which positions in this column of T’ could this entry j — 1 appear. There are two cases to consider. [ 97 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS 1. The j — 1 appears directly to the left of the bottom j. 2. The j 1 appears somewhere below the box directly to the left of the bottom j. — The j 1 cannot occur above the left of the bottom j else the element x directly to the left of the bottom j would satisfy j 1 <x <j. In this step we shall work from the top to the bottom of the second column of T’. We begin with j being the first pair of repeated elements in the second column, and proceed downwards. We now show how we fix these strictly increasing problems in each of the two cases mentioned above. Case I: The j 1 appears directly to the left of the bottom j. Starting from the top j, we search up the second column. Suppose the entry above j is the value j 1. We have already mentioned that there is another j 1 in the first column ofT’. Since there are two j l’s in T’, there are also two j l’s in ), and since 7j had a lattice reading word, there must be a j 2 in ). Hence, there is a j 2 in T’ as well. If this j 2 appeared in the second column of T’, then it must appear directly above the j 1. If this is the case, then in 7j we wouldn’t read this j 2 until after we had read both j l’s. Hence if this j 2 is in the second column then there is also a j 2 in the first column, and it must appear directly above the j 1 in the first column. There are now two j 2’s in T’. Using the lattice condition on 7, this implies there is at least one j 3 in T’. Just as with the j 2 previously mentioned, if this j 3 appears in the second column of T’ then we will find that there is a j —3 in the first column ofT’, which appears directly above the j 2. Continuing in this manner, we have a sequence j l,j —2,.. . ,j m above the top j in the second column and corresponding sequence j 1, j 2, . . . , j m in the first column, and the lattice condition of 7j requires a j m 1 to appear in T’. Since the tableau is finite, the above procedure must terminate for some value m = i and we find that the element j i 1 does not occur in the second column. Thus the j i 1 appears in the first column, directly above the j i. The entries j 1, j 2, . . . , j i, j i 1 in the first column and the entries j,j,j 1,j 2,.. . ,j un the second column define a block of entries. We highlight the block in the diagram below. Consider rotating this block of entries clockwise as shown. — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — 98 — — — CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS * y * y A A A A x i—i x A A j—i+1 i—i < A j—i—1 < A A i—i < < A = i—i = j—i+1 A j—i+2 —f j—i—1 A j—i+1 A A A A A A A A j—1 j—2 A A j j—1 3—3 < A j—2 < A = A = A j—1 < A z < j j A A w z j—2 j—1 A = j A < w This block rotation fixes the strictly increasing problem caused by the j’s in the second column of T’. We make a few comments to justify the accuracy of the relations displayed in the above diagrams. First, a note on the relation * y that appears at the top of each diagram. We are fixing these problems in T’ from top to bottom. Initially all rows of T’ strictly increase since the columns of T were strictly increasing. Yet, after we perform one or more of these block rotations all rows contained in a given block, except the top row, will now display equality. However, we will soon show that any two blocks are disjoint (see p. 101), hence all other row equalities appear strictly above the current block that is displayed. Initially, the entries of the first column of T’ were strictly increasing. This gives that x i 1 and j 1 < z. The first inequality gives x <j Also, there are can only be two j’s in the diagram, we have that z j. Therefore the second inequality gives that j <z. This shows that the block rotation preserves the strictly increasing nature of the first column. Since we are working from top to bottom, we know that the second column strictly increases above the j’s. This gives y < j i and j < w. Since we assumed that j i—i did not appear in the second column, the first inequality gives y < j i 1. Therefore the strictly increasing segment of the second column has been extended downwards. Again, since we are working from top to bottom and the blocks are dis joint, the rows strictly increase for each row that the current block intersects. After rotating this block it is evident that we obtain row equalities for each [] — — — — — — — — 99 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS of these rows except the top-most. Thus we have seen. how to resolve repeated elements in the second column that falls into the first case. We now turn to the second case. Case II: The j 1 appears somewhere below the box immediately left of the bottom j. We define the block of entries exactly as in Case I. The only difference in this case is that the block of entries consists of a sub-block in the second column and a lower sub-block in the first column. These two sub-blocks can be row-disjoint from one another. We still must check that we obtain a SSYT after we rotate the block. The strict inequality down the columns follows for the same reasons as in the first case. The rows were strictly increasing to begin with since the columns of 7j strictly illcrease. We need to check that, after rotating, the rows still weakly increase. There are three cases to check, each of which is displayed in the following diagram. — 1 is above the sub-block in the first column. 1. The row of interest r 2 is within the sub-block in both columns. 2. The row of interest r 3 is below the sub-block in the second column. 3. The row of interest r * j—i—1 3 r i—i * j——1 y1 * * * j—i * * * Block Rotation * Y2 * * * 2 x * * * 7J3 * k boxes J3 boxes i—i j * * 3 may in fact be the bottom-most Thus, in the left-hand diagram, the value x entry of the sub-block in the first column. That is, x 3 = j 1 is a case . 3 considered by the various possible positions of r — 100 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS 3 shown, we wish to show x <y for i = 1, 2, 3. For the rows r , r 1 , and r 2 the rows weakly increase after the block rotation. Since will show that This the columns strictly increase we have <j—i—1<j—iyi, and 1 x 3 < X — 1 < <p3. 2 =j k 2 and Y2 k as shown, we have x Further, with k 1 and 2 hence +ki 1 2 2 <x x +k Y2• 2 =j—k — = j — 2+k k , 1 Therefore the rows of the resulting tableau weakly increase. We can now check that no two block rotations move the same elements. problem then there cannot If we have performed a block rotation to fix a be two j + l’s below the new position of the j’s, since, if there were, then in ‘Tj we would have read two j + l’s in the foundation A before reading any j’s, which would violate the lattice condition. Since the blocks are formed by extending consecutively increasing sequences, this shows that the next block could not overlap this block. Thus any two blocks are disjoint. This process of block rotation removes the pairs of repeating elements in the second column while maintaining the strict inequalities of the two columns up to that point and never violates the weakly increasing restrictions on the rows. By working top to bottom and repeating this process for each pair of repeated elements in the second column we shall produce a SSYT T” of shape At. [ ] Step 4: Extend from shape At to a SSYT of shape S(At, k, n) (T” —* 7) Using T” and the unique semistandard filling of with lattice reading 2 of shape At word, we obtain a SSYT T 2 has a lattice reading word. In each case there is We also claim that T . If an n + 2 does appear, then it appeared at the 2 at most one n + 2 in T end of the second column of T, and none of the block rotations in Step 3 moved its position. Further, since 7j was lattice, we know that an n +1 must have appeared at the end of the first column of T. If A 1 > A 2 then Case 2(a) placed the n + 2 at the bottom of the first column and placed the n + 1 at the bottom of the second column. The only way this n +1 could have moved in Step 3 was if there was another n + 1 above it. In either case, an n + 1 remains at the end of the second column, so we read this n +1 before reading the n+2. Similarly, if A 1 =A 2 then Case 2(b) placed the n+2 at the bottom 101 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS of the second column and placed the n + 1 directly above it. Again, the oniy way this n + 1 could have moved in Step 3 was if there was another n + 1 above it, and in either case, an n + 1 remains above the n + 2, so we read this n + 1 before the n + 2. Therefore the single n + 2 that occurs does not violate the lattice condition. 2 is not lattice. Let j + 1 Nevertheless, suppose that the reading word of T when read, violated the lattice condition. We know that be the entry that, the content after reading /.S is (n, n 1,.. , 3, 2, 1), so we must have read . Since there 1 at least two more j + l’s than j’s since we finished reading Z are only two column for these two j + l’s to appear in, there can only be two j + l’s. Thus we must have read exactly two j + l’s and no j’s since we finished reading /. Let the values of the columns be x ,x 1 , 2 , x) and respectively. Thus 1 and x 1 for some i k. j j , 2 y, + + Vk = Yi, Y2,•• = {x, xH.1,. , x } U {yj, Yk+1,• . . , y 1 We know j } since the columns 2 strictly increase. But we also knowj {xi,x2, . . . 2 ,y . 1 ,x}u{y , ,y} since by assumption we had not read any j’s when reaching the second j + 1. Thus . — ... . .. ‘ .. {xl, x , y 1 which is to say j ,...,x 2 , Y2, . . . , y, 1 }. This is a contradic 2 tion since {xi, x ,. . . , x, yi, 2 = , 1 {a 27 ax a ..., ,b 1 , 2 } 2 b } 2 ,b 1 , y and the fact that there are two j + l’s in the foundation of 7 implies there was at least one j as well, else 7j could not have a lattice reading word. Therefore the SSYT T 2 has a lattice reading word. Thus we may apply Lemma 2.2.3 to obtain a SSYT 7 of shape S(t, k, n) with lattice reading word. ‘ . . ., . Check: Can we recover We claim that 7 can be recovered from 7. Step 4 can be undone by passing back to the foundation of 7. The swapping performed in Step 2 is easily detected and reversed. Undoing Step 1 requires a mere transposition of diagrams. So to prove the claim it remains to check that the block rotations in Step 3 are reversible. Since we have noted that no two block rotations move a common element, it is enough to check that each of the two cases are reversible. Hence we look at reversing both cases after fixing a problem. If we made such a manipulation in Case I of Step 3 (i.e. j 1 was immediately left of the bottom j), then the foundation of 7 now has a row containing j. By transposing the foundation we obtain a tableau of shape A with a column We now search to the left of this column until we come upon a nonrepeating column where x < j i 1. This [ ] — [ ]. [ 102 - ] — — CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS determines the block of entries we wish to rotate. We then rotate the entries clockwise to undo the original block rotation. < i—i < ... < j—1 < j—i—1 < i—i < ... < j—1 < x < j—i—1 < < j—2 < i—i < j—i+1 < x A A y * * A y < < j < * < j—1 < * 1 A A j •• < ... < A A A j j = A < If we made such a manipulation in the second case (i.e. j 1 was below the left of the bottom j), then upon transposing the foundation of 7 and reading its entries we come across two j i’s before reading the j i 1. This determines the smallest element j i 1 in the block we wish to form. The j i 1 necessarily appears in the second row, immediately to the left of the second j i that we have just read. The remaining elements of the block are the sequence of consecutive integers j i, j i + 1,. , j to its right and the copy of this sequence in the first row. The consecutive sequence cannot be further extended to the right, otherwise, in the foundation of 7, we would have read two j + l’s before reading either of the j’s. Therefore the correct endpoint j for this block of entries can be correctly determined. Again we rotate the elements in the block clockwise to recover the original. Therefore we can undo the block rotations of Step 3. Hence 7j can be recovered from 7. This completes the proof that SS()t,k,) SS(),k,n) 0. — — — — — — — — — . — . — An example of block rotations is shown after the remainder of the proof. 2. We now show that we can reverse the process described in the proof of 1 when we restrict to fillings using the numbers {1, 2,. , n+ 1}. If we take any SSYT 7 of shape k, n) with lattice reading word then the foundation ) consists of two strictly increasing columns. . 103 . * * CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS 1 a b < A A A A 1 2 aA < 1 _ 2 b < b A A 2 aA A A 1 aA Since the columns strictly increase we may see a pair of equal elements b in At, but never three equal values. We shall create the desired tableau 7 of shape SA, k, n) using three steps that we shall describe presently. In Step A we will transpose the foundation of 7, giving us a tableau T of shape A, which is not necessarily semistandard. In Step B we will fix any places in T where the lattice condition would fail if we appended T to /. by rotating certain blocks of entries. After completing this step, we will have a SSYT T’ of shape A. In Step C we will append T’ to /, creating a SSYT 7j of shape S(A, k, n). During Step C, we will have shown that 7 has a lattice reading word. Finally, we show that 7 can be recovered from 7. = Step A: Transpose Foundation (7 —+ T) Let us consider the tableau T that is obtained by transposing the entries of the foundation of 7. Then T is a tableau of shape A. A iA ... A <b <••<b 1 b 2 Step B: Fix Future Lattice Problems (T —* T’) In this step we move certain entries of T so that the resulting tableau of shape A can be extended to a tableau 7 of shape S(A, k, n) whose reading word is lattice. Given T, the only problems that may arise is that, when reading the entries of T, we come to a point where we have read two j’s before reading any (j 1)’s. We call this a future lattice problem. We look at how to remedy these problems. If there are two 2’s in T, then there are the correpsonding two 2’s in 7. Further since S(At, k, n) has a lattice reading word we must read a 1 in — 104 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS 7 before reading the second 2. By the semistandard conditions, we must have a 1 = 1. Since at most one 2 can appear in the first row of T, this 1 is read before the second 2 is read in T. Therefore j = 2 cannot give rise to a future lattice problem. Also, since the lattice condition places no restriction on reading l’s, j = 1 also cannot give rise to a future lattice problem. Let j 3 be the first value that we have read twice without reading any j 1. In this case we say that we have a j,j problem. Since 7 has a lattice reading word, a j 1 must have appeared somewhere in T. The only place we have not read is to the left of the j in the second row. Since the rows of T weakly increase (in fact strictly increase, to begin with), the j 1 must appear immediately to the left of the j in the bottom row. We now search to the right of both j’s and find the largest consecutive sequence j,j + 1,... ,j + i that appears in both rows. These sequences together with the entry j 1 define a block. There are two cases to consider: — — — — 1. The two j’s are in the same column. 2. The top j appears to the right of the bottom j. We note that the top j cannot occur to the left of the bottom j, otherwise the entry m above the bottom j satisfies j < m j. The two cases are displayed below. y i-i H +i... •..j+i1 j+iz j j+1... •.. j+i—1 j+i w or x y j—1 j j+1... j j+1 ... ... ... j+i-1 j+i j+i-1 j+i z w After rotating the entries of either block clockwise the columns will strictly increase. We inspect the relations of the rows in both of the two cases simul taneously. We may do this since the entries of the rows are the same in each case. We display the rotation in the second case. The entries of the block are rotated one position clockwise as shown. 105 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS j j+1 x y i-i j j+1•• •.. j+i—1 ... •.. j+i-l j+i w j+i z -I, x y j—1 j+i-2 j+i-1 z j j j+1 j+2 j+i j+i w Since both rows strictly increase to begin with, we have x <j, y <j 1, j+i < z, and j+i <w. Therefore we have the inequalities y <j, j+i—1 <z and j + i < w. Further, since there was no j 1 in the first row, we have 1. Hence the only pair of equal values in a row that is created by x < j this block rotation is the pair j + i, j + i in the bottom-right of the block. Initially, the columns of T were weakly increasing. Now consider any Since the reading word column of T with a pair of equal values, say for 7 is lattice, there is a m 1 in T. This rn 1 must occur in the column If this rn 1 appears in the first row of immediately to the left of the T, then since the colums weakly increase and there are only two rn’s in T we find that a second m 1 appears immediately below it. Thus we obtain a column We continue extending this block of equal valued columns = to the left. It terminates when we reach some column where a j 1 appears immediately left of this column in the second row, but not in the first row. — — — [ ]. — — [ ]. — — [ ]. [ ] x < j < j—i < j < ... ... < rn—i < rn < rn—i < m — This gives rise to a future lattice problem. Thus all columns in T that did not strictly increase are contained in some block. We now check that the columns of each block strictly increase after performing the block rotation. There are three cases to consider. 1. The column of interest c 1 is left of the sub-block in the first row. 2. The column of interest c 2 is within the sub-block in both rows. 3 is right of the sub-block in the second row. 3. The column of interest c 106 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS 1 C 3 C C2 X1* j j—i...*yi... X * * i+1 **y ‘.. :” 3 *:y Block Rotation * . j ... ...*... I 2 * x ** X3 j+i—i •••i+I i 1 k boxes boxes For the columns c , c 1 , and c 2 3 we wish to show that xj < yj for i Since the rows were strictly increasing to begin with we have 1 x 3 X 1, 2, 3. <j <yr, and < + <J3. 2 shown, we have x 2 j+k k 1 Further, for k 1 and k hence + <x = 1 — j+k k 1 <y2. 2 2 x — — 1 and Y2 = 2 j+k It can be seen that no two of these block rotations performed in Step B can move the same elements. If we have done a manipulation to fix a j, j problem then there cannot be a second j 1 immediately left of the bottomleft element of this block since, otherwise, before rotating that block the row had the value j 1 repeated occuring on the bottom-left of the block. However, we know that the rows were strictly increasing to begin with and the only repeated values we have introduced were on the bottom-right of each block we have rotated. So since we are working right to left, this repeated value j 1,j 1 could not occur. Therefore, after rotating this block, there is no j 1 in the bottom row, and hence the next block’s pair of consecutively increasing sequences cannot enter this block. Hence the two blocks are disjoint. We continue this process of reading values and fixing future lattice prob lems by rotating blocks until there are no more future lattice problems left in the tableau. This results in a SSYT T’ of shape A. — — — — — 107 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS Step C: Extend from shape A to SSYT of shape S, k, n) (T’ —* 7) Using T’ and the unique semistandard filling of z, with lattice reading 1 of shape A We check that T 1 is a SSYT word, we obtain a SSYT T with a lattice reading word. Since we removed all future lattice problems, T’ has the property that, when read, the number of j + l’s is always at most 1 does have a lattice one more than the number of j’s. Thus the SSYT T applying Lemma 2.2.3, we obtain a SSYT 7j of reading word. Therefore, shape S, k, n) with lattice reading word. Check: Can we recover Finally, we must show that we can recover 7 from 7. Undoing Step A and Step C are trivial. Thus we need only show that the block rotations iii Step B can be reversed. Since any two block rotations are disjoint, it suffices to check that a single block rotation can be undone. We have seen that a block rotation creates a tableau with a repeated value j + i, j + i in the bottom-right of the block. Transposing the tableau, there is a repeated value in the second column and so the block rotation described in Step 3 applies and it results in the transpose of the original tableau. Therefore these block rotations can be reversed, and we can recover 7 from 7. Thus we have shown that SS(A,k,n) — SS(?t,k,n) 0 as functions in n + 1 variables. This and 1 completes the proof that Ssp.t,k,n) n+1 SS(A,k,n). 3. We now wish to show that the two skew Schur functions are distinct when there is at least n + 2 variables. Hence we consider fillings using the values {l,2,...,n+2}. Let 1(A) = 2 and A # )t• The hypotheses of the theorem required A > 1, so that A was not a single column. If A = 2, then A is either the shape (2, 1) or (2, 2), which both have At = A. Thus we need only consider A 1 3. We split into three cases depending on the size of A . Namely, 2 1. A 2 = 1, 2. A 2 = 2, and 3. A 2 >3. 108 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS In each case we wish to create a SSYT T of shape $(At, k, n) with lattice reading word and content v such that no SSYT of shape S, k, n) with lattice reading word and content v exists. Here we show the fillings of the foundation of the required tableau T for each of the above three cases. 1. 2. 2 3 2 3 n+1 —2 1 A n+1 n+2 A — 1 2 n ri+1 n+2 n+1 n+2 3. 2 3 3 4 —2 2 A —1 2 A A — 2 1 2 A +1 2 A Ti n+1 n+2 A —2 1 —1 A n+1 n+2 If A = 3 in case 1 or 2, then the first column consists of the three entries 1 = 3 in case 3, then the first column consists of + 1,n + 2, and if A 2, Ti + 1, Ti + 2. Similarly, if A 2 = 3 in case 3, then the second column consists of n, Ti + 1, Ti +2. In each case it is clear that ‘T is a SSYT with a lattice reading word. We now check that no SSYT of shape S(A, k, Ti) with lattice reading word and the same content can exist. Any SSYT of shape S(A, k, n) with lattice reading word can only have a single n + 1 in the first row of A and a single Ti + 2 in the second row of A. Further, no n + 2 can appear in the first row of A. Thus, in Case 1, the Ti + 2 must appear in the second row of A, but then both Ti + l’s would have to appear in the first row, which is impossible. In Case 2 and Case 3, both Ti + 2’s would have to fit in the second row of A, which is impossible. Therefore Sst,k,n) n+2 8 S(),k,n). I Ti,’fl Example Here we illustrate a concrete example of Step 3 and reversing Step 3 in the proof of Theorem 4.2.1. Let us begin with the foundation of S((7, 6), 0, Ti), where Ti 11. 2 6 4 7 5 7 6 8 9 11 10 11 12 109 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS We now tranpose and perform Step 3 twice. For convenience, in each step we highlight the block that is about to be rotated. 25 46 67 78 9 10 11 11 12 25 46 67 78 9 11 10 11 12 26 47 57 68 9 11 10 11 12 To reverse Step 3 to return to the original tableau we transpose and then either follow the rules for rotating discussed in the Check section of the proof of part 1 of Theorem 4.2.1 or, equivalently, follow the the rules for rotating discussed in the Step B section of the proof of part 2 of Theorem 4.2.1. 2 5 4 6 6 7 7 8 9 10 11 11 12 2 5 4 6 6 7 7 8 9 11 10 11 12 2 6 4 7 5 7 6 8 9 11 10 11 12 110 Chapter 5 Complements in a Rectangle In this chapter we show how to extend the results of the previous chapters to fat staircases with bad foundations where the foundations are the comple ments of the foundations we previously inspected. Throughout this chapter, when considering a composition c we shall let n = 1(o). That is, c = (, c, , c). With this convention, the diagram 5c has width respectively) and length = o. (, In this chapter we shall be particularly concerned with the size of dia grams. Thus for a diagram D we let 1(D) denote the length of the diagram and w(D) denote the width of the diagram. That is, (w(D) (’)) is the smallest 1 rectangle that contains D. . . . c n 5.1 Preliminaries Given a partition p contained in the a x b rectangle (be) we define the plementary partition pC the rectangle (be) by pC = ((ba)/p)o. That is, pC is the complement of p in (ba) rotated by 1800. It is easy to see that this definition does define a partition. We display the relevant diagrams below for clarity. corn in (pC)o 111 CHAPTER 5. COMPLEMENTS IN A RECTANGLE For what follows, we shall make use of the following fact that can be found in [34]. Theorem 5.1.1 Let p be a partition contained in the a x b rectangle (ba), ic C p be a second partition. Then the skew diagram p/ic satisfies >.:: vC(ba) where c are the Littlewood-Richardson coefficients. Given a symmetric function f = plement of f in the rectangle (be) as c(f) we define the truncated com (5.1) = vC(ba) The rectangle being used should be clear from the context if it is not specif ically mentioned. We note that one effect of the restriction v (be) is that in passing from f to c(f), we are reducing computations to a variables. This follows since any term s from f with 1(v) > a is effectively being set to zero, which is precisely what happens when reducing f to a variables. This will not cause us any difficulties, since for each skew Schur function s, that we wish to compute, we will always choose an appropriate rectangle (be) with p/ic C (ba) and, when computing Sp/,c = it is easy to see that each v must satisfy v C (ba). For instance, we can check that each v in the above sum satisfies 1(v) l(p/ic) since the Littlewood Richardson rule implies that, for each SSYT T of shape p/ic and content u with lattice reading word, the entries of the i-th row of T are i for each i = 1, 2,. , l(p/ic). Therefore s is completely determined by using only l(p/,c) variables. Also, each v in the above sum satisfies w(v) w(p/,c). If not, then w(u) > w(p/ac). Then in particular v 1 > w(p/ic), which implies that there is a SSYT of shape p/ic and content v with lattice reading word using v 1 l’s. However, there is no way to fit v 1 > w(p/ic) l’s in the shape p/ic while maintaining the semistandard conditions. . . We may now restate Theorem 5.1.1 as follows. 112 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Corollary 5.1.2 Let p be a partition contained in the a x b rectangle (b°, and ic C p be a second partition. Then the skew diagram p/ic satisfies = c(sksPc). Proof From the definition of the Littlewood-Richardson numbers, we have S,çSpC = >cpcsv. Hence c(ssc) = c (cpcsv) By Theorem 5.1.1, this is just , 311 s, pcuc. — VC(ba) V so we are done. One must be careful in working with the expression c(skspc). We must (ba). Thus we truncate any term s we obtain from the product with ji must be mindful of the dimensions of the rectangle we are working in. We are interested in extending the results of the previous chapters to differences of skew Schur functions s ,/,ç for more types of diagrams p/ic. In 1 particular, we shall see how to generalize to fat staircases with bad founda tions where the foundations are either complements of hooks or complements of two-row diagrams. Since = c(sksc), we shall begin by inspecting the symmetric function c(skspc). Lemma 5.1.3 For a partition A, composition cii, and 0 < k 1 we have c(ss) = c(ssp<;k)), for any complementation in a rectangle of width w = n + k. We note that in general # SS(,;k). For instance, we know that = and if A has more than one column, then there exists SSYT of shape A e Li with lattice reading word for which the first row of A has repeated l’s, but no SSYT of shape S(A, c; k) with lattice reading word can have the same content by Lemma 2.2.2. Proof (of Lemma 5.1.3) Let the rectangle be (w ) 1 , say. We begin by comparing c(s) and Consider a content v that contributes to c(s). Then ii ) and 1 (w there is a SSYT T of shape A & and content V with lattice reading 113 CHAPTER 5. COMPLEMENTS IN A RECTANGLE word. Since z/ is contained in a rectangle of width w, T contains at most w = n + k l’s. We know that exactly n l’s appear in the copy of &. Thus the copy of \ contains at most k l’s. Therefore, by Lemma 2.2.3, we can obtain a SSYT T’ of shape c; k) with lattice reading word of content i/C by simply filling the entries of ) in S(A, c; k) identically to the filling of ), in T. This correspondence, T i—* T’ gives a bijection. That is, [ycJ (s) = ). This gives c(sa) = C(Ss(,c;k)). t [svc](Ss(A,o<;k)) for all V ç (w and so c(sAe) = c(ss). Thus we have We also have = c(sAsz) = C(Ss(,ca;k)), as desired. I o < Given a composition k < 1, we let = fl, = (c, c ,. 2 (€n, cn_i,. . (€ni, n—2,. . . , a) , 2, c) . . , and a width ) 1 2, cr if if w = n + k, where k = 1 k =0 denote the reverse composition. With this definition we have 5 = where the complement is performed in the rectangle (w). We illustrate the two cases k = 0 and k = 1 below. ] J rT1 HH 2 HH R’ Thus we have l(6) k= &j+(1-k)c. :1 l(ö) and w(6) w(6). In particular, we have Theorem 5.1.4 Let o be a composition, w = n + k where 0 < k < 1, 1 1, and p be a partition with Ic + 1 parts such that (wI) C p C (wIl ), 1 = pC ). 1 be the complement of p in (wI’+ = (p+1,pIl+2, ii+) and A Then p/6 a, c; k) and 1 S( . . SS(,a<;k) = c(ss(r<;k)). 114 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Proof We are interested in the following diagrams, each contained in the rectangle (w ). The first set of diagrams illustrates the case k = 1 and the 1 second set illustrates the case k = 0. li 1 S([L, c; 1) 1) 1 S(t, c; 0) p/:5yr It is clear from the definition of Therefore we obtain S(,a<;k) 8 that we have S(,u,;k) = = = = c(ssr) by Corollary 5.1.2 c(ssr) c(ss(A,cr4;k)) by Lemma 5.1.3, which is what we wanted to prove. • 115 = p/6r. CHAPTER 5. COMPLEMENTS IN A RECTANGLE 5.2 Staircases with Hook Complement Foun dations We now consider two hooks A, i both contained in a rectangle (w ) and let 1 AC and 1 U’ denote their complements in this rectangle. We call these hook complements. For a fat staircase Z, we now inspect when the difference SS(pC,;k) is Schur-positive. Thus we are interested in the differ SS(Ac,&;k) ences of skew Schur functions for pairs of diagrams such as the pair displayed below. — Our first result, Theorem 5.2.1 states that we obtain the same Hasse diagram for fat staircases with hook complement foundations as was obtained for fat staircases with hook foundations. Recall that for partitions A and t we define A U u to be the partition consisting of parts A ,A 1 ,. , p, 112,... placed in weakly decreasing order. 2 We shall be interested in the case when the first partition is the rectangle () and the second partition ic has w(ic) < n. In this case (wa) u , = , K 1 ic ,...) is obtained by merely appending ic to the rectangle (w’). 2 . . Theorem 5.2.1 Let A and 11 be hooks with A = = h < n + k = w and let 0 < k < 1. Then S(AC, c; k) S(, c; k) if and only if S(A, c; k) >T; S(t, k). Proof We wish to apply Theorem 5.1.4 to both diagrams. To this end, we need to choose appropriate partitions p. We let p(AC) := (wkI) U AC and p(itC) := (wII) U tC Then we have (wII) C p(Ac), p(11C) C (w* ) so we 1 may apply Theorem 5.1.4 to both p(AC)/5r = $(AC, &; k) and p(C)/Sr = S(11C, c; k). This gives SS(C,&;k) — S3(jC,1;k) = c(ss(A,r;k)) 116 — c(ss(,,ar;k)) CHAPTER 5. COMPLEMENTS IN A RECTANGLE c(ssp,oiy1;k) — where these complements are performed in the rectangle (wkHj. r; k), then the above equation shows that Now, if c; k) >S(), c; k) >- S(ic, ; k) as well. S(, c; k). For the converse direction, suppose that S(A, cr; k) is not Schur-positive. Thus, by assumption, the difference SS ;k)SS(p,;k) However, we need to verify that the truncated version is also not Schur-positive. In Section 3.1, we saw that the only cases where the difference was not Schur-positive among diagrams of this type were those in cases covered by Theorem 3.1.1, Theorem 3.1.2, and Theorem 3.1.5. Thus ). and t must satisfy the hypotheses of one of these three theorems. In each of these three theorems, by inspecting a particular term s in the difference, it was proved that the difference was not Schur-positive. We need only check that for each ). 1 (wkH theorem the partition v satisfies ii In both Theorem 3.1.2 and Theorem 3.1.5 we used ii = 5 ar + ,r) < 5 where r 1<r 2 < are the values of Rar,k. We have W( = n. Further, since the r are distinct, adding the terms e to e5 can only 1 = 1 which implies that increase the width by 1, and this only happens when r k = 1. Thus, Ill either case, w(v) < ri+k = w. Also, since l(5) < = jc+1,wehavel(zi) < j+1 < +l. Thereforeviscontained alldeachr ). 1 in the rectangle (wkH In Theorem 3.1.1 we used v = 6 + e + (O1I, iAt), where r 1 < 2 < r are the values of Rar,k. As in the previous case we find that w(v) n + k = w. For the length of ‘i we have 1(v) = al + A < c + 1, since ). t cv < o and ) ç (w ). Therefore v is contained in the rectangle (wH 1 ). Therefore 1 Thus, in each case ii is contained in the rectangle (wH the term s in the difference Ss(A,r1;k) SS(,r<;k), is also in the difference Ss(,i,cir;k)). Since this term has a negative coefficient, it shows that c(ssp,or;k) SS(p,,cr<;k)), and hence ssçc,cyi;k) SS(pCpl;k) is not Schurpositive. That is, k) This S(p, c; k). completes the converse c; direction. Therefore we have shown that S(), c; k) S(, ; k) if and only if S,€i<;k) ? S(t,c;k). — — — • 117 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Example Here we see the Hasse diagram obtained by considering all dia grams of the form S(, c; k) where c = (1, 1,3, 1,2), k = 1, and ) is a hook of size 6, where ) is computed in the rectangle (66). ri i We now wish to calculate the difference Ss(Ac,;k) SS(pC,ci1;k), for hook diagrams A and u, in the cases when this difference is Schur-positive. First we look at the case when Aa < Ita, which was explored in Theorem 3.2.2. AC and 1 u’ denote the complements in (w As before, we let ). 1 — 118 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Theorem 5.2.2 Let A and it be hooks with Aj f1Aa<aant0k1. Then — SS(,C,&;k) = = = h n+k = w and a,cs(B,c) 0 are given by where the coefficients a, aB,c—( — I(B — C) fl Rr,kI — ((B 1 AaCH1 — C) fl RGr,k — 1 ‘aCH1 (B, C) that arise are given by 1 the partitions r r(B, C) = (n + k 11 +I+0 1—k) k n+k — —B—ICI+cn+kl 1 n+k_2+k_2,...,2a2,11) — — cEO bEB and the sum is over all sets B, C such that • Bc {2—k,3—k,...jc1+1}, Cc BflR’,k—min(B), , 1 • C + 1 <A • Aa B fl Ro’r,k, • B+CHh, and +1eBifBj+jC<h—1, • if B = U= 1 B where the ]3 are the maximal disjoint intervals of B, then minB) e for each j, and • if C = U 1 C where the C are the maximal disjoint intervals of C, min(C 1 B C for each j. ) then 3 — — We note that the term 0 (B, C) is not defined for k = 1, but this 1 n+k in r causes no problem in computing the above expression since the oniy time the term 0 n+k appears is as part of the term (1 k)€fl+k, which is zero for k = 1. — Proof (of Theorem 5.2.2) We wish to apply Theorem 5.1.4 to both diagrams. To this end, we let p(Ac) := (w) U AC and p() : (w) U jic Then we have (wkI) C: 119 CHAPTER 5. COMPLEMENTS IN A RECTANGLE pc),p(jc) c $(,\c c; so we may apply Theorem 5.1.4 to both k) and p(C)/r = S(,uc, a; k). This gives (wIHl) SS(Ac,&1;k) — = c(ss(,cr;k)) = c(Ss(,cr;k) p(\c)/r c(Ss(p,cr;k)) ). 1 where these complements are performed in the rectangle (wk Since SS(X,&l;k) SS(,&i;k) is just Theorem 3.2.2 with a replaced by we have — — Ss(c,;k) = c ( &‘, acsv(Bc)) B,C That is, SSC,&1;k) where ii(B, C) = — SS(,tC,1;k) = c5r + bEB eb + cC e + (5.2) aB,CsL?(B,c)c, (Ok+1, lI?IHBIH) and and the sum is over all sets B, C such that • Bc{2_k,3_k,...jaT+1},CcBnRr,k_min(B), • C+1 • Aa , 1 A B fl R&’,k, • 3 where the 133 are the maximal disjoint intervals of B, • if B = U= 1B then min(B ) e Rr,k for each j, and 3 • if C = U 3 where the C 3 are the maximal disjoint intervals of C, 1C then min(C ) 1 e B C for each j. 3 — — For sets B and C satisfying the above properties, we display the par tition v(B, C) in the diagram below. We split the rectangle (w ) = 11 (WIa+(l_n+l) into sections of length an + 1 and (1 k)cv + 1 1. The length Ian I + 1 is a convenient choice since the sets B and C only contribute to the first ar I + 1 parts of v(B, C). In the depiction of v(B, C), the staircase in the top-left is &r, which arises from the filling of The boxes L1 and 1 denote the boxes that arise in zi(B, C) from filling the foundation with the terms of EbEB eb and >cEG e. The column at the bottom represents the — . values from the term (Ok1+1, lI_LBHIC). 120 — CHAPTER 5. COMPLEMENTS IN A RECTANGLE Since this diagram represents v(B, C), the blank space in the bottomright corner of the diagram represents (ii(B, C)c)0. &r + >ZbEB eb + ZcEC e PIIBHIC’I) + (OI+’, 1 (v(B, C)c)o (1 — k)c + 1 — 1 Consider the case when k = 1. Then these two rectangles are of size + iH1) and (n + ii’), respectively. Rotating the blank space in the (n + 1’) rectangle gives the partition (i-i (n IHBIH0). + Rotating the blank space in the (n + 11j rectangle gives the partition — — cC bB Thus we find 1—1—+IBI+ICI ii(B, C)’ = (n + 1 U (6 — eII+2_b I—B—IC) — bB cEC Hence 1—1+IAI+BI+Ct PHBIHC’In zi(B, C)C = (n + 1 ei+j — bB ei+i_. — cEC 121 — jQn_1 ‘)2 1’) CHAPTER 5. COMPLEMENTS IN A RECTANGLE Now consider the case when k = 0. Then these two rectangles are of size (nkHan+1) and (an+l—l), respectively. Rotating the blank space in the (a+l—l) rectangle gives the partition (cm+1—1—I+IBI+C, rj — (nk1) Rotating the blank space in the _ 2 e — iPIHBHdI) rectangle gives the partition — bEB cEC Thus we find v(B,C)c = iPHIBIHdI) (nn+l—1—P+BI+ICI,n U (ó(ai,...,Q_i) e2_b — e2_C). — cEC bEB Hence v(B C)C = (i—1+I+B+ICI+cn n n — — 2_2, , 1’) — cEC bB For both k v(B, C)C = = 1 and k (ii = 0 we can rewrite these expressions as BH-ICI+(1_k)a+, Ti + k1_1+ + k Q, a+k_2,•• , 2 ri + k 2 1’) — — — — cEC bEB (B,C). Substituting this expression into Equation 5.2 gives the formula stated for S3(\C,a<;k) — S3(ic,a;k). • We now look at the case when rem 3.2.3. which was explored in Theo Aa, /-tj Theorem 5.2.3 Let ). and p be hooks with )j and letO < k <1. 1f\a [Lj, then Aa,i = = h <[f, S°,c;k) 5 — S(,c;k) 5 122 = a,cs(B.c) < n+k = w and CHAPTER 5. COMPLEMENTS IN A RECTANGLE where the coefficients a,c are given by aB,c— ( (I(BC)flR,kI1 ) AaICH1 (BC)flRar,k1 [taIC1 (B, C) that arise are given by 1 the partitions r (B, C) 7 i = (n + kl_l n+k — n+k_2Qk_2,...,2a2,11) — — cC bEB and the sum is over all sets B, C such that • Bc{2—k,3—k,...&+1},CcBnR,k—min(B), • C+1 B fl R&,k, Aa • BI+C<h, and • if B = U= ]3 1 r+1EBif Bj+jC<h—1, where the 1 B are the maximal disjoint intervals of B, then min(Bj) e R&,k for each j, and • if C = U 3 where the C 3 are the maximal disjoint intervals of C, 1C then minC) 1 e B C for each j. — — Proof The proof of this theorem proceeds identically to the proof of Theo rem 5.2.2 but uses Theorem 3.2.3 in place of Theorem 3.2.2. • 5.3 Sums of Fat Staircases By using complements in a rectangle we now describe when a diagram of the form Sn/A is a sum of fat staircases in the cases when A is either a single row or a single column. Theorem 5.3.1 Let c m < c) be a composition. Then for 1. < = (au, n the skew diagram &/(m) is a sum of fat staircases if and only . . . , ifo > lforeachj=1,2,...,n—1. Theorem 5.3.2 Let c = (c,. ) be a composition. Then for 1 < m < ni the skew diagram 6Q/(lm) is a sum of fat staircases if and only if there is no j such that c <m . . , — 123 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Proof (of Theorem 5.3.1) The diagram öa/(m) is contained in the rectangle (nIaI). Using Corollary 5.1.2 we obtain Sö/(m) = C(S(m)Sör). We note that , a) since the width of the rectangle is n. = (an_i, an_2, . . . an 1 a a 1 a_ a [ [[ [ [ We can compute the product Thus we have S(m)S using Theorem 1.6.1 (Pieri’s rule). S(m)S5 = where the sum is over all partitions A such that A/ is a row strip with m boxes. That is, the sum is over all partitions A such that the skew diagram A/S has m boxes, no two of which are in the same column. Sillce we have Sö/(m) C(S(m)Sör) = = we obtain S/(m) (5.3) = Ac(nkI) where the sum is over all partitions A C (nI) such that the skew diagram A/o has m boxes, no two of which are in the same column. 124 CHAPTER 5. COMPLEMENTS IN A RECTANGLE n 1, such that cIj = 1. We intend Suppose there is a j, where 1 j to show that ö/(m) is not a sum of fat staircases. Namely, we will show that there is a term s in Equation 5.3 where ii is not a fat staircase. (n), there are Since ö is a fat staircase aild we are constrained by ) only n possible positions to place the m boxes. Namely, there is one position in the r-th row for each r e R, . These n possible positions are shown in 1 the diagram below. — Qj j+1 L[ [ Since we must place m 1 boxes, where m < n, we choose to place a box at the end of the row of length c and place the other m 1 < n 2 boxes in any of the other possible positions except for the position at the end of the This gives a partition ) ) such that )/6 has 11 (n first row of length ‘in boxes, no two of which are in the same column. Further, by the choice of placement of these boxes we see that ) is not a fat staircase. Therefore AC is also not a fat staircase. Since this term arises in Equation 5.3, this shows that 5/(m) is not a sum of fat staircases. This completes the first half of the proof. — — Now suppose that oj > 1 for each j = 1,2,. , n 1. We intend to show that 6a/(m) is a sum of fat staircases. As in the previous case, any term in Equation 5.3 arises from placing the m boxes among those n possible positions. Since c > 1 for each j = 1, 2, ,n—i, it is clear that each of these placements results in a fat staircase. Therefore ö/(m) is a sum of fat staircases, as claimed. . . . . — . Example Consider the skew diagram )/(2) , 2 ö( 125 = (3, 3, 2, 2, 1, 1)/(2). Since NTS IN A RECTANGLE CHAPTER 5. COMPLEME of ) is a sum ( 2 ö (2 S2 2 eorem 5.3.1, )/ Th of s ese oth hyp the es = (2, 2, 2) satisfi , we have fat staircases. In particular ( + 8(3,2,2,1,1,1) i) S , 2 , 3 S(3,3,,i,i) + ) ( 2 ö S(2 2 )/ 2 ö( ) S 21 = + 1 ö( ) S 13 + 1 . o( ) S 32 6/(1m) is contained in the rectangle the , ain Ag .2) 5.3 em Proof (of Theor C(S(im)Sö 5.1.2 we obtain S/(lm) °. Using Corollary t (n a [ j+1 j—1 [[ [ t We can compute the produc Thus we have S(1m)S, rule). using Theorem 1.6.2 (Pieri’s A n strip with A such that A/6 is a colum ns tio rti pa all r ove is sum where the t the skew diagram over all partitions A such tha sum the is, at Th es. box m e row. two of which are in the sam A/6 has m boxes, no Since = C(S(im)Sör) we obtain SAC, S&/(1m) AC(nkl) 126 (5.4) CHAPTER 5. COMPLEMENTS IN A RECTANGLE where the sum is over all partitions A ç (nI) such that the skew diagram A/6, has m boxes, no two of which are in the same row. m c c+i. Then, necessarily, Suppose there is a j such that €j &/(1m) is not a sum of fat staircases. 1 <j <n 1. We intend to show that Namely, we will show that there is a term s in Equation 5.4 where ii is not a fat staircase. Since ö is a fat staircase and we are constrained by A C (nkI), the only possible positions to place the m boxes are among the cj positions shown below. For the remainder of the proof we shall refer to the columns of this column strip of possible positions as possible columns. We note that when placing boxes in these possible columns, we must start from the top in order for the resulting diagram to be weakly decreasing in row lengths. — — 1 c_ Qj [[ L Since we must place m > c 7 boxes, where m ciI c+ , we choose 1 to place a box at the end of each row of length o and place the other < c m 3 boxes in any of the other possible positions except c cj+ for the positions at the end of the rows of length cj+i. This gives a partition A C (nkI) such that A/6 has rn boxes, no two of which are in the same row. Further, by the choice of placement of these boxes we see that A is not a fat staircase. Therefore AfD is also not a fat staircase. Since this term arises in Equation 5.4, this shows that C5a/(lm) is not a sum of fat staircases. This completes the first half of the proof. — — — — Now suppose that there is no j such that c, to show that S/(1) is a sum of fat staircases. 127 m c —cj . We intend 1 CHAPTER 5. COMPLEMENTS IN A RECTANGLE As in the previous case, any term in Equation 5.4 arises from placing the m boxes among those c possible positions. Since no j satifies c < m < cj+i, there is no way to place these m boxes so that a particular possible column is filled yet the possible column immediately to the left is empty. Since such a placement is the only way to obtain a partition that is not a fat staircase, this shows that öa/(lm) is a sum of fat staircases. — • Example Consider the skew diagram given by 6(3,3,3)/(1, 1) = (3, 3, 3, 2,2, 2, 1, 1, 1)/(1, 1). Since c = (3, 3, 3) satisfies the hypotheses of Theorem 5.3.2, sum of fat staircases. In particular, we have ) /(1,1) 333 Sö( = 8(3,3,3,2,2,2,1) + 8(3,3,3,2,2,1,1,1) +8(3,3,2,2,2,1,1,1,1) = 5.4 ) 133 Sö( + ö( 8 ) 323 + 8(3,3,3,2,1,1,1,1,1) + 8(3,2,2,2,2,2,1,1,1) ) + 242 + 513 ö( + Sö( 5 ) (432) ( 333 ö 8 )/(11) + is a 8(3,3,2,2,2,2,1,1) + Miscellaneous Results In Theorem 4.1.1 we saw that when A had only one part the difference Ss(.\t,k,n) S,k,n) was multiplicity-free. The same can now be said of the 5 difference SS(tc,k,fl) Ss.c,k,n), where the complementation is performed in a rectangle (w ) for w = n + k. 1 — — Theorem 5.4.1 Let A be a partition with 1(A) andO<k<1. Then SS()tC,k,n) — S8\C,k,n) = 1 and A 1 < 1, for some 1, = AC{2—k,3---k,...,n+k--1} where (A) = (n+kt+l_k_,n+k_11_l,n+k_2,n+k_3,...,2,1) — aEA In particular, SS(Atc,k,fl) — SS(Ac,k,n) is multiplicity-free. 128 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Proof We wish to apply Theorem 5.1.4 to both diagrams. Since we are n—1+k) 1 ( working with regular staircases, we have c = (in), which gives & p(C) )C. p(Atc) := (wi’) u and := (wn) u Then we have We let p(Atc) p(Ac) (wa) C C (w) so we may apply Theorem 5.1.4 to both of p\tc)/5n_+k = S)tc, k, n) and p)c)/on_l+k = S(?, k, n). This gives S5tc,k,n) — SS(Ac ,k,n) = c(ss(t,k,n_1+k)) = C(SS(At ,k,n— 1+k) = C — — c(ssp,k,n_1+k)) ss(k,k,n_1+k)) S(A) —1 + k} where the last step follows from Theorem 4.1.1. Therefore S8(Atc,k,n) — (5.5) Sv(A)c, SS(\c,k,n) = AC{2—k,3—k,...,n—1+k} (On1+k, lAiHA) where 11(A) = 6 This shows that the n—IH-k + aeA ea + difference is multiplicity-free. We now wish to obtain an expression for the partitions v(A)c. For such A, we display v(A) in the diagram below. We split the rectangle (w) into sections of length n 1 + k and 1 + 1 k. The length n 1 + k is a convenient choice since the set A only contributes to the first n 1 + k parts of 11(A). In the depiction of v(A), denotes a box that appears in v(A) from a term of ZaEA ea. The blank space in the bottom-right corner of the diagram represents (v(A) C) 0 — — — — n—+k 6 + + aA Ca n—+k 0 ( n—1H-k )i—IAI 1 0 (v(Ay) 129 1+1 — k CHAPTER 5. COMPLEMENTS IN A RECTANGLE Thus we find v(A)c ii—IAI) (w1_k_1, = u 1+k efl a) — aEA (n+k1+1_k_A1+A,n+k_11_A+1,n+k_2,n+k_3,...,1) — aEA Substituting this expression into Equation 5.5 gives the formula stated for SS(\tC,k,n) — • SS(\c,k,n). Example Let n = 4, 1 = 3, k = 1, and A = (3). Then AC Atc = (4, 4, 4). We are interested in the following diagrams. S(AtC, 1, 4) = (5,5,2) and S(Ac, 1, 4) Theorem 5.4.1 gives SS(AtC,1,4) — ) = 4 SSpc,i, S(A). Ac {1,2,3,4} AI<1 For A = 0 we have (53+1—1—3+0 43—0+1,3, = 2, 1) (4,4,4,4,3,2,1) andforA={a},foreachl<a<4,wehave = (53+1—1—3+1,43—1+1,3, 2, 1) e3+1+4a — aEA (5,4,4,4,3,2,1)—e a 8 . = Thus we obtain — SS(c,1,4) = S( , 2 3 , 4 i) + ) 2 3 4 , 5 S( +8(5,4,4,3,3,2,1). 130 + ,i,i) 3 4 , 5 S( + 8(5,4,4,4,2,2,1) CHAPTER 5. COMPLEMENTS IN A RECTANGLE We now inspect the analogue of Theorem 4.2.1, which looked at the dif ference SS.t,k,n) SS(,k,n) for a partition A with two parts. As before, we use ), where w = n + k. 1 the rectangle (w — Theorem 5.4.2 Let A be a partition such that A, At C (w ) for some 1, and t 1 > 1 then let 0 < k < 1. If 1(A) = 2 and A SStC,k,fl) SS(Ac,k,n) s — 0. Proof We wish to apply Theorem 5.1.4 to both diagrams. Since we are n—1+k) 1 working with regular staircases, we have c (in), which gives .jyr = ( We let p(Atc) := (wa) U A and p(Ac) := (wa) U Ac. Then we have (wj C P(Atc) p(Ac) C ( ) so we may apply Theorem 5.1.4 to both of 1 = s(Atc, +k 1 p(Atc)/5fl k, n) and p(Ac)/5fl_j+k = S(Ac, k, n). This gives SS()tc,k,n) — Sc,k,n) 5 c(ss(t,k,fl_1+k)) = C(5S(At ,k,n—1+k) — C(5sp,k,n1+k)) — where these complements are performed in the rectangle Theorem 4.2.1 shows that 5 Sp,k,n1+k) S(,k,n—1+k) 5 ence is Schur-positive. • (W’). >3 — 0, so the differ Finally, using Theorem 2.3.1, we can obtain the following result. Theorem 5.4.3 Suppose a diagram D ii= fat staircase Given a partition A and 0 < k S(A, D; k) = i/0. Then c(SOSKc) çC 1 p/si is such that > SD where = 1, let 8 > , and 0 be the partitions such that cuSS,(i,);k), is the complement of i in the rectangle (w(i/0) ). 1t Proof From Corollary 5.1.2 we have Sqo C(5S,cc). 131 CHAPTER 5. COMPLEMENTS IN A RECTANGLE From Theorem 2.3.1 we have SS(,D;k) C,S8(A,c(i)1;k). Therefore C(SS,c) = = SS(),D;k) • <8 132 Chapter 6 Reduction to Finite Variables In this chapter we are concerned with equalities of skew Schur functions in finitely many variables. In the first section we begin by reiterating the finite variable equalities for staircases with bad foundations that were proved in Chapter 4. These equalities involved differences of staircases with transposed foundations. We extend these results to the case of transposed hook foun dations, and make a conjecture for the general case. In the second section we prove a generalization of the factorization SD 12 = 8 15 D 2 when using D finitely many variables. 6.1 Differences of Transposed Foundations We return to the notation of Section 2.1. In Theorem 4.1.1 and Theorem 4.2.1 we proved that for each n and 0 < k < 1, we have SS(At,k,n) n+1 8 Si).,k,n) when X has either one or two parts. We can also prove this equality in the case when \ is a hook. Theorem 6.1.1 For each n, 0 k < 1, and hook ) with < ii + k, we have SSXt,k,n) Proof To prove n+1 S3(A,k,n). we show that, when considering fill ings with the entries taken from the set {1, 2,.. , n+ 1}, there is an bijection between the set of SSYTx of shape S, k, n) with content v and lattice reading word and the set of SSYTx of shape s(At, k, n) with content v and lattice reading word. As in Theorem 4.1.1, we simply consider the map that transposes the foundation of a given tableau. ssçt,k,n) n+ SS(A,I,n), . 133 CHAPTER 6. REDUCTION TO FINITE VARIABLES Given any tableau 7j of shape S(A, k, n) and content i’, this map gives us a tableau 7 of shape $(\t, k, n) and content v. Now suppose that 7j is a SSYT with lattice reading word. The first row of A strictly increases by Lemma 2.1.1 and the first column of A strictly increases since the tableau is semistandard. Therefore in 7, the foundation At is semistandard. In fact, the first row and the first column of At strictly increase. Now suppose that the reading word of 7 was not lattice. Then, when reading the foundation At of 7, we must come to a point where we have read two j + l’s but no j. Since both the first row and first column of At strictly increase, one of the j +1’s appears ill the first row and the other j +1 appears in the first column. Since 7j has a lattice reading word and contains these two j + l’s in its foundation A, a j must appear somewhere in A. Thus At contains a j as well. Since At is semistaridard, either the j appears to the left of the j + 1 in the first row of At or the j appears above the j + 1 in the first column of At. Either way, this j is read before reading the second j + 1, contradicting our assumption. Therefore the reading word of At Ls is lattice. Since At is semistandard and the entries of the each foundation are contained in {2—k, 3—k, , n+1}, Lemma 2.2.3 now shows that 7 is a SSYT with lattice reading word. Thus when restricted to fillings with entries that are taken from the set {1, 2,.. , n + 1}, we have a map from the set of SSYTx of shape S(A, k, ii) with content ii and lattice reading word to the set SSYTx of shape S(At, k, n) with content v and lattice reading word. This map is clearly its own inverse. Thus we obtain a bijection. I . . . . Since we have proven the finite variable equality S8Q,k,n) n+i SS(),k,n) for these simple shapes A, one might ask for which other partitions A is this equality true. We make the following conjecture. Conjecture 6.1.2 For each n 1, k 0, and partition A such that $(A, k, n) and S(At, k, n) are connected skew diagrams we have Ssp,k,n) n+1 Ssp.,k,n). For each pair n, k, there are many partitions A such that both S(A, k, n) and S(At, k, n) are defined. Namely, for all partitions A such that ökl ç A c ((n + k)n+k). 134 CHAPTER 6. REDUCTION TO FINITE VARIABLES n+k I I n+k Both will be connected skew diagrams so long as Sk+l C ) C ((n + k)nL). Computer-assisted calculations have shown that Conjecture 6.1.2 holds for the following values of the pair n, k, when searching through all pairs of connected skew shapes $,k,n), S(At,k,n). • n = 2, 0 < k <5, • n = 3, 0 k <4, and • n = 4, 0 k 1. When n = 1, the conjecture gives an equality in two variables. In this case it is not hard to check that the only pairs of connected skew shapes S, k, n), S(At, k, n) with nonzero skew Schur functions in two variables have ,\ = so the conjecture does hold for n 1. As ii and k increase, the number of shapes S, k, n) grows quickly. This search space can be reduced by oniy considering the partitions ) such that ) is contained in ön+k, since otherwise both skew diagrams k, n) and S(,\t, k, ii) contain a column of length n + 2, which implies that both skew Schur functions equal 0 in n + 1 variables. Nevertheless, as n and k increase the average size of the shapes increase, which makes it very time-consuming to compute each skew Schur function SS(,\,k,n). This makes computationally 135 CHAPTER 6. REDUCTION TO FINITE VARIABLES verifying Conjecture 6.1.2 for a given pair n, k difficult for larger values of n and k. 6.2 Factoring in Finite Variables In this section we are interested in generalizing the factorization result 2 e 1 SD D = when working with finitely many variables. We begin by inspecting Theorem 1.6.5, which stated that for skew dia , we have 2 grams D , D 1 2 S 1 SD D = 2 •D 1 D 8 + 2 0 1 D 8 • D Example Suppose we have the following two skew diagrams. The concatenation and near-concatenation are given by the following. = 2 1 D 2 ® 1 D = D From Theorem 1.6.5 we can conclude that 2 SD = 2 1 SD GD 1 SD . •D + 2 1 D 5 We note that the diagram D 1 D contains a column of length 5, whereas , and D 2 each of D , D 1 1 0 D only contain columns of length 3 or less. Thus we have 2 .D = 0 and 1 SD . 2 G 1 SD D gives a non-trivial factorization of 2 4 SjSD 2 G 1 SD D 136 in four variables. CHAPTER 6. REDUCTION TO FINITE VARIABLES In order to state the next few results, we find it convenient to make the , 2 1 and D following notational convention. For a pair of skew diagrams D , and let 12 1 we shall let l denote the length of the right-most column of D of . 2 D denote the length of the left-most column Corollary 6.2.1 If l + 12 n + 1, then we have SD 1 SD . GD = 2 1 SD 2 Proof Using Theorem 1.6.5 gives SD = 2 1 SD 2 .D 1 SD + GD 1 SD . 2 2 contains a column of length > n, 1 D However, if 11 + 12 > n + 1, then D which shows that 2 GD = 2 1 SD SD as desired. 1 SD , .D = 0. Therefore 2 1 SD . We now generalize to our main result for factoring skew Schur functions 1 and D 2 as before, in finitely many variables. We consider skew diagrams D ®j < , l2}, so that D 1 2 is a skew but now assume that the overlap i min{1 1®D diagram. Theorem 6.2.2 If l. +12 n+i, then we have SD 1 SD . ØD = 2 1 D 8 2 Proof We are only interested in fillings using the values {1, 2, , n}. We let x 1 and ,x 1 , 2 ,x denote the first i entries of the right-most column of D entries denote the last of the left-most i . 2 D Then column of y, , Y2, 1 y , 1 2 consists of a SSYT of shape D D any SSYT of shape D 1 and a SSYT of < shape D 2 such that x 3 3 for each j = 1,2,.. , i. y . . . . . . . . 137 .. CHAPTER 6. REDUCTION TO FINITE VARIABLES 1 and a SSYT of shape Conversely, suppose we have a SSYT of shape D . We intend to show that x <Yj for each j = 1, 2,. , i. 2 D 1 + j for each j = 1,2,. ..,i. If not, then We claim that x < ri—I > n—li +j for some 1 <j <j• Since there are li_i boxes below x, and since the columns of the tableau strictly increase we find that the last entry in 1 +j this column is larger than n. Since this is impossible, we have x 3 <n—i for each j = 1, 2,. , i, as claimed. . . . . y1 Y2 12 yi 11 yi We also claim that y i+j for each j = 1,2,...,i. If not, then 3 12 < < i for some 1 i. Since there are 12 i + j + j j 1 boxes 12 Yj above y, and since the columns of the tableau strictly increase we find that the first entry in this column is less than 1. Since this is impossible, we have Yj 12 —i+j for each j = 1,2,...,i, as claimed. By assumption, Ti i <12 i. Thus, for any SSYT of shape D 1 and any SSYT of shape D 2 we have < — — — — — xi <fl—1 1+ <j 12 for each j = 1, 2,. , i. Therefore this gives a SSYT of shape D 1ØD . 2 Therefore 2 , as desired. 2 Ø%D = ss 1 SD . . • 138 CHAPTER 6. REDUCTION TO FINITE VARIABLES Example With the following skew diagrams D 1 and D 2 we have 11 + 12 3 + 3 = 6 4 + 2 = n + i. Thus, Theorem 6.2.2 gives SD D 2 G 1 4 8 . 2 1 D = When using Theorem 6.2.2 to check a pair of diagrams for equality, one hopes that the pair shares the same collection of factors. Even when this is not the case, we may sometimes delve further into the products that arise in order to check for equality. Example We wish to show that the following two diagrams give the same skew Schur function in n = 5 variables. We have indicated the breaks where Theorem 6.2.2 applies. = 1 D = 2 D We let A = (4,3,3, 1, 1, 1)/(2,2), B = (1,1,1), C = (2,1,1,1), and D = (3,3,3,1,1)/(2,2), so that D 1 = B® 2 = D® A and D 2 C. The 2 orem 6.2.2 shows that 8 We note that 2 =5 SCSD. 1 =5 SASB and SD D A® B = (5, 5,5,3,3, 1, 1, 1)/(4, 4,2,2) = C 0 D, as is illustrated below. 139 CHAPTER 6. REDUCTION TO FINITE VARIABLES A®B= =COD Further, we find that 5 A.B =5 S(3,3,3,1,1,1)/(2,2)S(1,1,1,1) =5 8 G.D from applying Theorem 6.2.2 to both A B and C D. A•B= CD= Thus we obtain 1 SD 5 SASB + SAØB —5 A.B 5 —5 S(3,3,3,1,1,1)/(2,2)S(1,1,1,1) —5 SC.D —5 D 5 C 8 + SGQD —5 140 + (5,5,5,3,3,1,1,1)/(4,4,2,2) CHAPTER 6. REDUCTION TO FINITE VARIABLES We have the following result to aid us when we are inspecting an equality of the form 5 BØA AGB = 5 Lemma 6.2.3 For skew diagrams A and B, we have AOB = SBOA 5 if and only if 5 A.B Proof Using Theorem 1.6.5 and the fact that mediately follows. SASB = 5 A, B the result im For the purposes of the factoring that results from Theorem 6.2.2, it is generally easier to work with diagrams that have longer columns. Therefore, with respect to Theorem 6.2.2, it is usually more convenient to inspect the pair A B, B A in place of the pair A 0 B, B 0 A. . In the statement of the next lemma, we let a 1 and ar denote the lengths of the left-most and right-most column of A, respectively. Further, we let A a 1 denote the diagram obtained by removing the left-most column from A and we let A ar denote the diagram obtained by removing the right most column from A. We also make the same notational conventions for the diagram B. — — Lemma 6.2.4 LetA andB be skew diagrams with ar+bj = n and br+ai and 5 , then we have 5 1 SB_b,,SA_a A—bt B —ar AOB =, SB®A. = fl Proof Using Theorem 6.2.2 and our assumption that SA_arSB_bj SB_br 5 Aat, we have SA.B n n Bbr S(ln)SA_at 5 SB.A Thus Lemma 6.2.3 shows that A®B = SBOA. 5 • The simplest application of the previous lemma is the following corollary. Corollary 6.2.5 Let n = 1 a + b and 1 <i S((la)Ø. (b))o((la)Ø. (ib)) 2 < <min{a, b}, then (lb))Ø((la)Ø (ib)). S((la)G. 1 141 CHAPTER 6. REDUCTION TO FINITE VARIABLES Proof Take A = (la) 0 (ib) and B = (1) ®2 (ib) in Lemma 6.2.4. • Example Taking a = 3, b = 2, i 1 = 2, and i 2 = 1 in Corollary 6.2.5 we find 1 and D 2 are as shown below. that 2 GD =5 S21 where D 1 SD ®D 2 D = 1 ®D 1 D = 2 Although the techniques in this section may be used to explain many of the finite variable equalities of skew Schur functions, they seem inadaquate when it comes to proving the following conjectured equalites. Conjecture 6.2.6 For each n > 4, ( S((2)Ø(ln_l))Ø ( 2 ln_1))Ø(l) (l2)Ø Example Here we see the pairs for n = 4 and n = 5. “S n=4 n=5 This conjecture has been verified for the values 4 n 11. We finish this chapter with the following result, which gives the factor ization of any skew diagram in n = 2 variables. 142 CHAPTER 6. REDUCTION TO FINITE VARIABLES Theorem 6.2.7 Consider a connected skew diagram D. If D has a column of length larger than two, then 5 D =2 0. Otherwise, if j is the number of )) flk(5(k)), where the ek are , 1 (s( columns of length two in D, then 5 D =2 nonnegative integers, only finite number of which are nonzero. Proof Clearly, if D has a column of length larger than two, then SD =2 0. Suppose that all columns of D have length less than or equal to 2, and let j be the number of columns of length equal to 2. If two columns of length two are adjacent, then their overlap is at most i = 2 and Theorem 6.2.2 shows that we can factor the skew diagram by splitting the diagram between these columns. Further, whenever a column of length two is adjacent to a column of length one, then their overlap is at most i = 1 and Theorem 6.2.2 shows that we can factor the skew diagram by splitting the diagram between these columns. Through these factorizations, we can collect all the columns of length two into the term (5(,))3. The only remaining diagrams that could not be factored are rows. These give rise to a product of the form fJk(S(k))ek. I 143 Chapter 7 Conclusion The aim of this thesis was to determine instances of Schur-positivity. In Section 2.3 we proved Theorem 2.3.1, which provided a collection of Schur-positivity results for each sum of fat staircases D. In fact we obtained a Schiir-positivity result by augmenting D with any skew diagram \/t. The remainder of Section 2.3 sought to determine necessary conditions for a dia gram to be a sum of fat staircases. Theorem 5.3.1 and Theorem 5.3.2 gave necessary and sufficient conditions for certain simple skew diagrams to be sums of fat staircases. Namely, these results inspected skew diagrams of the ). m form 6a/(m) and ö,./(1 In Section 3.3 we showed that for each composition c = (c,. , cj, and each h and k with h n + k and 0 k h, we can determine the entire Hasse diagram which describes which pairs of skew diagrams of the form <; k), S(i, c; k) have Schur-positive difference and which are Schur incomparable, where ) and u are hooks of size h. Expressions for certain Schur-positive differences were given in Section 3.2. Chapter 4 looked at some special cases of differences of fat staircases with bad foundations in which the foundations of the two diagrams were transposes of each other. Equality in finite variables for these diagrams was also discussed, which led to Conjecture 6.1.2. Most of the results of the earlier chapters were extended in Chapter 5 to yield results for the fat staircases with complementary foundations. Many of the proofs in this thesis relied heavily on Lemma 2.2.2 and Lemma 2.2.3. In fact, nearly every result from Chapter 2 to Chapter 5 used at least one of these two lemmas. The defining structure of the fat staircases was made precisely so that we could develop these results. Unfor tunately these fat staircases are the only partitions for which Lemma 2.2.2 and Lemma 2.2.3 hold. As we saw with the sums of fat staircases, some generalizations can still be reached with these techniques. . 144 . CHAPTER 7. CONCLUSION However, there is still a vast amount of questions remaining about Schur positivity and Schur-equality. There is significant interest in the resolution of these and many other related problems. 145 Bibliography [1] S.H. Assaf and P.R.W. McNamara, A Pieri Rule for Skew Shapes, arXiv:0908.0345v1, (2009). [2] C.M. Ballantine and R.C. Orellana, Multiplicities in the Kronecker Prod uct, Electronic Journal of Combinatorics 12 R28, 1—26, (2005). [3] H. Barcelo and A. Ram, Combinatorial Representation Theory, New Perspectives in Geometric Combinatorics 38, 23—90, (1999). [4] F. Barekat and S. van Willigenburg, Composition of Transpositions and Equality of Ribbon Schur Q-Functions, Electronic Journal of Combina torics 16 RhO, (2009). [5] N. Bergeron, S. Mykytiuk, F. Sottile, and S. van Willigenburg, Pieri Operators on Posets, Journal of Combinatorial Theory, Series A 91, 84-110, (2000). [6] F. Bergeron, R. Biagioli, and M.H. Rosas, Inequalities between Littlewood-Richardson coefficients, Journal of Combinatorial Theory, Se ries A 113, 567—590, (2006). [7] C. Bessenrodt, On Multiplicity-free Products of Schur P-functions, An nals of Combinatorics 6 (2), 119—124, (2002). [8] L.J. Billera, H. Thomas, and S. van Willigenburg, Decomposable Com positions, Symmetric Quasisymmetric Functions and Equality of Ribbon Schur Functions, Advances in Mathematics 204, 204—240, (2006). [9] D. Bravo and L. Lapointe, A Recursion Formula for k-Schur Functions, Journal of Combinatorial Theory, Series A 116, 918—935, (2009). [10] A. Brown, S. van Willigenburg, M. Zabrocki, Expressions for Catalan Kronecker Products, arXiv:0809.3469, (2008) 146 BIBLIOGRAPHY [11] A.S. Buch, A. Kresch, and H. Tamvakis, Littlewood-Richardson Rules for Grassmannians, Advances in Mathematics 185, 80—90, (2004). [12] J.O. Carbonara, A Combinatorial Proof of the Equivalence of the Clas sical and Combinatorial Definitions of Schur Function, Journal of Com binatorial Theory, Series A 72, 293—301, (1995). [13] C. Carré and B. Leclerc, Splitting the Square of a Schur Function into its Symmetric and Anitsymmetric Parts, Journal of Algebraic Combi natorics 4, 201—231, (1995). [14] J. Carrell, Chern Classes of the Grassmanians and the Schubert Calcu lus, Topology 17, 177—182, (1978). [15] A.L. Cauchy, Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes coritraires par suite des transposition opérés entre les variables qu ‘elles renferment, Journal de 1’ Ecole Polytechnique 10, 29—112, (1815). [16] S. Cho, E. Jung, and D. Moon, A Combinatorial Proof of the Reduction Formula for Littlewood-Richardson Coefficients, Journal of Combinato rial Theory, Series A 114, 1199—1219, (2007). [17] C.W. Curtis, Pioneers of Representation Theory: Frobenius, Burnside, Schur, and Braner, American Mathematical Society, (1999). [18] 5. Fomin, W. Fulton, C. Li, and Y. Poon, Eigenvalues, Singular Values, and Littlewood-Richardson Coefficients, American Journal of Mathemat ics 127, 101—127, (2005). [19] 5. Fomin and C. Greene, A Littlewood-Richardson Miscellany, European Journal of Combinatorics 14, 191—212, (1993). [20] F.G. Frobenius, Uber Gruppencharaktere, Sitzungsberichte der Preussis chen Akademie der Wissenschaften zu Berlin (1896), 985—1021; Gesam melte Abhandlungen III. 719—733. [21] F.G. Frobenius, Uber die Primfactoren der Gruppendeterminante, Sitzungsberichte der Preussischen Akademie der Wissenschaften zu Berlin (1896), 1343—1382; Gesammelte Abhandlungen III, 38—77. [22] F.G. Frobenius, Uber die Darstellung der endlichen Gruppen durch un eare Subs titutionen, Sitzungsberichte der Preussischen Akademie der Wissenschaften zu Berlin (1897), 944—1015; Gesammelte Abhandlungen III, 82—103. 147 BIBLIOGRAPHY [23] V. Gasharov, A Short Proof of the Littlewood-Richardson Rule, Euro pean Journal of Combinatorics 19, 451—453, (1998). [24] C. Gutschwager, On Principal Hook Length Partitions and Durfee Sizes in Skew Characters, to appear in Annals of Combinatorics, arXiv:0802.0417v2, (2008). [25] C. Gutschwager, On Base Partitions and Cover Partitions of Skew Characters, Electronic Journal of Combinatorics 15 (1) N30, (2008). [26] C. Gutschwager, Equality of Multiplicity Free Skew Characters, Journal of Algebraic Combinatorics 30, (2009). [27] C. Gutschwager, On Multiplicity-Free Skew Characters and the Schubert Calculus, to appear in Annals of Combinatorics, arXiv:math/0608145v2, (2007). [28] H. Salmasian, Equality of Schur’s Q-function and their Skew Analogues, Annals of Combinatorics 12, 325—346, (2008). [29] J. Haglund, K. Luoto, S. Mason, and S. van Willigenburg, Refinements of the Littlewood-Richardson Rule, arXiv:0908.3540v2, (2009). [30] P. Hanlon and S. Sundaram, On a Bijection between Littlewood Rich ardson Fillings of Conjugate Shape, Journal of Combinatorial The ory, Series A 60, 1—18, (1992). [31] T. Hawkins, The Origins of the Theory of Group Characters, Archive for History of Exact Sciences 7 (2), 142-470, (1971). [32] K.G. J. Jacobi, Dc functionibus alternatibus earumque divisione per productum e differerentiis elementorum conflatum, Crelle’s Journal 22, 360—371, (1841); Werke 3, 439—452. [33] R.C. King, C. Tollu, F. Toumazet, Factorisation of Littlewood Richardson Coefficients, Journal of Combinatorial Theory, Series A 116, 314—333, (2009). [34] R.C. King, T.A. Welsh, and S. van Willigenburg, Schur Positivity of Skew Schur Function Differences and Applications to Ribbons and Schu bert Classes, Journal of Algebraic Combinatorics 28: 139—167, (2008). [35] D.E. Knuth, Permuatitions, Matrices, and Generalized, Young Tableaux, Pacific Journal of Mathematics 34, 709—727, (1970). 148 BIBLIOGRAPHY [36] C. Kostka, Uber den Zusammenhang zwischen einigen Formen von sym metrischen Functionen, Crelle’s Journal 93, 89—123, (1882). [37] T. Lam, A. Postnikov, and P. Pylyavskyy, Schur Positivity and Schur Log-Concavity, American Journal of Mathematics 129, 1611—1622, (2007). [38] T. Lam and P. Pylyavskyy, Cell Transfer and Monomial Positivity, Jour nal of Algebraic Combinatorics 26 (2), 209—224, (2007). [39] T. Lam and P. Pylyavskyy. P-Parition Products and Fundamental Quasi-symmetric Function Positivity, Advances in Applied Mathematics 40 (3), 271—294, (2008). [40] L. Lapointe and J. Morse, A k-tableau Characterization of k-Schur Func tions, Advances in Mathematics 213, 183—204, (2007). [41] A. Lascoux, B. Leclerc, and J.-Y. Thibon, Ribbon Tableaux, Hall Littlewood Symmetric Functions, Quantum Affine Algebras, and Unipo tent Varieties, Journal of Mathematical Physics 38 (3), 1041—1068, (1997). [42] D.E. Littlewood, The construction of invariant matrices, Proceedings of the London Mathematical Society 43 (2), 226—240, (1937). [43] D.E. Littlewood and A.R. Richardson, Group Characters and Algebra, Philosophical Transactions of the Royal Society of London, Series A 233, (1934). [44] I.G. Macdonald, A New Class of Symmetric Functions, Actes du 20e Séminaire Lotharingieri 372 (20), 131—171, (1988). [45] I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd Edi tion, Oxford University Press, New York, USA, (1995). [46] S. Mason, A Decomposition of Schur Functions and an Analogue of the Ro binson-Schensted-Knuth Algorithm, Séminaire Lotharingien de Com binatoire 57, (2008). [47] P.R.W. McNamara, Necessary Conditions for Schur-Positivity, Journal of Algebraic Combinatorics 28 (4), 495—507, (2008). [48] P.R.W. McNamara and S. van Willigenburg, Towards a Combinatorial Classification of Skew Schur Functions, Transactions of the American Mathematical Soceity 361, 4437—4470, (2009). 149 BIBLIOGRAPHY [49] P.R.W. McNamara and S. van Willigenburg, Positivity Results on Rib bort Schur Function Differences, European Journal of Combinatorics 30, 1352—1369, (2009). [50] O.H. Mitchell, Note on determinants of powers, American Journal of Mathematics: 4 (1), 341—344, (1881). [51] H. Narayanan, On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients, Journal of Algebraic Combinatorics 24 (3), 347—354, (2006). [52] Y. Numata, Pieri ‘s Formula for Generalized Schur Polynomials, Journal of Algebraic Combinatorics 26 (1), 27—45, (2007). [53] A. Okounkov, Log- Concavity of Multiplicities with Applications to Char acters of U(oo), Advances in Mathematics 127 no. 2, 258—282, (1997). [54] M. Pieri, Sul Problema Degli Spazi Secanti, Rendiconti Istituto Lom bardo 26 (2), 534—546, (1893). [55] K. Purbhoo, Puzzles, Tableaux, and Mosaics, Journal of Algebraic Com binatorics 28, 461—480, (2008). [56] K. Purbhoo and F. Sottile, A Littlewood-Richardson Rule for Grassrnan nian Permutations, Proceedings of the American Mathematical Society 137 (6), 1875—1882, (2009). [57] K. Purbhoo and S. van Willigenburg, On Tensor Products of Polynomial Representations, Canadian Mathematical Bulletin 51, 584—592, (2008). [58] E. Rassart, A Polynomial Property for Littlewood-Richardson Coeffi cients, Journal of Combinatorial Theory, Series A 107, 161—179, (2004). [59] V. Reiner, K.M. Shaw, and S. van Willigenburg, Coincidences among Skew Schur Functions, Advances in Mathematics 216, 118—152, (2007). [60] J.B. Remmel and M. Shimozono, A Simple Proof of the Littlewood Richardson Rule and Applications, Discrete Mathematics 193, 257—266, (1998). [61] G. de B. Robinson, On the Representation of S, American Journal of Mathematics 60, 745—760, (1938). [62] M.H. Rosas, The Kronecker Product of Schur Functions Indexed by Two Row Shapes or Hook Shapes, Journal of Algebraic Combinatorics 14 (2), 153—173, (2001). 150 BIBLIOGRAPHY [63) B.E. Sagan, The Symmetric Group: Representations, Combinatorial Al gorithms, and Symmetric Functions, Springer-Verlag, New York, (2001). [64] B.E. Sagan, Robinson-Schensted Algorithms for Skew Tableaux, Journal of Combinatorial Theory, Series A 55, 161-493, (1990). [65] C.E. Schensted, Longest Increasing and Decreasing Subsequences, Cana dian Journal of Mathematics 13, 179—191, (1961). [66] I. Schur, Uber eine Klasse von Matrizen, die sich einer gegebenen Matrix zuordnen lassen, Dissertation, Berlin (1901); Gesammelte Abhandlun gen, Springer-Verlag, Berlin (1973), I, 1—73. [67] M.P. Schützenberger. La correspondence de Robinson, in Combinatoire et Representation du Groupe Symétrique, Lecture Notes in Mathematics 579, 59—135, (1977). [68] K.M. Shaw and S. van Willigenburg, Multiplicity Free Expansions of Schur P-Functions, Annals of Combinatorics 11, 69—77, (2007). [69] R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, UK, (1999). [70] J.R. Stembridge, On Multiplicity-Free Products of Schur Functions, An nals of Combinatorics 5, 113—121, (2001). [71] J.R. Stembridge, Enriched P-partitions, Transactions of the American Mathematical Society 349 (2), 763—788, (1997). [72] G.P. Thomas, On a Construction of Sch’ützenberger, Discrete Mathe matics 17, 107—118, (1977). [73] G.P. Thomas, On Schensted’s Construction and the Multiplication of Schur Functions, Advances in Mathematics 30, 8—32, (1978). [74] H. Thomas and A. Yong, Multiplicity-Free Schubert Calculus, to appear in Canadian Mathematical Bulletin of Mathematics, arXiv:math/051 1537v2, (2007). [75] M.A.A. van Leeuwen, The Robinson-Schensted and Schützenberger Al gorithms, an Elementary Approach, Electronic Journal of Combinatorics 3 (2) R15, (1996). [76] 5. van Willigenburg, Equality of Schur and Skew Schur Functions, An nals of Combinatorics 9, 355—362, (2005). 151 BIBLIOGRAPHY [77] T. Watallabe, On the Littlewood-Richardson Rule in Terms of Lattice Path Corabinatorics, Discrete Mathematics 72, 385—390, (1988). [78] D.E. White, Some Connections Between the Littlewood-Richardson Rule and the Construction of Schensted, Journal of Combinatorial Theory, Series A 30, 237—247, (1981). [79] A.V. Zelevinsky, A Generalization of the Littlewood-Richardson Rule and the RobinsonSchensted-Knuth Correspondence, Journal of Algebra 69, 82—94, (1981). [80] P. Zinn-Justin, Littlewood-Richardson Coefficients and Integrable Tilings, The Electronic Journal of Combinatorics 16 R12, (2009). 152
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Schur-positivity of differences of augmented staircase...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Schur-positivity of differences of augmented staircase diagrams Morin, Ma 2010
pdf
Page Metadata
Item Metadata
Title | Schur-positivity of differences of augmented staircase diagrams |
Creator |
Morin, Ma |
Publisher | University of British Columbia |
Date Issued | 2010 |
Description | The Schur functions {s_lambda} and ubiquitous Littlewood-Richardson coefficients are instrumental in describing representation theory, symmetric functions,and even certain areas of algebraic geometry. Determining when two skew diagrams D₁, D₂ have the same skew Schur function or determining when the difference of two such skew Schur functions SD₁ - SD₂ is Schur-positive reveals information about the structures corresponding to these functions. By defining a set of staircase diagrams that we can augment with other (skew) diagrams, we discover collections of skew diagrams for which the question of Schur-positivity among each difference can be resolved. Furthermore, for certain Schur-positive differences we give explicit formulas for computing the coefficients of the Schur functions in the difference. We extend from simple staircases to fat staircases, and carry on to diagrams called sums of fat staircases. These sums of fat staircases can also be augmented with other (skew) diagrams to obtain many instances of Schur positivity. We note that several of our Schur-positive differences become equalities of skew Schur functions when the number of variables is reduced. Finally, we give a factoring identity which allows one to obtain many of the non-trivial finite-variable equalities of skew Schur functions. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-06-14 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0071003 |
URI | http://hdl.handle.net/2429/25747 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2010-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_spring_2010_morin_matthew.pdf [ 2.86MB ]
- Metadata
- JSON: 24-1.0071003.json
- JSON-LD: 24-1.0071003-ld.json
- RDF/XML (Pretty): 24-1.0071003-rdf.xml
- RDF/JSON: 24-1.0071003-rdf.json
- Turtle: 24-1.0071003-turtle.txt
- N-Triples: 24-1.0071003-rdf-ntriples.txt
- Original Record: 24-1.0071003-source.json
- Full Text
- 24-1.0071003-fulltext.txt
- Citation
- 24-1.0071003.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-0071003/manifest