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 D1, D2 have the same skew Schur function or determining when the difference of two such skew Schur functions SD1 — 5D2 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 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 Abstract ii 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 1.3 Tableaux 5 1.4 Symmetric Functions 6 1.5 The Littlewood-Richardson Rule 9 1.6 Some Useful Identities for Schur Functions 10 1.7 A Brief History of Schur Functions 12 1.8 Overview of Schur-Positivity Results 15 2 Staircases with Bad Foundations 23 2.1 Regular Staircases 23 2.2 Fat Staircases 27 2.3 Sums of Fat Staircases 33 3 Hook Foundations 43 3.1 Schur Comparability / Incomparability . 43 3.2 Expressions for Schur-Positive Differences 60 3.3 Hasse Diagrams for k> 1 73 4 Differences of Transposed Foundations 91 4.1 Single Part Partitions 91 4.2 Two Part Partitions 95 111 5 Complements in a Rectangle.111 5.1 Preliminaries 111 5.2 Staircases with Hook Complement Foundations 116 5.3 Sums of Fat Staircases 123 5.4 Miscellaneous Results 128 6 Reduction to Finite Variables 133 6.1 Differences of Transposed Foundations 133 6.2 Factoring in Finite Variables 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 decreasing positive integers A = (A1,A2, , A,) with A = n. \1Ve call each A2 a part of A, and if A has exactly k parts we say A is of length k and write 1(A) = k. When A I— n we will also write IA n and say that the size of A is n. We shall use jT to denote the sequence j, j j consisting of r j’s. Under this notation, we shall write A = (k1, k — 17’k—1 . . , U’) for the partition which has r1 parts of size one, r2 parts of size two, ..., and rk parts of size k. Given two partitions A = (A1, . . . , A,) and p = (h,. . . , ,Lim), we let A U ,u denote the partition that consists of the parts A1, .. . , A, /J1,. , ltm placed in weakly decreasing order. We say a = (a1,a2,.. . , ak) is a composition of n, written a = n, if each aj is a positive integer and a = n. As with partitions, we call each a2 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 = (z1,z2,z3,. . . , z) we shall mean the infinite vector z=(z1,z23...,z,O,O,O,...). 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 (A1,2...,A) F-n and fL = (t1,ii2.. .jtk) F-rn, with m < n, k <j, and 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 = (4, 4, 2) and = (3, 1), and form the skew diagram A/si. [=iJr _ H For two boxes b1 and b2 in a diagram D, we define a path from b1 to b2 in D to be a sequence of steps either up, down, left, or right that begins at b, ends at b2, and at no time leaves the diagram D. We say that a diagram D is connected if for any two boxes b1 and b2 of D there is a path from b to b2 in D. If D is not connected we say it is disconnected. 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 = (4, 4, 2) form the skew diagram A/1i. HH and i = (3, 1), and The conjugates, At = (3,3,2,2), shown below. = (2,1,1) and (A/ji)t = At/itt are Finally, we see the skew diagrams (A/i)° and ((A/j)t)° = ((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 t = (5, 1). ‘A’ Li It 3 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. Given two diagrams D1 and D2 the concatenation of D1 and D2, denoted • D2, is the skew diagram obtained by placing D1 and D2 so that the top- right box of D1 is immediately below the bottom-left box of D2. Similarly, the near-concatenation of D1 and D2, denoted D1 0 D2, is the skew diagram obtained by placing D1 and D2 so that the top-right box of D1 is immediately left of the bottom-left box of D2. Finally, if the last column of D1 and first column of D2 are both of length i, then the near-concatenation of depth i of D1 and D2, denoted D1 0 D2, is the is the skew diagram obtained by placing D1 and D2 so that the top-right box of D1 is one step left and i — 1 steps up from the bottom-left box of D2. We note that 0 = 0. Example Let D1 be the skew diagram (2, 2, 2)/(1, 1) and D2 be the Ferrers diagram (4,4,2). Here we show the diagrams D1 D2, D1 0 D2, D1 02 D2, and D1 0 D2. I_ _ __ D1 0 D2 D1 02 D2 D1 03 D2 Given a diagram D, the connected components of D are the maximally connected subdiagrams of D. Any skew diagram D decomposes into a finite number of connected components D1,D2,. . . , D,. Conversely, given con nected diagrams D1,D2,. . . , Dk, we define the diagram D = D, called the direct sum of the D, to be the skew diagram with connected components D1,D2,. . . , Dk such that the top-right box of D is one step left and one step down from the bottom-left box of D1 for i = 1, 2,. . . , k — 1. We note that =0o. 4 CHAPTER 1. INTRODUCTION Example With D1 = (2, 2, 2)/(1, 1) and D2 = (4, 4, 2), as in the previous example, we now show the diagram D1 D2. D12 1.3 Tableaux 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) = (v1,u2...), where Vj is the number of i’s that appear in T. Example Here we consider a semistandard Young tableau 7Ej with shape D1 = (2, 2, 2)/(1, 1) and content (1,0, 1, 2), and a semistandard Young tableau 7 of shape D2 = (4,4,2) and content (2,2,3,2, 1). 1124 3 2335 144 34 7 72 We may sometimes find it useful to take the transpose of a tableau T so that we obtain a tableau of conjugate shape. In these cases we simply 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 subtableau of shape D’. Also, given tableau 7j and 7 of shapes D1 and D2 respectively, we may form the tableaux ‘Tj 7 of shape D1 D2, 7j 7 of shape D1 D2, 7 0 7 of shape D1 0 D2, and 7 O 7 of shape D1 ® D2 (when D1 0 D2 is defined) in the obvious way. 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 1 2 4 _______ 2335 1124 _______ 134 12335 111124 3 334 323135 44 144 14434] 7i07 7027 7037; Of these tableaux, only ‘Jj 0 7 and 7 02 7 are semistandard. 1.4 Symmetric Functions In this section we consider an infinite set of variables x = (xi,x2,...) and the ring of formal power series C[x]. By S, we mean the group of permutations of the letters {1, 2,. . . , n}. We can let each ‘it E S act on elements f(x1,x2,...) C[xj by defining X2,...) f(x(i), X(2),. . . X), n+1, Xn+2,. . (1.1) We are interested in certain functions f(x1,x2,...) C[x] which are fixed 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)= :: xilxi2 . . xfl and the n-th homogeneous symmetric function, h(x)= xilxi2 Xi. 1 2 3 6 CHAPTER 1. INTRODUCTION Given a partition A = )2,. ,A) by the power symmetric function, elementary symmetric function, and homogeneous symmetric function corre sponding to A, we shall mean p(x) Ho e(x) = 11ex, and h(x) = k 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 space. This space, denoted A7, is called the set of homogeneous symmetric 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 ii = (zi,v2,...) we have the weight xT defined by xT = JJx”. Given this weight function, the Schur function corresponding to A is defined to be s.x(x) = xT, (1.2) 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 Finally, given a skew diagram A/ji, the skew Schur function corresponding to )/i is s1(x) = xT, (1.3) where the sum is taken over all SSYTx T of shape The skew Schur 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) = xjx2 = 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. Example We wish to compute the Schur function S(2,i) (x). Thus we need to inspect each SSYT of shape ) = (2, 1). Let ‘T be such a tableau and let i, j, and k be the entries of T as shown below. Since the columns of T must strictly increase, we require that i < k, and, since the rows of T weakly increase, we require i <j. Thus S(2,l)(X) = XXjXi4 i<j, i<k = (xixxk) — XiXjXk j i<k j<i<k = (xixk) — XXjXk j i<k j<i<k = e(l)(x)e(2)( ) — e(3)(x). 8 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 >csA, (1.4) Al—n where n = ji + v, for some coefficients The coefficients appear 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 5A/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 from the top row to the bottom. We say that a sequence r = r1,r2,. . . , is 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]) For partitions A, , and ii, the Littlewood-Richardson coefficient is the 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(22)v is the number 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. ____ 1j2 v= (4,1) v= (3,2) v= (3,1,1) v= (2,2,1) Therefore S(4,3,2)/(2,2) = S(4,) + S(3,2) + 5(3,1,1) + 5(2,2,1). For any f = aAs.X E A, we say that f is Schur-positive, and write f 0, if each aA > 0. Further, we say that f is multiplicity-free if each aA E {0, 1}. Therefore, the Littlewood-Richardson rule shows that both s,s,1 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 D1 ‘- D2 if SD1 s 8D2• If we consider the relation )— on the set of all Schur-equivalent classes of diagrams (i.e. [D]3 = {D’sD = 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 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, = 5D0. (1.6) 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 reducible. If D = D1 D2, then we have = (1.7) Proof Any SSYT of shape D1 D gives rise to a SSYT of shape D1 and a SSYT of shape D2 by taking the obvious subtableaux. Conversely, any SSYTx 7 of shape D1 and 7 of shape D2 give rise to the tableau ‘Tj 7 of shape D1 D2, which is clearly semistandard. • Lastly, we mention another expression for the product 5D12 Theorem 1.6.5 [[5], Chapter 1.5, Example 2.1 (a)] For skew diagrams D1 and D2, we have SD12 = 5D12 +5D1OD2 (1.8) Proof Given SSYTx 7j of shape D1 and 7 of shape D2 we let a be the entry of the top-right box of D1 and b be the entry of the bottom-left box of D2. If a < b then Ti 0 7 is a SSYT, and if a > b then Ti 7 is a SSYT, and clearly all SSYTx of shape D1 0 D2 and D1 . D2 arise in this fashion. I 11 CHAPTER 1. INTRODUCTION 1.7 A Brief History of Schur Functions 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, given a composition 1u = u2,. . . , tj), we may obtain the alternant Ihir(1) 1ir(l) a(xi,. . . ,x1) = sgn(r)x1 . rES1 where the S1 is the group of permutations of {1, 2, . .. , l}, and sgn(7r) is the sign of the permutation ir. Then, taking a partition A of length 1 and using 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 = (A1,A2, . . . , A1), then s = 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 irreducible character xA to the function It was by this type of connection between representations of the symmetric group and homogeneous symmetric 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 5A 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 X X’1 = describing the multiplicities of the irreducible character xA in the product of the irreducible characters and ‘, and (S 0 SV) t= cS’, describing the multiplicities of the Specht module 5A in the induced tensor product of the Specht modules S” and 5i 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 manian, the cup product of two Schubert classes cr1. and u,,, is given by g1 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 pute the Littlewood-Richardson coefficients However, it is known that 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 recent results on determining the equivalence classes [D]3 of Schur-equivalent 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 a2 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 for each i = 1, . . . , l(?), where is 0 for any i > l(t). The relation - defines 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 — 5L’/p >8 0, then 1. rowsk(A/I1) rowsk(v/p) for all k, 2. colsj(?../i) colsj(v/p) for all 1, and 3. rectk,l)/,u) rectk,1(v/p) for all k, 1. Given a skew diagram )/p, the base partition of )/i is denoted B/t) and is defined as the intersection of all diagrams v such that 0. The 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 5x/ Sv/p 0 requires that B(A/) ç B(v/p) and C(v/p) ç C(A/). 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 “ — k} for each k, and := — 1 + #{kPk — k > 1u — l} for each 1. Conjecture 1.8.2 (Conjecture 5.1, /18]) For partitions A and we have S)*S,3* — 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 ji/c and ii//3, if (A,p) = (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, are hooks with o=/3. 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 set of pairs (cr, ii), with having at most p parts, and largest part bounded 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/1i and v/p such that A + v and + p both have even parts, we have — S\//ASV/p >8 0. 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 — 5/ILSV/p 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) = (vj,v3,5...) and sort2(A,p) = (v2,46. . Theorem 1.8.8 (Conjecture 2.7, [18]) Given partitions A and p, we have Ssortl(),)Ssort2()L) — 5Ap s 0. 18 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 5sort2(,)/sort,p) —5A/LSv/p s 0. Given a partition A, let A”1 (A Ai+n, Ai+2n, . . .). In this way the parts of A are distributed among the partitions A[i,?] for i = 1,. . . Theorem 1.8.10 (Conjecture 6.4, [41]) For integers 1 m < n and a partition A, we have fl m fJ S[i,n] — S[i,m] > 0. A generalization of this result to skew shapes can also be given. Theorem 1.8.11 (Theorem 13, [37]) Let A(’)/i(1), ..., A()/1i(’ , be n skew shapes, let A = U be the par tition obtained by the decreasing rearrangement of the parts in all and = U. Then we have > 0. Given two partitions A and ji, we can define A V ji and A A ji by A V i := (max{A1, max{A2,Ii2},...) and A A := (min{A1,ii}, min{A2Ji2},. . Then, given skew diagrams A/1i and v/p, the operators V and A can be defined on pairs of skew diagrams via (A/ii) V (v/p) := (A V v)/( V p) and (A/1i) A (v/p) := (A A v)/(i A p). Theorem 1.8.12 (Conjecture 4.6, [38]) Let A/1u and v/p be any two skew shapes. Then we have SA/Sii/p 0. 19 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 multiplicity- free 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 rows1(/t) and rows2/t), thus we may identify the skew Schur function using the overlap notation = {rows1/i)ro2(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 )/1u. In this situation 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 — r), 0 if and only if,u -< A and 1(A) = 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 T be compositions such that 1(a) = s > 0 and 1(r) = t> 0, and let a- and ‘ be sequences of non-negative integers that satisfy the following conditions: 1. The lengths of a- and are s and t respectively; 2. as 1 when s > 0; 3. = 1 when t > 0; 4. ö <min{a, aj4} for 1 <i < s, and ‘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]) Assume a, r, a-, and satisfy Hypothesis 1.8.14. If a b > 2 then we have {a,a,b,rja-,1,5} — {a,a+ 1,b— 1,rja-,1,’} >30 and {a, a, ra-, 1n—1 — {a, a + 1,a2a — 1, -ja-, 1n—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 will be denoted by S, and respectively. For what follows we will also define _i = = 0. Example Here we see the two staircases of length 5: 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. 65 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 6k—l such that skew diagram A/t5k_1 is connected and k A1 ii + k, then we 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 A1 — 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 6k1 is removed. The requirement k < A1, guarantees that the top row of the skew diagram A/Sk_l is non- empty. The diagram S(A, k, n) is connected if k <A1 and has two connected components, A/k_1 and , if k = A1. We also note that the skew diagram S(A, k, n) can be written in the form P/6n+k—1, where a is a partition. Example For k = 0 we have 6k—1 = = 0, and and A overlap in A1 places. 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 For k = 1 we have 6k1 = = 0, and and .\ overlap in — 1 places. Thus k, n) is the diagram SA, 0, n) with its foundation ,\ shifted one to the left. For example, with n = 5, k 1, and ) = (5, 4, 2) we have the following staircase with bad foundation: S,1,5) 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). S(At,4, 5) 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 algebraically from Theorem 1.6.3 since s = s = s, where s6 is a Schur 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 n—4n—3n—2 1 2 n—3n--2n--1 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 the value j twice. Then j 1 since the second value in R is immediately 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 0k—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 — ic1 — 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 5D = 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 sA/,1 = s if and only if A/p = 11 or 27 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 to the left of the staircase and the fact that the content of was the partition 6, which is the sequence of consecutively decreasing integers (n, n — 1,. . . , 2, 1). In fact, if the first row of )/i extends at most 1 box 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 11 given by sequences of the form (n°, (n — 1)°—’,. . . ,2°’, 1a1), where each 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—1)n_1,...,2Q2,)0 where c = (c, . . . , c) is a composition. This composition c has a = = 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 if either D = ii or D v°, where 11j — v > 1 for some i, then ,, D; k) 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 a total of 11j — v times. Therefore D = O and D = are precisely the diagrams in which we are interested. We call a skew diagram D a fat staircase if D = or D = L for some composition . The numbers c, count the number of rows of D with i boxes, for each i. Using this notation the regular staircases may be expressed as = 6(m) and = (1), respectively. We note that the unique semistandard 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 fat hook is defined as a diagram of the form A2’). 28 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Example Here we see the fat staircases 6(1,2,2) and 6(1,2,2) (3,1,2,3) Just as the diagram k, n) was of the form IL/ön+k_1, where 6n+k—1 is a staircase, it would be nice if S, ,c, c; k) was of the form i/67, where 67 is a fat staircase. This requires that 0 k 1 and ,ç = 6 for some com position 13. Thus the diagrams of this form can be written as S(\, 6, ; k) 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. Given a composition c, k > 0, and partitions X, 4a with ) — — k 1(a) we now define S\, , c; k) to be the diagram obtained by placing .A/i immediately below such that the rows of the two diagrams overlap in precisely )4 — — k positions. We call S\, t, c; k) a fat staircase with bad foundation. The subdiagram A/1i is called the foundation of S(\, ,u, a; k). 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 to avoid confusion in the cases when the compositions o = c2, 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) S((2, 1), (2, 2)1; 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 Now we show the fat staircase with bad foundation S(A, , c; 1) for A = (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) satisfy 1’ and 2’ when 0 k 1. Moreover, we have the following result 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 = (cr1,. . . , cj, then the entries in the first row of the foundation 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 if and only if k 1 since it is precisely in that case that the first value in R is not below an entry of &. Furthermore, since there are only k boxes from 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 condition implies that there is at least one more t — 1 in than there are t’s in zic. Since the content of & is (n°, (n — 1)’,.. . , 11), the only 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 each t t 1, can appear at most once in R. 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 ing word, where D1 $ D denotes the disjoint union of the diagrams D1 and D2. Lemma 2.2.3 Let c be a composition, ). and be partitions, and k > 0 such that ) — — k < l(o). If T is a SSYT of shape )/t with lattice reading word such that there are at most k 1 ‘s in the first row of )/t, then 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 in R, so that k > q. Further, let r1 r2 r be the entries of R. 31 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Consider the case k 1. Since r1 = = = rq = 1, we have rq = min(R,k) and for each 1 j n we have the (j + 1)-th smallest value of R,k = 1 + Since k > q, for each 1 j n we have rk rj+q 1 + n+1-i i=1 jrrl j fl—i II 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 r T2 rk ri+4 T2+) r3+, 32 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 r > j-th smallest value of R,k 1 + Also, the entry r3 is beneath precisely boxes, so the entry of L, directly above r3 is cn+i. Thus the columns strictly increase. Therefore This a SSYT with lattice reading word, as desired. • Example Let c = (2, 2, 1), = 0, ) = (3, 2), and k = 1. Consider the SSYT T of shape ) with lattice reading word and only one 1 in the first row of ) shown on the left. This gives rise to the SSYT of shape S, c; 1) with lattice reading word shown on the right. 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 J 1 2 3 4 5 1 2 31 62 3 33 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS let c(zi) be the composition such that = ii. That is, c(v) is the number of parts of i’ equal to i. Then using these compositions we can rewrite SD as 8D= Example Let p=(4,3,3,3,3,3,3), ic= (2,2,2, 1, 1), and D=p/,. Then SD S(4,32i,j,i) +S(3,2i,i,i) +S(3,2i,i) = (3,2,1,1) + S(313) + Thus, when computing the Schur function of D, we are interested in the following diagrams. (3,2,1,1) ‘(3,1,3) L(2,3) For a sum of fat staircases D and a value , D; k). By assumption, we have k 0, we consider the diagram = zi=fat staircase CvS(). When we compute the skew Schur function SS(A,,D;k) we notice that, since the subdiagram D is strictly above the foundation the contents that 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 v=fat staircase D E 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. The next result summarizes the relationship between these fillings. Theorem 2.3.1 Suppose a diagram D p/ii is such that SD = C,S11. 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) obtained by filling the copy of with content ii and filling the copy of )/ identically to its filling in T. -I- 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 A/ and are semistandard. Further T’ has a lattice reading word since checking the lattice condition within the subtableau of shape is 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 image T’ and suppose that T1 T are both SSYT of shape S(A, , D; k) with lattice reading word such that T = T’ = T. Let SX, p, c(v); k) be the shape of T = T’ = T. Then the filling of the foundation A/[L in T1 is the same as the filling of the foundation A/si in T2, and the content of the subdiagram D is v for both T1 and T2. Since there are only c SSYT 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) + S(2,2,l,l,l) = S(13) + (32) is a sum of fat staircases. Here we display D, (1,3), and L(3,2). D L(i,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(A, D; 1) S(), (1, 3); 1) S(?, (3, 2); 1) We can compute that SS,D;1) = 5(3,3,2,2,1) + 5(3,3,2,1,1,1) +S(3,i,i,i,i,i) + 5(3,2,2,2,2) + 5(3,2,2,2,1,1) +S(,i,i,i,i) + 5(2,2,2,2,2,1) + 5(2,2,2,2,1,1,1) and SS(A,(1,3);1) + SS,(3,2)<;1) = 2s(3,l) + 25(3,3,2,1,1,1) + 5(3,3,1,1,1,1,1) + S(3,2)+ 2S(,l,l) +S(2,i,i,i,i) + 5(2,2,2,2,2,1) +S(,l,i,i), 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. 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 that D1 ®j D2 denotes the near-concatenation of D1 and D2 of depth i. That is, if the last column of D1 and first column of D2 are both of length greater than or equal to i, then D1 ® D2 is the is the skew diagram obtained by placing D1 and D2 so that the top-right box of D1 is one step left and i — 1 steps up from the bottom-left box of D2. In other words, the last column of D1 and the first column of D2 overlap in exactly i boxes. Lemma 2.3.2 Let c be a column and D be a skew diagram that is not a sum of fat staircases and let D1 = D ® c and D2 = c ®j D be obtained from D by the addition of a single column c. Then neither D1 nor D2 is a sum of fat staircases. 37 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Proof We shall begin by proving that D2 is not a sum of fat staircases. 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, v3 v+ + 2 for some j. Let n be the length of the column c. We create a tableau T’ of shape D2 and lattice reading word by filling c with the numbers 1,2,. . . , n and by filling the rest of D2 as D is filled in the tableau T. Then T’ is semistandard 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’) = Vj + 1 vj+i + 3 = c(T’)+i + 2. If j = n, comparing the j-th and (j + 1)-th entries of this content gives c(T’) = Vj + 1 vj+ + 3 c(T’)+i + 3. And if j > n, comparing the j-th and (j + 1)-th entries of this content gives = vj v1 + 2 = c(T’)+i + 2. In all cases we see that c(T’) is not a fat staircase. Hence D2 is not a sum of fat staircases. Then, since SDo = 5D is also not a sum of fat staircases, the above shows that c ® D° is not a sum of fat staircases. Now, since SD1 = 5DGc = S(DGc)o = ScoDo, we find that D1 is not a sum of fat staircases. • 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 C1, C2 . . . , Cn. Let D = D0 and, for each i = 1,.. . , n, let D be the subdiagram of D’ consisting of D and the columns c1,. . . , c. Then using Lemma 2.3.2 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 staircases, then we have 1(c) + 1 R0(),l and i + 1 for each ii with c0. Proof We shall consider the case = c GD. As in the proof of Lemma 2.3.2, the second case = D Ø c can then be obtained by rotating diagrams by 180. Suppose 1(c) + 1 e R(),l for some ii with 0. Since c 0, there 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 reading word. Further, c(T’) v + (11(c)). Since 1(c) + 1 e RQ(V),I, we have 1(c) = c(v)+i_ for some k, where z’ (n(”)’,n — o(v)0_,. ., Thus c(T’) = v + (i) = n —1c(v)0_1, . . , n + 1 — k n+1k n — ka(v)0_k +(1v)n(ii)_ = (n + 1(t’)0, . . . , n + 2 — n — 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 0 Ra(v),l for each v with c,, $ 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,1(v) + 2,. . . , 1(v) + 1(c) — i and filling D as in the tableau T. Again, T’ is a SSYT with lattice reading word. Further, c(T’) = ii + (U) + (01(v),1(c)_i). 39 CHAPTER 2. STAIRCASES WITH BAD FOUNDATIONS Since i + 1 e we have i = for some k, where ii = (nv)n, — (M),_1, 1a(v)i) Thus c(T’) = v + () + 1(c)_i) — (O(1/)n n —1n(v)1, , n + 1 — ka(v)n+1_k, n — + (01(v),1(c)_i) = (n + Q(l/)_i . . , n + 2 — k(M)n+1_k, — 2a(v)2,1c(v)l+1(c)_i). 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 Ra(v),l for each v with c 0. • Example Consider the diagram D = (2, 2, 2, 1, 1, 1)/(1), seen below. We have SD = S(2,2,l,1) +S(2,i,i,i,) = (23) + S(42). Therefore, when adding a column, we must avoid lengths and overlaps that are one more that an element of R(2,3),i U R(4,2),i = {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 6 + 1 E R(2,3),i U R(4,2),i the resulting diagram is not a sum of fat staircases. 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 c1, . . . , c and, for each j, let m3 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 I, = 2(l1(c)) Thus, for each j, zi3 is the number of columns of D of length greater than or equal to j. Therefore we have = v3_1 + m, (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 these fat staircases with hook foundations D1,D2 satisfy 8D1 — SD2 0 and 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 D1 >— D2 whenever 5D1 — 8D2 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 [Dj8. 43 CHAPTER 3. HOOK FOUNDATIONS Example Here we show the Hasse diagram for on the collection of stair cases with bad foundations S(A, 0, 7) (or (i); 0) in the fat staircase notation), for ) varying over all hooks of size 7. A line drawn from a diagram D1 to a diagram D2 in an upwards direction indicates that SD1 — 5D2 0. We note that the diagrams along the top are all Schur-incomparable. 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 1u 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 = (cr1, €2, . . . , 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. The restriction h n + k is needed to guarantee that SA, c; k) is a skew diagram for every hook A of size h. For each pair of hooks A, 1u with Aa, ILa Ei, Theorem 3.1.1 and The 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 that S(A, c; k) Js S(, c; k). This describes the chain structure displayed along the right of the Hasse diagrams in the previous examples. Finally, for each pair of hooks A, [t with Aa, I-’i <Eii, Theorem 3.1.4 and Theorem 3.1.5 show that Aa t’i if and only if S(A, c; k) ‘— S(i, ; k). This describes the relationships between the diagrams displayed on the right with the diagrams displayed along the top in the previous Hasse diagrams. 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 with content 6a = (n°, (n — 1)-’,. . . , 2, 1’). This content led us to 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, . . . , x — 1 before 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 Aa < ita and let 0 k 1. Then we have S(it c; k) S(A, a; k). 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 Since Aa < Ita and A IiI, we have A1 > . Let r1 < r < < rj be the values of R,k. We can create a SSYT of shape A by filling the boxes of A as follows. r1 r_1 + 1 c + A1 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 < A1, we have l(S(jt, a; k)) = oj + 1uj < k + A1. Therefore no SSYT of shape S(t, c<; k) with lattice reading word can contain the entry c + A1. Thus no SSYT of shape S(p,, a<; k) with lattice reading word can have the same content as T. Hence, it follows that SS(;k) —8S(A,c;k) s 0. I Theorem 3.1.2 Let A and i be distinct hooks with A = = h < n+k and Aa <fLa ri and let 0 < k < 1. Then we have S(A, ; k) S(j, ; k). Proof Let r1 < r2 < < rfl4 be the values of R,k. We can create a SSYT of shape i by filling the boxes of p as follows. r1 r2 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 r1, r2, . . . , rk. Since r1 < r2 < < rh, the value r1 must appear in the top-left corner of j (A, resp.). Further, once we choose — 1 (Aa — 1, resp.) 47 CHAPTER 3. HOOK FOUNDATIONS of the values r2 <r3 < <rh to appear in the first row of (first row of )., resp.), then 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(, ; k) = ic’/p’ with lattice reading word and content v = c(T) is given by ,‘ (h—i = [t — 1 and the number of SSYTx of shape S(, c; k) = i’/p with lattice reading word and content v = c(T) is given by ,, (h—i Cp i\ ?a1 Since )a < a < we have h + 1 > a + I-a Therefore we have h — ‘a > Pa — 1 and we obtain hAaj>/aij, (3.1) for each i. Therefore (h—i)! (h — ia)!(iia — 1)! aAa1 — (h_i). ri ______ — (h)a)!(Aa1)! h\i = cpvx /ta1 > cv, 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 < ri. 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. 48 CHAPTER 3. HOOK FOUNDATIONS Theorem 3.1.3 Let ). and ,u be hooks with j) = h < n + k and ri a <Ia and let 0 k 1. Then we have S(;\, c; k) S(j, ; k). 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 lattice reading word. Then, letting o; k) = ,i/p and S(j, cv; k) = for partitions ,c, 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 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 first row of ji contains a strictly increasing sequence a1 < 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 < < a, where a = a1. Since can only be filled in one way (in both shapes S(t, c; k) and a1; k)), in order to obtain a tableau of shape S\, a; k) and content i’ we only need to show how to place the values of {ai,a2,...,aa}U{a3.,aj}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 = a1 = a1 = aI+tj—j+2. Again, by the lattice condition, it is clear that any SSYT of shape a1; k) with lattice reading word and content v must also have these values a, a+1, 49 CHAPTER 3. HOOK FOUNDATIONS as the last — j + 1 entries of the first column of A. Since Aa < /ta gives <A1, we have — j + 1 < A1 — j + 1. This gives, IM—j+lA1, (3.2) so these entries do fit in this column. Note that if 1(u) < a + 1, then this sequence of values a, a+1,. . . , a1 is empty and we do not have to worry about placing any entries larger than al + 1. Let M be the multiset {a1,a2,. . . , a} U {a, as,. . . , a_1}. Then M is 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) = al + 1. Let R = {ai,a2,.. .,aa} 0 We note that R {a, a2,. . . , a,La}fl{a, a, . . . , a} since Lemma 2.2.2 shows 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 {a1,a2,.. . , aa}—R and A’ = {a, a,. . . ,a_1}—R. 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 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 > A1. Thus we have R <t1 <A1 <Aa. Now because Aa, (3.3) we can extend the values of R to an increasing sequence b1 <b2 < < 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 — {b1,.. . , b} C M — R contains w = jMj — Aa = [La +j —2— Aa distinct values, each no greater than l + 1. That is, they are an increasing sequence c1 <c2 < <cm, where ci,, < al + 1. We have A1 = [La+IMAa 50 CHAPTER 3. HOOK FOUNDATIONS — 1+(/a+j2Aa)+(jti_j+1) = so we may fill A as shown below. b1 b2 bAa Cl C2 cw a+1 By the definitions of R and the sequence of b, it is clear that b1 = a1 = aç. Thus, a1 < c1. Since the sequence of c is strictly increasing and since od+1 < we have 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, ., x — 2, x — 1 is read before the x is read in A and the lattice 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 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+1, . . . greater than c+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 S(1,c; k) = ic’/p’ with lattice reading word and content v is given by — I” (AUA’)flR,kICp_ [LaIRI and the number of SSYTx of shape S(A, c; k) = ic/p with lattice reading word and content v is given by — ( (AUA’)flR,kI AaIRI SinceAA1>jij>j—1,wehave 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 (Aa RI) — i, (3.6) for each i. 53 CHAPTER 3. HOOK FOUNDATIONS Therefore — (AuA’)nR,kl! CPV — (l(AuA’) flR,kl — (Aa — IRD)!(Aa — IRD! — j(AuA’)nR,kl! - (j(A U A’) fl R,kl - (ILa - l))!(Ita - IRD! aa1 TT /ialRHX l(AUA’)flRck(AalRDi=O ILaAa1 ri ILaRli — CPII,X 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. Theorem 3.1.4 Let A and p be hooks with Al = = h < n + k and Aa, ri and let 0 < k 1. If Aa > then $(A, ; k) $(, <; k). 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 Equation 3.4 held. Namely, we required that 1Uj — j + 1 <A1, RI <Aa, and 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, we note that r i < A1. In order to show Equation 3.3 holds for the assumptions of this theorem, we note that RI < 1Uj < Aa. In order to show Eiation 3.4 holds for the assumptions of this theorem, we note that lta Aa. Therefore we can create a SSYT of shape S(A, ; k) with lattice reading word and content ii whenever there exists a SSYT of shape S(u, c; k) with lattice reading word and content ii. 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 Aa > j > j — 1. Therefore the inequality for the Littlewood-Richardson numbers holds here as well, which proves that S5(A,o1;k) —3S(,o;k) s 0. I Theorem 3.1.5 Let A and be hooks with A = = h < n + k and and let 0 k 1. IfS(A,;k) S(,;k), then Aa i. Proof Towards a contradiction, suppose Aa <IM. As before, we let r1 < r < < Tfl. be the values of Ra,k. We can create a SSYT of shape [1 by filling the boxes of i as follows. r1 r2 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 us with a SSYT T of shape o<; k) with lattice reading word, where p is 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 r1,T2,. . . , rh. Since r1 < r < < Th, the value r1 must appear in the top-left corner of i (A, resp.). Further, once we choose — 1 (Aa — 1, resp.) of the values r2 < r < <Th to appear in the first column of 1u (first row of A, resp.), then the remaining r’s must appear in 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’ (h—i Cpu) = 111 — 1 55 CHAPTER 3. HOOK FOUNDATIONS and the number of SSYTx of shape S(A, o<; k) = ic/p with lattice reading word and content ii = c(T) is given by (h—i Since \a < < we have h + 1 > Aa + jig. Therefore we have h — )‘a > p — 1 and we obtain h)aj>iij, (3.7) for each i. Therefore — (h—i)! C,1? — (h — — 1)! — (hi). x — (ha)!(\ai)! 1Licz1 = u > c1?, where we have used Equation 3.7 in the final step. Since we have found a content ii with c1? > c1?, we can conclude that SS(A,;k) — 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 Ss(\t,D;1) — where D is a sum of fat staircases and ) is a single row. Theorem 3.1.6 Let D = p/si be such that SD = > C,S1?, uzfat staircase and ) be a single row. Then we have SS(t,D;1) — SS(,D;1) s Cv(SS(At,a(v);1) — SS((v);i)) s 0. 56 CHAPTER 3. HOOK FOUNDATIONS Proof Applying Theorem 2.3.1 shows that SS(A,D;) s CvSS(A,c(v)<;1), so we have S8(A,D;1) s — CySS(A,(v);l). (3.8) We now intend to show that SS(t,D;1) = CvSSt,c(v)1;1). (3.9) Then, adding Equation 3.8 and Equation 3.9 will give that SS(,D;1) — SS(A,D;1) s Cy(SS(At,(v);l) — 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’) = c(T), and 2. there are at most c, distinct SSYT of shape s(At, D; 1) that could map to T’. 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) — SS(A,D;1) s Cj,(S8(t,a(j,)<;1) — SS(,a(v)<;1)). Now, using Theorem 3.1.4 on each pair Ss(At,(v)<;1), SS(A,(v);1) gives S8(At,a(v);1) — SS(\,(v)1;1) 0, 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 = S(4,32i,i,i) +S(3,2i,i,i) + S(3,3,2,2,2,1,1) = S(3211) + (313) + We now wish to apply Theorem 3.1.6 to this diagram D using ). = (3). We are interested in appending A to D and each of L\(3,21),L(3,i,) and (2,3,2) and also in appending At to D and each of L(3,i,) and L(2,3). Therefore, we are interested in the following diagrams. 58 SS(t,D;1) S3(,D;1) s v(Ss(t,a(zi);1) — SS(A,(z,);1)) s 0. (Ss(t,D;1) — SS(A,D;1)) — (C,(ss(At,(v)<;1) — = S(5,432i,i,i) +S(5,42.i,i) +S(5,42i,1). 59 CHAPTER 3. HOOK FOUNDATIONS Theorem 3.1.6 states that In fact if we compute both Cj, (Ss t,(v)<;1) — SS(,a(v) ;i)) 1 (Ss(At,(3,2,1,1);1) — S8(A,(3,2,1,1);1)) + 1 (sspt,(3,i)i;i) — SS,(3,i,3);1)) + 1 (ss(At,(2,3,2ya;1) — SS,(2,3,2y;1)) and SS(At,D;1) then the difference is given by CHAPTER 3. HOOK FOUNDATIONS Further, one can also check that Cy(5S(,(ziy;l) — SS(A,c(,,))) s 0. 3.2 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 entries. When we write the vector z = (z1,z2,z3,. . . , z,) we shall mean the infinite vector z = (z1,z2,z3,. . . ‘Zn, 0, 0,0, .. .). We shall only consider 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} where c — 1, c + j + 1 A. We say that two maximal intervals A1,A2 of A are disjoint if A1 fl A2 = 0. It is clear that any finite set A of non-negative integers can be decomposed into a finite collection of maximal disjoint inter vals {A1,A2,.. . , Am}, and that this collection is unique. Finally, when we 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 a fat staircase, 0 < k < 1, and h 1. Then zi(B, C) = ö + eB + ec + (01,1h-IBI-IC) 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, • if B = U=1B3 where the B3 are the maximal disjoint intervals of B, then min(B) E R,k for each j, and • if C = U1C3 where the C3 are the maximal disjoint intervals of C, 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=1B3. Since each J3 is a set of consecutively increasing numbers and each min(B3)e 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 = U1C3. Since C ç B, this is the second time we are reading each of these values. The fact that each value is in R,k allowed us to read all these values the first time. Now, since each C3 is a set of consecutively increasing numbers and we have previously read a min(C3)— 1 e B — C, the lattice condition is 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) = öa + eB + ec + (O’, lh-IBI-IC1) is a partition. • We can now state a formula for the differences discussed in Theorem 3.1.3. Theorem 3.2.2 Let A and 1u be hooks with A = p = h < n + k andf1Aa<1ta and letO<k<1. Then 8S,o;k) — S5(jy1;k) = aB,cs(B,C) where the coefficients aB,c are given by — ((B — C) flRa,kl 1 ((B — C) flR,kl 1 aB,c— AaC11 ) — aCH1 the partitions v(B, C) that arise are given by zi(B, C) = 6 + eB + ec + (O’,1HBHI0I), and the sum is over all sets B, C such that 61 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, • if B = U=1B where the B3 are the maximal disjoint intervals of B, then minB) e R for each j, and • if C U1C3 where the C3 are the maximal disjoint intervals of C, 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 whenever a SSYT of shape S(1i,; k) with lattice reading word and content 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) = ic’/p’ with lattice reading word and content ii is given by — ( (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 ‘i with lattice reading word. 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 p C + 1 and Ita lB fl Ra,kI, 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 < A1, p which, since R = C + 1, gives jC +1 < A1 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 = U1C, 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 j. 64 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 values kl + 2, c + 3, . . ., a + h — 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 + (01,1h-IBI-ICI) 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, which is possible since lB fl R,kj p and C U {min(B)} C to fill the 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 placed each entry of C twice and each entry of B — C once. This adds 2ec + eB_c = eB + ec to the content. Together with the unique filling of L, 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. Consider the first case, x e Since the lattice condition failed at 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 = U1C3. So x e C, for some j. Let 65 CHAPTER 3. HOOK FOUNDATIONS t = min(C3). Then t — 1 e B — C appears exactly once in and each of the values t, t + 1, . . . , x C appear twice in Since the first row and 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 implies that there is no x in the first row. Since the tableau is semistandard this implies that there is only one x in the tableau. If x < + 1, then x E B = U=1B. Thus x B for some i. Let t = min(B) e Then each of the values value t, t+ 1, . . . , x —1 also appears in the tableau and, since 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 x > + 1, then B + C < h — 1. Therefore cj + 1 e B. Further, the values in t greater than °d + 1 are precisely the h — Bj — IC values + 2, c + 3,..., kI + h — B — C + 1, and these all appear at the bottom 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 1LaH1 — ( (B—C)nR,k{—1 - JLaCH1 and — ( I(AUA’)11?cx,k Cp(B,c) — — 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 Sv(B,C) that arise in Case 1. 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, • if B = U1B3 where the B3 are the maximal disjoint intervals of B, then min(B3)e R for each j, and • if C = IJL1 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 t to fit all of C and min(B), or • 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 uj < C + 1. Since min(B) U C C R,k fl B, the second case implies that 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 I BflRcx,k </La, then by following the same method as in Case 1 we can show 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 — I I(AUA’)flRa,klCp(B,c) — — l1 — (‘ l(BC)flRa,k11 - palCH1 and — ( l(AUA’)flRa,kl Cp(B,c) — — RI — ( I(B—C)flRk}—1 - AaICH1 but now, since p > lB fl R,kl where C U {min(B)} c B fl R,k, we have iialCH1 > l(BC)flRa,k11, and so — ( I(B—C)flR,kI—1 —oCpI(B,c) — Pa — CI — 1 — This shows that aB,c are the correct coefficients for the terms Sv(B,C) that arise in Case 2. Thus the formula given for SS(,a;k) —5Scu,a;k) is correct. • 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 = ll = h < n + k and Aa,pi and let 0< k <1. If Aa then SS(A,a4;k) — SS(,c;k) = aB,cs(B,c) 68 CHAPTER 3. HOOK FOUNDATIONS where the coefficients aB,c are given by — ( I(B—C)flR,kH1 (I(BC)flRa,k1 aB,c 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, • if B = U’=1B3 where the B, are the maximal disjoint intervals of B, then min(B) E for each j, and • if C = U1 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, c<; k) and content i’ with lattice reading word. 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 fl R,kj. 69 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), = (3,1) and k = 0. We are interested in the following two diagrams. SQ, a; 0) For this a, k, we have R,k = {2, 3, 4, 5}. Thus Theorem 3.2.3 gives SS(A,1;O) — 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=1B3 where the B3 are the maximal disjoint intervals of B, then min(B3) e R for each j, and • if C = U1C3 where the C3 are the maximal disjoint intervals of C, then min(C3)— 1 E B — C for each j. 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 S(t, a<; 0) 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} and {2, 3, 5}. If C = {4}, then {3, 4} B, so the possibilities for B are the sets {2, 3, 4} and {3, 4, 5}. In each of these four cases we can compute — ( (B—C)nR,kJ—1 (j(B—C)nR,kj—l aB,c — AaICH1 )_ taCH1 ( 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 — 2—1—1) — 3—1—1 - (1 (1 - =1-1 =0. When B = {4, 5} we have — ( (B—C)flR,k—1 ( (B—C)nR,k—1 aB,c — 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 — ((B—C)nR,k—1 N (I(B—C)flR,kH-1 aB,c — aCH1 iaICH1 — ( 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 — ( (B—C)nR0,k 1 N (I(B—C)flR,k—1 aB,c — XaICH1 ialCH1 — ( 3—1 N ( 3—1 — 2—0—1)3_0_1 - (2N (2 - =2-1 =1, and when B is {2,3,4,5} we have — ( (B—C)nR,k—1 N I (B—C)flR,kI—1 aB,c — aICH1 i-’aCH1 — I 4—’ N 1 4—’ — 2—0—1)3—0—1 - (3N (3 - =3-3 =0. 72 CHAPTER 3. HOOK FOUNDATIONS Thus we have SS(,1;O) — SS(,c;O) = aB,cs(B,c) = 1S({4,5},{5}) + 1S({2,5},O) + 1S({3,5},O) + lSv({4,5},O) +1S({23},O) + lSti({2,4,5},Ø) + 1S({3,4,5}.O) = S(4,3,22,1) +S(4,2l,1,1,l) +S(43,3,l,,l,l) + S(4,3,2,2,l,l,l) +S(4,i,i,i) +S(4,2,2,l,l) +S(4,33,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 + e + (Os, 14_2_1) bE{4,5} 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). 3.3 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 1u 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,c2,. . . , 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) 8S( ,o;k) S5(tJ,c;k) k=0,1 i i v;k) SS(H iii i,c;k) 11111 ,c;k) 74 CHAPTER 3. HOOK FOUNDATIONS S3(,&;/c) SS(JQi;k) 8S(fl,&;k) k=2 Ss( i i hc;k) I I I SS(j I I I I I k) 8S(,c;k) SS(J&a;k) SS(IJ,a1;k) I I k=3 SS(H III i,a;k) Ss(1 I I I I I 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) SS(1 I I I ,c;k) SS(,cy1;k) SS(Jo1;k) SS(LJ,c1;k) I I a;k) k=5 SS(H iii i,;k) SS(1 liii ,c;k) 76 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 [ii, 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 77 CHAPTER 3. HOOK FOUNDATIONS only if S, c; k) S(1,<; k), and when k 0 we have Aa > if and 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. Theorem 3.3.1 Let A and t be distinct hooks with Aj = = h n+k and </2a ri and let 0 < k < h. Then we have S(, c; k) S(A, c; k). 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. Since Aa < /La and Al = [II, we have A > Let r1 = = = rk = 1 and let rl+k < r2+k < .•• < Tfl be the values of greater than 1. We can create a SSYT of shape A by filling the boxes of A as follows. r1 rk rl+k r2+k rAa_1 + 1 Ic + A1 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 < A1, we have l(S(,u, c; k)) = c + j < c + A. Therefore no SSYT of shape S(u, c; k) with lattice reading word can contain the entry c + A1. Thus no SSYT of shape S(ji, c; k) with lattice reading word can 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 = = h n+k and Aa <Ia ri and let 0 < k < h. Then we have S(A, a<; k) 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 r1 = = rk = 1 and let r+k < r2+k < ... < rfl+k be the 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 r1 rk rl+k r2+k Ta+l rh Since r = r2 = = 1 and rl+k < < < rh are distinct values of R1,k, it is easy to check that the resulting tableau of shape p & has 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 r1,r2,. . . , rh. Since r1 = = = rk 1 and T1+k < r2+k < < rh, the values r1,r2,. . . , 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 r1+k, r2+k, . , rh to appear in the first row of p (first row of A, resp.), then 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 (h—k p’ii = ‘\ Pa — k and the number of SSYTx of shape S(A, ; k) = ic/p with lattice reading word and content ii = c(T) is given by (h—k CPv=k\Aa_k Since Aa <Pa <ri, we have Aa+pa < h+1 < h+k. Therefore we have h — Aa > Pa — k and we obtain hAai>pakj, (3.10) for each i. Therefore jçl (h—k)! = (h — pa)!(pa — k)! 79 CHAPTER 3. HOOK FOUNDATIONS IL LII — li). TT — — (h_Aa)!(Aa_k)!X [Lak = fjj/ ‘1 [Lak2 > cv, where we have used Equation 3.10 in the final step. Therefore SS(A,i;k) — SSu,1;k) s 0. I We now depart from looking at the hooks ;\qL satisfying a <[La 1. Instead, we turn to the hooks A, [L satisfying r i 5 Aa <[La. The following theorems describe the relations among the diagrams we displayed on the right in our examples. Theorem 3.3.3 Let A and t be hooks with Al = [LI = Ii < n + k and ri Aa <[La, and letO k h. 1fAa [Li+k—1 thenS(A,ci;k) >- S(i,c;k). 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 a1 = a2 = = 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 < < a1, where a = a1 = 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 a1, ..., 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 {a+i, aq+2,. . . , a} U {a, a,. . . , a1} in 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 that + 2 appears in . Since each a E R,k, we have a2 < °i + 1 for each 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, a1 as the last 4u1 — j + 1 entries of the first column of A. Since Aa < ILa gives Ii < A1, we have ,u — j + 1 <A1 — j + 1. Since j 2 this gives, p—j+1Aj, (3.11) so these entries do fit in this column. Note that if 1(v) < aj + 1, then this sequence of values a, a+1,.. . , a1 is empty aild we do not have to worry 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 ..,a_1}. We note that R = {aq+i, aq+2,. . . , a} fl {a, a, . . . , a1} since Lemma 2.2.2 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 1tt. Since the values of R all appear in the first row of , Lemma 2.2.2 gives that R c 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 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. Consider A = {aq+i, aq+2,. . . , a,J — R and A’ = {a, as,. . . ,a1} — R. 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 that can appear in exactly one of the first row of A or the first column of A. We wish to show that R <Aaq (3.12) holds. If q = 0, then R < j < p + 1 < A1 Aa = — q. Now, when q 1 the top-left entry of 1tt is 1 which is not in R, hence we have R </1 <Aak < Aaq, where we have used the fact that Aa /M+k1. Now, because Equation 3.12 holds, we can extend the values of R to an increasing sequence bq+i < bq < < b by choosing Aa — Rj — 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 = — (Aa — q) = Ita +j 2 — Aa distinct values, each no greater than cj + 1. That is, they are an increasing sequence c1 < c2 < < c,,,, where c < c + 1 and c1 > 1. We have A1 = Ia+IMa = 1+(pa+j_2Aa)+(iii_j+1) = so, letting b1 = = = bq = 1, we may fill A as shown below. b1 b2 ... bAa c1 c2 c a+1 82 CHAPTER 3. HOOK FOUNDATIONS Since the sequence of cj is strictly increasing and since c1 > 1 and c c+1 < wehave That is, the first column of A is increasing. We also have bib2”bql 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 1u, 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 1u. 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 that none of the values t + 1, t + 2, ..., x — 2, x — 1 are from R,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 R,k. That is, each value t + 1, t + 2,. . . , x — 1 appears 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 t, t + 1, ..., x — 2, z — 1 is read before the x is read in A and the lattice 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 1u (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,... greater than + 1. Since Lemma 2.2.2 shows 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 [La — q — RI P’a — q IRI, resp.) values from the set (AU A’) fl to place 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 ICp_ and the number of SSYTx of shape S, ; k) = ic/p with lattice reading word and content ii is given by — I 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, (3.15) for each i. Therefore — I(AUA’)nR,kI! CPV — (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 — (Aa — RI) — — q 85 CHAPTER 3. HOOK FOUNDATIONS aa1 TT _____________________________ _CP!VX (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 = h < n + k and < A < iLa, and let 0 < k < h. If S(A, c; k) S(, c<; k), then Aa iii + k—i. Proof Since ri Aa <Ita, where A = = h, we have ri < 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 r1 = 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 1tt as follows. r1 r2 rk rk+1 ra+l ra+2 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 r1, r2, . . . , rh. Since r1 = = = Tk = 1, the values r1, r2, ..., 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 = I4 IM — 1 and the number of SSYTx of shape S, c; k) = ic/p with lattice reading word and content v = c(T) is given by jç (hk CPV=\,)a_k Since <A <r1 a <ita, where = h, we have [Li+Aa <Ai+\a h+1. This gives h — ) > ,u — 1 and we obtain hAaj>/j1j, (3.16) for each i. Therefore (h—k)! cp,v (h—k—1+1)!(—1)! (hk). j ______ (hAa)!\ak)! p—1—i = c1)x > cv, where we have used Equation 3.16 in the final step. Therefore SS,<;k) S5(<;k) 0, which is a contradiction. Therefore we have /M + k — 1. I Finally, we turn to the hooks A, 4u satisfying Aa, ii ri. 87 CHAPTER 3. HOOK FOUNDATIONS Theorem 3.3.5 Let A and u be hooks with = h < n + k and Ifi < k < h and Aa Ifk=O andAa > then S(;\,c;k)>-8S(1,;k). Proof The case k = 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 SA, c; k) S(1i,; k). We claim that proof of Theorem 3.3.3, with a few 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 Aa — q, and [La — — q Aa — Rj — q. 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 [La — — q Aa — jR — q, 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.11 holds for the assumptions of this theorem, we note that [Li A1. In order to show Equation 3.12 holds for the assumptions of this theorem, we note that In order to show Eqjation 3.13 holds for the assumptions of this theorem, we note that [La > Aa. Therefore we can create a SSYT of shape 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 S([L, ; k) with lattice reading word and content To prove this, we first 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) s 0. • 88 CHAPTER 3. HOOK FOUNDATIONS Theorem 3.3.6 Let A and be distinct hooks with ) = = h < n+k and ri. If 1 <k < h andS(A,c;k) If k = 0 and S, cr; k) >— $(i, c; k), then Aa [tj. Proof The case k = 0 was proved in Theorem 3.1.5. We turn to the case 1 k h. Towards a contradiction, suppose Aa < k + IM — 1. As before, we let r1 = r2 = = = 1 and r1 < < < 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. r1 r2 r rk+1 r 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 r1,r2,. . . , rh. Since r1 = r2 = = rk = 1, the values r1, r2, ... , rk must appear in the first k positions of the first row of i (A, resp.). Further, once we choose [Lj — 1 (Aa — k, resp.) of the values rk+1 < rk+2 < < 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) = ii/p with lattice reading word and content v = c(’T) is given by (h—k CPV=k\Aa_k 89 CHAPTER 3. HOOK FOUNDATIONS Since Aa,i <r1, we have h+1 Aa+i. If we have h+1 = then this implies that h is odd and A = = ri = Using the fact that ) = = h implies A1 = = ri = as well. Therefore A = However, we are only interested in distinct hooks A and i. Thus, among distinct pairs A and 1u, we cannot have h + 1 = Aa + /Jj. Thus for A , with Aa, <[, we have h + 1 > Aa + This gives h — Aa > — 1 and we obtain hAaj>/11, (3.17) for each i. Therefore — (h—k)! cp,v — (h—k—1+1)!(—1)! (h — k)! h — Aa — i (h_Aa)!(Aa_k)!X i)a+k2 i. It — Aa — i =c Xpv i—O > cv, where we have used Equation 3.17 in the final step. Therefore ss(A,;k) SS(,i,c;k) 0, which is a contradiction. Therefore we have Aa I-’i + k 1. 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) — Ssp,k,n) s 0, 2. SS(At,k,n) n+1 SS(A,k,n), and 3. SS(At,k,n) n+2 Ss,k,n) 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 + (On, 1”—I’). In particular, SS(t,k,n) — SS)..,k,n) ‘S multiplicity-free. Example Let n = 4, ) = (3), and k = 0. We are interested in the following two diagrams. $t,o,4) S,0,4) Theorem 4.1.1 gives SSt,O,4) — Ss(,o,4) = Sv(A) A C {2,3,4} Sv(O) + Sv({2}) + Sv({3}) + Sv({4}) = S(4,3,2,i,1,1,i) + S(4,4,2,i,1,1) + 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 = S4 + e + (Ok, 13_i) 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) — 5S,k,n) we show that any 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 < a2 < <a1 where aA1 n + 1 by the lattice condition. 92 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS Since a1 < a2 < <aA1,we can create a SSYT of shape )t by transpos 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 a1 < a < < a1 and a1 <ri + 1. 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 n + 1 variables. This and 1 completes the proof that SSt,k,n) n+1 SS,k,n). 3. If A At then A1 2. Therefore At consists of a column of length A1, where 2 < A1 < n + k. We shall fill the last two spaces of the column with n + 1 and n + 2, and then fill the remaining A1 — 2 spaces with 2 — k, 3 — k,. . . , A1 — 1 — k. That is, we fill the column with the entries 2 — k,3 — k,...,A1 —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. Let ii be any partition with 1(v) n + 2. No SSYT of shape S(A, k, n) 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 case, A ç {2 — k, 3 — k, . . . , n}. The order that these values appear in At is uniquely determined since the column must strictly increase. Since there are only A1 entries in At and we know that both n + 1, n + 2 e At, we have jA A1 — 2. Furthermore, any A C {2 — k, 3 — k, . . . , n} with IA <A1 — 2 gives rise to a unique SSYT of shape S(At, k, n) with lattice reading word that contains A in its foundation. Namely, we fill the first IA boxes of At with the values of A andtheremainingA1—AboxesofAwithn+1,n+ 2,...,n+ A1— A. The content of this filling is v(A) Sfl+eA+(OhI,1—tAI). Since 1(v(A)) > ri+2, 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) — SS\,k,n) will still be multiplicity-free if we use any fat staircase since this 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 with two rows such that 1 <A1 <k + n. Then 1. SS(A,k,n) — Ss,k,n) s 0, 2. 5S(,\t,k,n) n+1 SS(A,k,n), and 3. SS(t,k,) n+25S(A,k,n) if A At. Proof 1. Consider any SSYT 7j of shape S(A, k, n) with lattice reading word, where 0 k 1. Then the entries of the foundation A have the following relations. a1<a2<•<aA2<•<aA A A •.. A b1<b2 <•••<b2 The fact that a1 <a2 <aA1 follows from Lemma 2.1.1, and the rest of the relations follow from the definition of a SSYT. We also have the condition a1 > 1 when k = 0. The relations a1 < a < < a1 show that there is no repeated value 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. a1 < b A iA A A aA2_1 < b2_1 A A a2 < b2 A A a1 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. If a1 <n + 1 and b2 <n + 2 then T’ = T. 2. If aA1 = n+ land b2 = n+2, then (a) If X > A2 then T’ = T with aA1 and b2 swapped. (b) If Ai )2 then T’ = T with a2 and b2_1 swapped. 1. 2.(a) 2.(b) a1 < b1 a1 b1 a1 b1 A iA A A A A A iA A iA A A a2_1 < b2_1 a2_1 < b2_ aA2_1 < n + 1 A A A A A A < b2 aA2 < n + 1 b2_1 < ri + 2 A A A A a1 n+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 aj — 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 < j—i—1 A A A A j—i—1 < j—i+1 i—i = i—i A A A A i—i < j—i+2 —f j—i+1 = j—i+1 A A A A A A A A 3—3 < j—1 j—2 = j—2 A A A A j—2 < j j—1 = j—1 A A A j—1 < j j = j A A A A z < w z < 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. The row of interest r1 is above the sub-block in the first column. 2. The row of interest r2 is within the sub-block in both columns. 3. The row of interest r3 is below the sub-block in the second column. i—i * j——1 * y1 * * * j—i—1 * Block j—i * Rotation * Y2 * * * * x2 * * * k boxes r3 * 7J3 J3 k1 boxes i—i * j * Thus, in the left-hand diagram, the value x3 may in fact be the bottom-most entry of the sub-block in the first column. That is, x3 = j — 1 is a case considered by the various possible positions of r3. 100 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS For the rows r1, r2, and r3 shown, we wish to show x <y for i = 1, 2, 3. This will show that the rows weakly increase after the block rotation. Since the columns strictly increase we have x1<j—i—1<j—iyi, and X3 < — 1 < <p3. Further, with k1 and k2 as shown, we have x2 = j — k2 and Y2 = j — k2 + k1, hence x2 <x2+ki =j—k2+k1 Y2• Therefore the rows of the resulting tableau weakly increase. We can now check that no two block rotations move the same elements. If we have performed a block rotation to fix a [ ] problem then there cannot 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 word, we obtain a SSYT T2 of shape At We also claim that T2 has a lattice reading word. In each case there is at most one n + 2 in T2. If an n + 2 does appear, then it appeared at the 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 A1 > A2 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 A1 = A2 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. Nevertheless, suppose that the reading word of T2 is not lattice. Let j + 1 be the entry that, when read, violated the lattice condition. We know that the content after reading /.S is (n, n — 1,.. . , 3, 2, 1), so we must have read at least two more j + l’s than j’s since we finished reading Z1. Since there 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 x1,x2, . . . , x) and Yi, Y2,•• . , y,2 respectively. Thus x = j + 1 and Vk = j + 1 for some i k. We know j ‘ {x, xH.1,. . . , x1} U {yj, Yk+1,• . . , y2} since the columns strictly increase. But we also knowj {xi,x2, . . . ,x}u{y . . . ,y} since by assumption we had not read any j’s when reaching the second j + 1. Thus which is to say j ‘ {xl, x2, . . . , x1y1, Y2, . . . , y,2}. This is a contradic tion since {xi, x2,. . . , x, yi, . , y2} = {a1,a27..., ax1,b1, b2, . . ., b2} 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 T2 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. * < x < i—i < ... < j—1 j < * A A 1 A y < j—i—1 < i—i < ... < j—1 < j < * * < x < j—i—1 < < j—2 < j—1 < * A A A •• A A A y < i—i < j—i+1 < ... < j = j < * 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 a1 < b A A A A aA21 < b2_1 A A aA2 < b A A aA1 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 b1<b2 <••<b 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 a1 = 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. H +i... •..j+i1 j+iz y i-i j j+1... •.. j+i—1 j+i w or x j j+1 ... ... j+i-1 j+i z y j—1 j j+1... ... j+i-1 j+i 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 x j j+1 ... •.. j+i—1 j+i z y i-i j j+1•• •.. j+i-l j+i w -I, x j—1 j j+i-2 j+i-1 z y 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 x < j — 1. Hence the only pair of equal values in a row that is created by 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 column of T with a pair of equal values, say [ ]. Since the reading word for 7 is lattice, there is a m — 1 in T. This rn — 1 must occur in the column immediately to the left of the [ ]. If this rn — 1 appears in the first row of 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 < ... < rn—i < rn j—i < j < ... < 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 c1 is left of the sub-block in the first row. 2. The column of interest c2 is within the sub-block in both rows. 3. The column of interest c3 is right of the sub-block in the second row. 106 CHAPTER 4. DIFFERENCES OF TRANSPOSED FOUNDATIONS C1 C2 C3 X1* j X * * j—i...*yi... ‘.. **y i+1 . j ...*... ... ** •••i+I *:y3:” X3 j+i—i I i k1 boxes boxes For the columns c1, c2, and c3 we wish to show that xj < yj for i 1, 2, 3. Since the rows were strictly increasing to begin with we have x1 <j <yr, and X3 < + <J3. Further, for k1 and k2 shown, we have x2 j + k — k1 — 1 and Y2 = j + k2 hence x2<x+k1=j+k—1<y2. 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 bottom- left 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. Block Rotation * x2 * 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 word, we obtain a SSYT T1 of shape A We check that T1 is a SSYT 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 one more than the number of j’s. Thus the SSYT T1 does have a lattice reading word. Therefore, applying Lemma 2.2.3, we obtain a SSYT 7j of 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 A1 3. We split into three cases depending on the size of A2. Namely, 1. A2 = 1, 2. A2 = 2, and 3. A2 >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. 3. 2 n+1 2 n+1 2 3 3 3 n+2 3 4 A1—2 A1—2 A2—2 A2—1 n A2—1 Ti n+1 ri+1 A2 n+1 n+2 n+2 A2+1 n+2 A —2 A1 —1 n+1 n+2 If A = 3 in case 1 or 2, then the first column consists of the three entries Ti,’fl + 1,n + 2, and if A1 = 3 in case 3, then the first column consists of 2, Ti + 1, Ti + 2. Similarly, if A2 = 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+28S(),k,n). I 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 4 5 6 9 10 12 6 7 7 8 11 11 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. 26 25 25 47 46 46 57 67 67 68 78 78 9 11 9 11 9 10 10 11 10 11 11 11 12 12 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 4 6 7 9 11 12 5 6 7 8 10 11 2 4 6 7 9 10 12 5 6 7 8 11 11 2 4 5 6 9 10 12 6 7 7 8 11 11 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 (, respectively) has width n and length c = 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)1’)) is the smallest rectangle that contains D. 5.1 Preliminaries Given a partition p contained in the a x b rectangle (be) we define the corn plementary partition pC in 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. __H (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 = we define the truncated com plement of f in the rectangle (be) as c(f) = (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 v1 > w(p/ic), which implies that there is a SSYT of shape p/ic and content v with lattice reading word using v1 l’s. However, there is no way to fit v1 > 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) — pcuc. V VC(ba) By Theorem 5.1.1, this is just s,311, so we are done. One must be careful in working with the expression c(skspc). We must truncate any term s we obtain from the product with ji (ba). Thus we 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 s1,/,ç for more types of diagrams p/ic. In 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 (w1), say. We begin by comparing c(s) and Consider a content v that contributes to c(s). Then ii (w1) and 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) = [svc](Ss(A,o<;k)) for all V ç (wt). This gives c(sa) = C(Ss(,c;k)). We also have = and so c(sAe) = c(ss). Thus we have c(sAsz) = C(Ss(,ca;k)), as desired. I Given a composition = (c,c2,. . . , a) and a width w = n + k, where o < k < 1, we let = f (€n, cn_i,. . , 2, c) if k = 1 l, (€ni, n—2,. . . , 2, cr1) if 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. ] 2 rT1 J HH R’ HH :1 Thus we have l(6) l(ö) and w(6) w(6). In particular, we have k= &j+(1-k)c. 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 (wIl1), = (p+1,pIl+2, . . ii+) and A = pC be the complement of p in (wI’+1). Then p/6 S(1a, c; k) and 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 (w1). The first set of diagrams illustrates the case k = 1 and the second set illustrates the case k = 0. li 1 1) It is clear from the definition Therefore we obtain of that we have S(,u,;k) = p/6r. = 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. • S([L, c; 1) 1 p/:5yr S(t, c; 0) 8S(,a<;k) = 115 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 (w1) and let AC and 1U’ denote their complements in this rectangle. We call these hook complements. For a fat staircase Z, we now inspect when the difference SS(Ac,&;k) — SS(pC,;k) is Schur-positive. Thus we are interested in the differ 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 A1,A2,. . . , p, 112,... placed in weakly decreasing order. 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 , = ic1,K2,...) is obtained by merely appending ic to the rectangle (w’). 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) >- S(t, 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*1) so we 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)) — c(ss(,,ar;k)) 116 CHAPTER 5. COMPLEMENTS IN A RECTANGLE c(ssp,oiy1;k) — where these complements are performed in the rectangle (wkHj. Now, if c; k) >- r; k), then the above equation shows that S(), c; k) >- S(ic, ; k) as well. For the converse direction, suppose that S(A, cr; k) S(, c; k). Thus, by assumption, the difference SS ;k)SS(p,;k) is not Schur-positive. 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 theorem the partition v satisfies ii (wkH1). In both Theorem 3.1.2 and Theorem 3.1.5 we used ii = 5ar + where r1 < r2 < are the values of Rar,k. We have W(5,r) < = n. Further, since the r are distinct, adding the terms e to e5 can only increase the width by 1, and this only happens when r1 = 1 which implies that k = 1. Thus, Ill either case, w(v) < ri+k = w. Also, since l(5) < = alldeachr jc+1,wehavel(zi) < j+1 < +l. Thereforeviscontained in the rectangle (wkH1). In Theorem 3.1.1 we used v = 6 + e + (O1I, iAt), where r1 < r2 < 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 cv < o and ) ç (w1). Therefore v is contained in the rectangle (wHt). Thus, in each case ii is contained in the rectangle (wH1). Therefore 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 Schur- positive. That is, c; k) S(p, c; k). This completes the converse 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 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. As before, we let AC and 1u’ denote the complements in (w1). i 118 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Theorem 5.2.2 Let A and it be hooks with Aj = = h n + k = w and f1Aa<aant0k1. Then — SS(,C,&;k) = a,cs(B,c) where the coefficients a,0 are given by — ( I(B — C) fl Rr,kI — 1 ((B — C) fl RGr,k — 1aB,c AaCH1 ‘aCH1 the partitions r1(B, C) that arise are given by r(B, C) = (n + k11 +I+0 1—k) k n + k —1—B—ICI+cn+kl n+k_2+k_2,...,2a2,11) — — bEB cEO and the sum is over all sets B, C such that • Bc {2—k,3—k,...jc1+1}, Cc BflR’,k—min(B), • C + 1 <A1, • Aa B fl Ro’r,k, • B+CHh, and +1eBifBj+jC<h—1, • if B = U=1B where the ]3 are the maximal disjoint intervals of B, then minB) e for each j, and • if C = U1C where the C are the maximal disjoint intervals of C, then min(C3)— 1 B — C for each j. We note that the term 0n+k in r1(B, C) is not defined for k = 1, but this causes no problem in computing the above expression since the oniy time the term 0n+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 (wIHl) so we may apply Theorem 5.1.4 to both p(\c)/r $(,\c c; k) and p(C)/r = S(,uc, a; k). This gives SS(Ac,&1;k) — = c(ss(,cr;k)) c(Ss(p,cr;k)) = c(Ss(,cr;k) where these complements are performed in the rectangle (wk1). 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) — SS(,tC,1;k) = aB,CsL?(B,c)c, (5.2) where ii(B, C) = c5r + bEB eb + cC e + (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 A1, • Aa B fl R&’,k, • • if B = U=1B3 where the 133 are the maximal disjoint intervals of B, then min(B3)e Rr,k for each j, and • if C = U1C3 where the C3 are the maximal disjoint intervals of C, then min(C3)— 1 e B — C for each j. 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 (w11) = (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 bottom- right corner of the diagram represents (ii(B, C)c)0. (1 — k)c + 1 — 1 Consider the case when k = 1. Then these two rectangles are of size (i-i + iH1) and (n + ii’), respectively. Rotating the blank space in the (n + 1’) rectangle gives the partition (n + IHBIH0). Rotating the blank space in the (n + 11j rectangle gives the partition Thus we find — — bB cC Hence ii(B, C)’ = (n +1—1—+IBI+ICI I—B—IC) U (6 — eII+2_b — bB cEC zi(B, C)C = (n +1—1+IAI+BI+Ct PHBIHC’In — jQn_1 ‘)2 1’) — ei+j — ei+i_. bB cEC &r + >ZbEB eb + ZcEC e + (OI+’,1PIIBHIC’I) (v(B, C)c)o 121 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 — iPIHBHdI) Rotating the blank space in the (nk1) rectangle gives the partition — e2_— bEB cEC Thus we find v(B,C)c = (nn+l—1—P+BI+ICI,n iPHIBIHdI) U (ó(ai,...,Q_i) — e2_b — e2_C). bEB cEC Hence v(B C)C = (i—1+I+B+ICI+cn n — n — 2_2, , 1’) — bB cEC For both k = 1 and k = 0 we can rewrite these expressions as v(B, C)C = (ii + k1_1+ BH-ICI+(1_k)a+, Ti + k — ri + k —2a+k_2,•• , 2Q, 1’) — — bEB cEC (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 Aa, /-tj which was explored in Theo rem 3.2.3. Theorem 5.2.3 Let ). and p be hooks with )j = = h < n + k = w and Aa,i <[f, and letO < k <1. 1f\a [Lj, then 5S°,c;k) —5S(,c;k) = a,cs(B.c) 122 CHAPTER 5. COMPLEMENTS IN A RECTANGLE where the coefficients a,c are given by (I(BC)flR,kI1 ( (BC)flRar,k1aB,c— AaICH1 ) [taIC1 the partitions r1(B, C) that arise are given by i7(B, C) = (n + kl_l n + k — n+k_2Qk_2,...,2a2,11) — — bEB cC and the sum is over all sets B, C such that • Bc{2—k,3—k,...&+1},CcBnR,k—min(B), • C + 1 Aa B fl R&,k, • BI+C<h, and r+1EBif Bj+jC<h—1, • if B = U=1 ]3 where the B1 are the maximal disjoint intervals of B, then min(Bj) e R&,k for each j, and • if C = U1C3 where the C3 are the maximal disjoint intervals of C, 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 = (au, . . . , c) be a composition. Then for 1. < m < 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 = (an_i, an_2, . . . , a) since the width of the rectangle is n. a1 [ a [ a_1 [ We can compute the product S(m)S using Thus we have S(m)S5 = Theorem 1.6.1 (Pieri’s rule). 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 we obtain Sö/(m) = C(S(m)Sör) = S/(m) = Ac(nkI) (5.3) 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. an [ a [ 124 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Suppose there is a j, where 1 j n — 1, such that cIj = 1. We intend 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. Since ö is a fat staircase aild we are constrained by ) (n), there are only n possible positions to place the m boxes. Namely, there is one position in the r-th row for each r e R,1. These n possible positions are shown in the diagram below. 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 first row of length This gives a partition ) (n11) such that )/6 has ‘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) = (3, 3, 2, 2, 1, 1)/(2). Since L Qj [ j+1 [ 125 CHAPTER 5. COMPLEMENTS IN A RECTANGLE = (2, 2, 2) satisfies the hypotheses of Theore m 5.3.1, Sö(222)/(2) is a sum of fat staircases. In particular, we ha ve Sö(22)/( ) S(3,3,,i,i) + S(3,2i) + 8(3,2,2,1,1,1) = Sö(212) + Sö(131) + S o(321). Proof (of Theorem 5.3.2) Again, the 6/(1m) is contained (nt°. Using Corollary 5.1.2 we obtain S/(lm) C(S(im)Sö in the rectangle We can compute the product S(1m)S, using Theorem 1.6.2 (Pieri’s rule). Thus we have A where the sum is over all partitions A such that A/6 is a column strip with m boxes. That is, the sum over all p artitions A such that the skew diagram A/6 has m boxes, no two of wh ich are in the same row. Since we obtain = C(S(im)Sör) S&/(1m) SAC, AC(nkl) (5.4) a [ j+1 [[ j—1 [ 126 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. Suppose there is a j such that €j m c — c+i. Then, necessarily, 1 <j <n — 1. We intend to show that &/(1m) is not a sum of fat staircases. 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. Since we must place m > c7 boxes, where m ciI — c+1, we choose to place a box at the end of each row of length o and place the other m — < c — cj+ — c3 boxes in any of the other possible positions except 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, m c —cj1. We intend to show that S/(1) is a sum of fat staircases. c_1 [ Qj [ L 127 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,8ö(333)/(11) is a sum of fat staircases. In particular, we have Sö(333)/(1,1) = 8(3,3,3,2,2,2,1) + 8(3,3,3,2,2,1,1,1) + 8(3,3,3,2,1,1,1,1,1) + 8(3,3,2,2,2,2,1,1) +8(3,3,2,2,2,1,1,1,1) + 8(3,2,2,2,2,2,1,1,1) = Sö(133) +8ö(323) +5ö(13) + Sö(242) + (432) + 5.4 Miscellaneous Results In Theorem 4.1.1 we saw that when A had only one part the difference Ss(.\t,k,n) — 5S,k,n) was multiplicity-free. The same can now be said of the difference SS(tc,k,fl) — Ss.c,k,n), where the complementation is performed in a rectangle (w1) for w = n + k. Theorem 5.4.1 Let A be a partition with 1(A) = 1 and A1 < 1, for some 1, andO<k<1. Then SS()tC,k,n) — S8\C,k,n) = 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 working with regular staircases, we have c = (in), which gives & (1n—1+k) We let p(Atc) := (wi’) u and p(C) := (wn) u )C. Then we have (wa) C p(Atc) p(Ac) 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(ssp,k,n_1+k)) = C(SS(At ,k,n— 1+k) — ss(k,k,n_1+k)) = C S(A) —1 + k} where the last step follows from Theorem 4.1.1. Therefore S8(Atc,k,n) — SS(\c,k,n) = Sv(A)c, (5.5) AC{2—k,3—k,...,n—1+k} where 11(A) = 6n—IH-k + aeA ea + (On1+k, lAiHA) This shows that the 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 6n—+k + aA Ca n—1H-k +(0n—+k 1)i—IAI (v(Ay)0 1 + 1 — k 129 CHAPTER 5. COMPLEMENTS IN A RECTANGLE Thus we find v(A)c = (w1_k_1, ii—IAI) 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 = (5,5,2) and Atc = (4, 4, 4). We are interested in the following diagrams. S(AtC, 1, 4) S(Ac, 1, 4) Theorem 5.4.1 gives SS(AtC,1,4) — SSpc,i,4)= 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)—e8a. Thus we obtain — SS(c,1,4) = S(4,32i)+S(5,432)+S(5,43i,i) + 8(5,4,4,4,2,2,1) +8(5,4,4,3,3,2,1). 130 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 the rectangle (w1), where w = n + k. Theorem 5.4.2 Let A be a partition such that A, At C (wt) for some 1, and let 0 < k < 1. If 1(A) = 2 and A1 > 1 then SStC,k,fl) — SS(Ac,k,n) s 0. Proof We wish to apply Theorem 5.1.4 to both diagrams. Since we are working with regular staircases, we have c (in), which gives .jyr =(1n—1+k) We let p(Atc) := (wa) U A and p(Ac) := (wa) U Ac. Then we have (wj C P(Atc) p(Ac) C (1) so we may apply Theorem 5.1.4 to both of p(Atc)/5fl1+k= s(Atc, k, n) and p(Ac)/5fl_j+k = S(Ac, k, n). This gives SS()tc,k,n) —5Sc,k,n) = c(ss(t,k,fl_1+k)) — C(5sp,k,n1+k)) C(5S(At ,k,n—1+k) — where these complements are performed in the rectangle (W’). Theorem 4.2.1 shows that5Sp,k,n1+k) —5S(,k,n—1+k) >3 0, so the differ ence is Schur-positive. • Finally, using Theorem 2.3.1, we can obtain the following result. Theorem 5.4.3 Suppose a diagram D = p/si is such that SD > ii=fat staircase Given a partition A and 0 < k 1, let , and 0 be the partitions such that S(A, D; k) = i/0. Then c(SOSKc) 8 > cuSS,(i,);k), where 1çC 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 SD12 = 8D15D2 when using 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 8Si).,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) n+1 S3(A,k,n). Proof To prove ssçt,k,n) n+ SS(A,I,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. 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 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 I I n+k 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 SD1e2 = when working with finitely many variables. We begin by inspecting Theorem 1.6.5, which stated that for skew dia grams D1, D2, we have SD12 = 8D1•D2 +8D10D2• Example Suppose we have the following two skew diagrams. The concatenation and near-concatenation are given by the following. From Theorem 1.6.5 we can conclude that SD12 = 5D1•D2 + SD1G2. We note that the diagram D1 . D contains a column of length 5, whereas each of D1, D2, and D1 0 D only contain columns of length 3 or less. Thus we have SD1.2 = 0 and SD1G2 4 SjSD2 gives a non-trivial factorization of SD1G2 in four variables. D12= D1®D2= 136 CHAPTER 6. REDUCTION TO FINITE VARIABLES In order to state the next few results, we find it convenient to make the following notational convention. For a pair of skew diagrams D1 and D2, we shall let l denote the length of the right-most column of D1, and let 12 denote the length of the left-most column of D2. Corollary 6.2.1 If l + 12 n + 1, then we have SD1G2 = SD12. Proof Using Theorem 1.6.5 gives SD12 = SD1.2 + SD1G2. However, if 11 + 12 > n + 1, then D1 . D2 contains a column of length > n, which shows that SD1.2 = 0. Therefore SD1G2= SD12,as desired. We now generalize to our main result for factoring skew Schur functions in finitely many variables. We consider skew diagrams D1 and D2 as before, but now assume that the overlap i < min{11,l2}, so that D1 ® D2 is a skew diagram. Theorem 6.2.2 If l. +12 n+i, then we have8D1ØD2= SD12. Proof We are only interested in fillings using the values {1, 2, . .. , n}. We let x1,x2, . . . ,x denote the first i entries of the right-most column of D1 and y1, Y2, . . . , y, denote the last i entries of the left-most column of D2. Then any SSYT of shape D1 ®j D2 consists of a SSYT of shape D1 and a SSYT of shape D2 such that x3 < y3 for each j = 1,2,.. . , i. 137 CHAPTER 6. REDUCTION TO FINITE VARIABLES Conversely, suppose we have a SSYT of shape D1 and a SSYT of shape D2. We intend to show that x <Yj for each j = 1, 2,. . . , i. We claim that x < ri—I1 + j for each j = 1,2,. ..,i. If not, then > 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 this column is larger than n. Since this is impossible, we have x3 <n—i1+j for each j = 1, 2,. . . , i, as claimed. We also claim that y3 12 i+j for each j = 1,2,...,i. If not, then Yj < 12 — i + j for some 1 < j < i. Since there are 12 — i + j — 1 boxes 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 D1 and any SSYT of shape D2 we have xi <fl—11+ 12 <j for each j = 1, 2,. . . , i. Therefore this gives a SSYT of shape D1 Ø D2. Therefore SD1Ø%D2= ss2,as desired. • 12 11 y1 Y2 yi yi 138 CHAPTER 6. REDUCTION TO FINITE VARIABLES Example With the following skew diagrams D1 and D2 we have 11 + 12 = 3 + 3 = 6 4 + 2 = n + i. Thus, Theorem 6.2.2 gives SD1G2D 48D12. 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. 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 D1 = B®2A and D2 = D®2C. The orem 6.2.2 shows that 8D1 =5 SASB and SD2 =5 SCSD. We note that A® B = (5, 5,5,3,3, 1, 1, 1)/(4, 4,2,2) = C 0 D, as is illustrated below. D1= D2= 139 CHAPTER 6. REDUCTION TO FINITE VARIABLES Further, we find that 5A.B =5 S(3,3,3,1,1,1)/(2,2)S(1,1,1,1) =5 8G.D from applying Theorem 6.2.2 to both A B and C D. A®B= =COD A•B= Thus we obtain SD1 5 —5 —5 —5 —5 —5 CD= SASB 5A.B + SAØB S(3,3,3,1,1,1)/(2,2)S(1,1,1,1) + (5,5,5,3,3,1,1,1)/(4,4,2,2) SC.D + SGQD 8C5D 140 CHAPTER 6. REDUCTION TO FINITE VARIABLES We have the following result to aid us when we are inspecting an equality of the form 5AGB = 5BØA Lemma 6.2.3 For skew diagrams A and B, we have 5AOB = SBOA if and only if 5A.B Proof Using Theorem 1.6.5 and the fact that SASB = 5BA, the result im mediately follows. 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 a1 and ar denote the lengths of the left-most and right-most column of A, respectively. Further, we let A — a1 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 = fl and5A—arB bt SB_b,,SA_a1,then we have 5AOB =, SB®A. Proof Using Theorem 6.2.2 and our assumption that SA_arSB_bj SB_br5Aat, we have SA.B n n 5Bbr S(ln)SA_at SB.A Thus Lemma 6.2.3 shows that 5A®B = SBOA. • The simplest application of the previous lemma is the following corollary. Corollary 6.2.5 Let n = a + b and 1 <i1 <2 <min{a, b}, then S((la)Ø. (b))o((la)Ø. (ib)) S((la)G. (lb))Ø((la)Ø1(ib)). 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, i1 = 2, and i2 = 1 in Corollary 6.2.5 we find that SD1G2 =5 S21 where D1 and D2 are as shown below. D1®D2= D2®D1= 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))Ø( l2)Øln_1))Ø(l) 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 5D =2 0. Otherwise, if j is the number of columns of length two in D, then 5D =2 (s(1,)) flk(5(k)), where the ek are 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 form 6a/(m) and ö,./(1m). 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 Richardson 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
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | 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 |
GraduationDate | 2010-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | 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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0071003/manifest