Schur positivity of skew Schur function differences and applications to ribbons and Schubert classes

DOI 10.1007/s10801-007-0113-0

Schur positivity of skew Schur function differences and applications to ribbons and Schubert classes

Ronald C. King·Trevor A. Welsh·Stephanie J. van Willigenburg

Received: 2 April 2007 / Accepted: 10 December 2007 / Published online: 21 December 2007

© Springer Science+Business Media, LLC 2007

Abstract Some new relations on skew Schur function differences are established both combinatorially using Schützenberger’s jeu de taquin, and algebraically using Jacobi-Trudi determinants. These relations lead to the conclusion that certain differ- ences of skew Schur functions are Schur positive. Applying these results to a basis of symmetric functions involving ribbon Schur functions confirms the validity of a Schur positivity conjecture due to McNamara. A further application reveals that cer- tain differences of products of Schubert classes are Schubert positive.

Keywords Jacobi-Trudi determinant·Jeu de taquin·Ribbon·Schubert calculus· Schur positive·Skew Schur function·Symmetric function

For Manfred Schocker 1970–2006.

S.J. van Willigenburg was supported in part by the National Sciences and Engineering Research Council of Canada.

R.C. King

School of Mathematics, University of Southampton, University Road, Southampton, Hampshire SO17 1BJ, UK

e-mail:rck@maths.soton.ac.uk

T.A. Welsh

Department of Physics, University of Toronto, 60 St. George Street, Toronto, ON, M5S 1A7 Canada e-mail:taw@maths.soton.ac.uk

S.J. van Willigenburg (

Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, BC, V6T 1Z2 Canada

e-mail:steph@math.ubc.ca

1 Introduction

Recently there has been much research on Schur positivity of differences of skew Schur functions, see for example [3, 8, 12]. In this paper we discover some new Schur positive differences of skew Schur functions and use them to derive a result on the basis of symmetric functions consisting of skew Schur functions indexed by certain ribbons, which is analogous to a well-known result on complete symmetric functions.

This paper is structured as follows. In the remainder of this section we review the necessary background concerning tableaux and skew Schur functions. In Sec- tion2we derive new relations on differences of skew Schur functions, in particular Lemma2.2and Theorem2.13. Lemma2.2is the technical heart of the paper and in view of its importance and their independent interest we offer both a combinatorial and an algebraic proof. The former invokes Schützenberger’s jeu de taquin, while the latter is based on Jacobi-Trudi determinants. In Section3we apply Theorem2.13to obtain various new Schur positive differences of skew Schur functions and resolve a conjecture of McNamara in Theorem3.3. Finally, in Section 4we show that the preceding results may be used to establish that certain differences of products of Schubert classes are Schubert positive, in a sense that we define.

1.1 Partitions and diagrams

Letα=(α₁, α₂, . . . , α_k)be a sequence of integers whose sum,|α|, isN. If the parts α_i, ofα, satisfyα₁, α₂,· · ·, α_k>0 then we say thatαis a composition ofN, denoted αN. We also say thatαhas length(α):=k. Ifα_i=α_i+1= · · · =α_i+j−1=awe normally denote the subsequenceαi, αi+1, . . . , αi+j−1bya^j. We denote by ()the unique composition of 0.

For use in some of our proofs later, recall that there exists a bijection between compositions of N and the collection 2^[N−1] of all subsets of {1,2, . . . , N −1} that sends a compositionα=(α1, . . . , α_(α))to the set of partial sumsS(α)= {α1, α1+α2, . . . , α1+α2+ · · · +α_(α)−1}. If the parts of the composition α satisfy α1≥α2≥ · · · ≥α_(α)then we sayαis a partition ofN, denotedαN. For clar- ity of exposition we usually denote sequences and compositions by α, β, σ, τ and partitions byλ, μ, ν, and we will use this convention next.

Three partial orders that exist on partitionsλandμare 1. the inclusion order:μ⊆λifμi≤λifor all 1≤i≤(μ);

2. the dominance order on partitionsλ, μN:μ≤domλif μ1+ · · · +μi≤λ1+ · · · +λi

for alli, where ifi > (λ)(resp.i > (μ)) thenλi:=0 (resp.μi:=0);

3. the lexicographic order on partitionsλ, μN:μ≤lexλ if for someiwe have μj=λj for 1≤j < iandμi< λi.

It is not hard to see that the lexicographic order extends the dominance order. It is also known, see for example [2], that the cover relations in the dominance order are

1. (λ, a, b, μ)dom (λ, a+1, b−1, μ)forλ_(λ)> a≥b > μ₁;

2. (λ, aⁿ, μ)dom (λ, a+1, aⁿ⁻², a−1, μ)forλ_(λ)> a > μ₁andn≥3.

For example,(3,2)dom(4,1)and(2,2,2,2)dom(3,2,2,1).

Given a partition λ=(λ1, λ2, . . . , λ_(λ))we can associate with it a (Ferrers or Young) diagram also denoted byλ that consists of λ_i left-justified boxes in row i when read from the top. For ease of referral, boxes will be described by their row and column indices. Furthermore, given two partitionsλ, μsuch thatμ⊆λ, the skew diagramλ/μis obtained from the diagramλby removing the subdiagram of boxes μfrom the top left corner. In terms of row and column indices

λ/μ= {(i, j )|(i, j )∈λ, (i, j )∈μ}. For example, if we denote boxes by×then

(3,3,2,1)/(1,1)= .

Additionally, two skew diagrams will be considered equivalent if one can be ob- tained from the other by the removal of empty rows or empty columns. We say a skew diagram is connected if it is edgewise connected.

We can describe skew diagramsλ/μa third way using 1- and 2-row overlap se- quences as defined in [13]. Letλ, μbe diagrams such thatλ/μis a skew diagram occupying(λ)rows. Then the 1-row overlap sequence ofλ/μis

r⁽¹⁾(λ/μ)=(λ₁−μ₁, λ₂−μ₂, . . . , λ_(μ)−μ_(μ), λ_(μ)+1, . . . , λ_(λ)) and the 2-row overlap sequence ofλ/μis

r⁽²⁾(λ/μ)=(λ2−μ1, λ3−μ2, . . . , λ_(μ)+1−μ_(μ), λ_(μ)+2, . . . , λ_(λ)).

Hence, considering our previous skew diagram

r⁽¹⁾((3,3,2,1)/(1,1))=(2,2,2,1), r⁽²⁾((3,3,2,1)/(1,1))=(2,1,1).

Note that this completely describesλ/μand so we can also denote the skew diagram by

λ/μ=(r⁽¹⁾(λ/μ)|r⁽²⁾(λ/μ)). (1.1) Ifr⁽²⁾(λ/μ)=(1^k)withk=(λ)−1 then we sayλ/μis a ribbon (or border strip or rim hook) and sincer⁽²⁾(λ/μ)is predetermined we can describe the ribbon com- pletely by the compositionr⁽¹⁾(λ/μ).

One last notion that we need for diagrams is that of inner and outer corners. Ifλis a diagram, then we say(i, j )is an inner corner ofλif(i, j )∈λandλwith the box in position(i, j )removed is also a diagram. Similarly we say(i, j )is an outer corner ofλif(i, j )∈λandλwith a box appended in position(i, j )is also a diagram. For

example, ifλ=(3,3,2,1)then the inner corners ofλare denoted by⊗and the outer corners by :

.

Inner and outer corners will play a vital role in the next subsection.

1.2 Tableaux and jeu de taquin

Consider a skew diagramλ/μ. We say we have a tableau,T, of shapeλ/μif each box is filled with a positive integer. In addition, we say we have a semistandard Young tableau (SSYT, plural SSYTx) if

1. As we read the entries in each row of T from left to right the entries weakly increase;

2. As we read the entries in each column ofT from top to bottom the entries strictly increase.

If we read the entries ofT from right to left and top to bottom then the resulting word is called the reading word ofT,w(T ). If, for eachi, the number ofis we have read is always at least the number of(i+1)s we have read then we sayw(T )is lattice.

Letc_i(T )be the total number ofis appearing inT and also inw(T ), then the list c(T ):=(c₁(T ), c₂(T ), . . .)is known as the content ofT and also ofw(T ). If T is a SSYT withnentries andc(T )=(1ⁿ)then we sayT is a standard Young tableau (SYT, plural SYTx).

Lastly, if we have a SSYT we are able to perform Schützenberger’s jeu de taquin (jdt), see for example [14], on it.

Definition 1.1 Given a SSYT,T, of shapeλ/μwe perform a forward-(jdt)-slide as follows:

1. Choose an inner corner ofμ,C=(i, j ).

2. Letc=min{T (i+1, j ), T (i, j+1)}orc=T (i+1, j )ifT (i+1, j )=T (i, j+1) or if only one ofT (i+1, j ), T (i, j+1)exists then that is taken to be the minimum value. LetCbe the positioncis in.

3. FormTby settingT (i, j )=cand lettingCbe empty.

4. SetC:=Cand return to the second step untilTis a SSYT.

Given a SSYT,T, of shapeλ/μwe perform a backward-(jdt)-slide as follows:

1. Choose an outer corner ofλ,D=(i, j ).

2. Let d=max{T (i−1, j ), T (i, j−1)} or d=T (i−1, j ) if T (i−1, j )= T (i, j−1) or if only one of T (i −1, j ), T (i, j −1) exists then that is taken to be the maximum value. LetDbe the positiondis in.

3. FormTby settingT (i, j )=dand lettingDbe empty.

4. SetD:=Dand return to the second step untilTis a SSYT.

Note the output of each algorithm is a SSYT and that these slides are invertible, as illustrated in the following example.

Example 1.2 LetT = ^{1 31 1 2}

2 4

andC=(1,2)then a forward-jdt-slide takes place as shown, where•indicates the position ofCat each stage.

Conversely, letU= ^{1 1 1 23}

2 4

andD=(2,3)then a backward-jdt-slide takes place as shown, where•indicates the position ofDat each stage.

We are now ready to introduce skew Schur functions.

1.3 The algebra of symmetric functions

For any setT of tableaux, we define the generating function g(T)=

T∈T

x^{c(T )} (1.2)

where x^{c(T )}:=x₁^{c1(T )}x^c₂^{2(T )}· · ·. This generating function can be used to define a basis of the algebra of symmetric functions,, known as the basis of Schur functions {s_λ}λNthrough

s_λ:=g(T^λ) (1.3)

whereT^λis the set of all SSYTx of shapeλ. Another basis of the algebra of symmet- ric functions is the basis of complete symmetric functions{h_λ}λNwhereh₀:=1,

h_λ:=h_λ1h_λ2· · ·h_λ(λ) and

h_k:=

i₁≤i₂≤···≤i_k

x_i1x_i2· · ·x_ik.

Either of these bases can be used to describe our desired objects of study, skew Schur functions.

Given a skew diagramλ/μwe define the skew Schur function by

s_λ/μ:=g(T^λ/μ) (1.4)

whereT^λ/μis the set of all SSYTx of shapeλ/μ. For clarity of exposition we will use the less conventional overlap notation

s_λ/μ= {λ/μ} = {r⁽¹⁾(λ/μ)|r⁽²⁾(λ/μ)} (1.5) to state our results from the next section onwards. In terms of complete symmetric functions

s_λ/μ=h_{λi−μj−i+j} ^(λ)

i,j=1 (1.6)

whereμj:=0 ifj > (μ)andhk:=0 ifk <0, see for example [15]. These deter- minants are known as Jacobi-Trudi determinants. Expanding, instead, in the Schur function basis we have

s_λ/μ=

ν

c^λ_μνs_ν (1.7)

where c_μν^λ is the Littlewood-Richardson coefficient defined to be the number of SSYTx,T, of shapeλ/μwherew(T ) is lattice andc(T )=ν. This manner of de- terminingc^λ_μνis called the Littlewood-Richardson rule, and clearly yields thatc^λ_μνis a non-negative integer.

In what follows, we are especially interested in the case whereλ/μis a ribbon.

In such a case,λ/μ=(α|1^(λ)−1)whereα=r⁽¹⁾(λ/μ), and we definerα=sλ/μ≡ {α|1^(λ)−1}. We callr_αa ribbon Schur function. The set{r_λ}λNforms another basis for the algebra of symmetric functions [1, Section 2.1]. Ribbon Schur functions are also significant because they are, for example, useful in computing the number of permutations with a given cycle structure and descent set [5], and they can be used to compute skew Schur functions via determinants consisting of associated ribbon Schur functions [7].

Note that the Jacobi-Trudi determinant (1.6) for the ribbon Schur function r_α= {α1, . . . , α_(α)|1^(α)−1}

takes the form

r_α=h_Rij ^(α)

i,j=1 (1.8)

with

R_ij=

⎧⎨

⎩

α_i+α_i+1+ · · · +α_j ifi≤j;

0 ifi=j+1;

−1 ifi > j+1,

(1.9)

so that

r_α=

h_α1 h_α1+α2 h_α1+α2+α3· · · 1 h_α2 h_α2+α3 · · · 0 1 h_α3 · · · ... ... ... . ..

(1.10)

where we have substitutedh0=1 andh_k=0 fork <0.

More generally, for

s_λ/μ= {α1, . . . , α_(α)|β1+1, . . . , β(α)−1+1}

we have

s_λ/μ=h_Qij ^(α)

i,j=1 (1.11)

with

Q_ij=

⎧⎪

⎪⎨

⎪⎪

⎩

(α_i+α_i+1+ · · · +α_j)−(β_i+β_i+1+ · · · +β_j−1) ifi≤j−1;

α_i ifi=j;

β_j ifi=j+1;

−(α_j+1+α_j+2+ · · · +α_i−1)+(β_j+β_j+1+ · · · +β_i−1)ifi > j+1, (1.12) so that

sλ/μ=

hα₁ hα₁+α₂−β₁ hα₁+α₂+α₃−β₁−β₂· · · hβ₁ hα₂ hα₂+α₃−β₂ · · · h_{β1+β2−α2} h_β2 h_α3 · · · h_{β1+β2+β3−α2−α3}h_{β2+β3−α3} h_β3 · · ·

... ... ... . ..

. (1.13)

Note that (1.7) is a non-negative linear combination of Schur functions. This mo- tivates the following definition.

Definition 1.3 If a symmetric functionf ∈can be written as a non-negative linear combination of Schur functions then we say thatf is Schur positive.

Our goal for the remainder of this paper is to construct new Schur positive expres- sions. We end our introduction with a classical Schur positive linear combination that will serve as a motivation for some of our later results.

Theorem 1.4 [9, p. 119] Letλ, μN then h_μ−h_λ

is Schur positive if and only ifμ≤domλ.

2 Skew Schur function differences

In this section we study a variety of differences of skew Schur functions, and more- over discover that some of them are Schur positive. Before we proceed with these differences, we introduce the following hypothesis.

Hypothesis 2.1 Letσ andτ be compositions such that(σ )=s≥0 and(τ )=t≥ 0, and letσ andτ be sequences of non-negative integers that satisfy the following conditions:

1. The lengths ofσ andτ aresandtrespectively;

2. σ_s=1 whens >0;

3. τ1=1 whent >0;

4. σ¯_i≤min{σ_i, σ_i+1}for 1≤i < s, andτ¯_i≤min{τ_i, τ_i−1}for 1< i≤t.

2.1 A combinatorial approach

Lemma 2.2 Assumeσ, τ, σ , τ satisfy Hypothesis2.1. Ifm≥1,n≥2 and 0≤x≤ min{m, n−1}then

{σ, m, n, τ| ¯σ , x,τ¯} − {σ, m+1, n−1, τ| ¯σ , x,τ¯}

=

{σ, m, n, τ| ¯σ , x+1,τ¯} ifx < m;

−{σ\σ_s, m+σ_s, n, τ| ¯σ\ ¯σ_s, m+1,τ¯} ifx=m,

−

{σ, m+1, n−1, τ| ¯σ , x+1,τ¯} ifx < n−1;

−{σ, m+1, n−1+τ₁, τ\τ₁| ¯σ , n,τ¯\ ¯τ₁} ifx=n−1.

(2.1)

Ifs=0 then the term containingσ\σ_s is to be omitted. Similarly, ift=0 then the term containingτ\τ₁is to be omitted.

Proof In this proof, we use Schützenberger’s jeu de taquin to construct invertible maps between various sets of tableaux of skew shape, and then use the corresponding generating function (1.2), to obtain (2.1) by means of (1.4) and (1.5). The proof runs through the four cases demarcated by (2.1). First we prove the case wherex < mand x < n−1. The other three cases are then treated as variants of this case.

Before we begin, we introduce some notation. For any skew diagramκ=(α|β), letT^κdenote the set of all SSYTx of shapeκ, so that{κ} =g(T^κ).

Let

ξ=(σ, m, n, τ| ¯σ , x,τ )¯ ζ=(σ, m+1, n−1, τ| ¯σ , x,τ )¯

Fig. 1 Map fromT^ξtoU1⊂T^ξ∗via a forward-slide

Fig. 2 Map fromT^ξtoU2⊂T^ζvia a forward-slide

Fig. 3 Map fromU1⊂T^ξ∗toU₁^<⊂T^ξ+via left-shifting the entriesσ

and letT ∈T^ξ. For the purposes of a forward-jdt-slide, letCbe the vacancy imme- diately to the left of the first entry in the(s+1)th row ofT.

We now consider our first case, for whichx < m andx < n−1. The latter of these constraints implies that the vacancyChas just one node fromT below it. Thus, forward-slidingCthroughT necessarily results in this vacancy migrating to the end of either the(s+1)th or(s+2)th row, as depicted in Figs.1and2respectively.

In these two cases, the resulting SSYT is of shape ξ^∗=(σ, m, n, τ| ¯σ\ ¯σs,0, x+1,τ )¯ or shape ζ respectively. Let U1 and U2 be the sets of SSYTx of shapes ξ^∗andζ respectively that arise from performing a forward-slide as above on all the elements ofT^ξ. Then{ξ} =g(U1)+g(U2).

However, neitherU1norU2is the full set of SSYTx of shapeξ^∗orζ respectively.

In particular, for each tableau U ∈U1, the entry at the end of the (s +1)th row (immediately to the left of the vacancy) is larger than that at the beginning of thesth row (immediately above the vacancy), because in the preimageT ofU, the former of these entries would have been immediately below the latter. We claim that all SSYTx of shapeξ^∗that satisfy this constraint occur inU1. To see this, letU be an arbitrary such SSYT. Performing a backward-jdt-slide onU necessarily results in a SSYT of shapeξ, which is thus an element ofT^ξ. That forward-sliding is the inverse of backward-sliding then guarantees thatU∈U1.

Now form the setU₁^<of tableaux by, for each tableauU∈U1, shifting each entry in the firstsrows ofU one position to its left. This shift is indicated in Fig.3. The elements ofU₁^<are of shape

ξ⁺=(σ, m, n, τ| ¯σ , x+1,τ ).¯

The above constraint on the entries of each element of U1ensures that each element ofU₁^<is a SSYT. Moreover, by reversing the shift, we see thatU₁^<=T^ξ+. Therefore,

Fig. 4 Map fromT^ζ toV1⊂T^ζ∗via a backward-slide

Fig. 5 Map fromT^ζ toV2⊂T^ξvia a backward-slide

Fig. 6 Map fromV1⊂T^ζ∗toV₁^>⊂T^ζ+via right-shifting the entriesτ

T^ξ+ andU1are in bijection, and thus {ξ⁺} =g(U1). Consequently, {ξ} − {ξ⁺} = g(U2).

Now consider T ∈T^ζ. For the purposes of a backward-slide, let D be the va- cancy immediately to the right of the final entry in the (s+2)th row of T. The constraint x < m implies that the vacancy D has just one node from T above it.

Thus, backward-slidingD throughT necessarily results in this vacancy migrating to the beginning of either the(s+2)th or (s+1)th row. These two instances are depicted in Figs.4 and5respectively. In these two cases, the resulting SSYT is of shapeζ^∗=(σ, m+1,n−1, τ| ¯σ , x+1,0,τ¯\ ¯τ1)or shapeξ respectively. LetV1and V2be the sets of SSYTx of shapesζ^∗andξ respectively that result from performing a backward-slide as above on all the elements ofT^ζ. Then{ζ} =g(V1)+g(V2).

In analogy with the treatment ofU1above, for each elementV ∈V1we shift each of the entries in rowss+3 and below one position to the right, as indicated in Fig.6.

This forms a setV₁^>of SSYTx of shape

ζ⁺=(σ, m+1, n−1, τ| ¯σ , x+1,τ ).¯ This yields{ζ⁺} =g(V1), and consequently,{ζ} − {ζ⁺} =g(V2).

Now, backward-sliding maps the elements ofU2⊂T^ζ bijectively onto a subset of V2because backward-sliding is inverse to forward-sliding. Similarly, forward-sliding maps the elements ofV2⊂T^ξbijectively onto a subset ofU2because forward-sliding is inverse to backward-sliding. It follows that U2 andV2are in bijection, and thus g(U2)=g(V2). Consequently,{ξ} − {ξ⁺} = {ζ} − {ζ⁺}, which yields the case of the lemma for whichx < mandx < n−1.

We now consider the case in whichx < mandx=n−1. In this case, forT ∈T^ξ, the vacancyChas more than one entry fromT below it (assume for now thatτ is not empty). Then, on performing a forward-slide, the vacancy migrates to one of three

Fig. 7 Map fromT^ξtoU3via a forward-slide

Fig. 8 Map fromU3toU₃^∧⊂T^ηvia up-shifting of some entriesτ

positions. The first two are, as in the first case above, at the ends of rowss+1 and s+2. The third position is at the bottom of the column that initially containedC. This instance is depicted in Fig.7. LetU3be the set of all SSYTx that result in this third case. As above,U1andU2are defined to be the sets of SSYTx of shapesξ^∗ andζ respectively that result from the first two cases. Then{ξ} =g(U1)+g(U2)+g(U3).

Moreover, we obtain {ξ⁺} =g(U1) as in the first case, resulting in{ξ} − {ξ⁺} − g(U3)=g(U2).

Note that, forU∈U3, each entry in the same column ofUas the vacancy is greater than or equal to the entry (if there is one) below and to its left. This follows because Uwas obtained from a SSYTT ∈T^ξby a sequence of slides that move downwards.

Now form the setU₃^∧by, for eachU∈U3, shifting up one position each entry in all the columns to the left of that of the vacancy. This shift is depicted in Fig.8. Each of the resulting elements ofU₃^∧is of shape

η=(σ, m+1, n−1+τ₁, τ\τ₁| ¯σ , x+1,τ¯\ ¯τ₁).

In view of the above note, each of these elements is a SSYT. Indeed,U₃^∧is in bijection withT^η, as may be seen by, in each element of the latter, shifting downward each of the entries in the columns to the left of that of the vacancy and then performing a backward-slide. Therefore,{η} =g(U₃^∧)=g(U3). Then, from above,{ξ} − {ξ⁺} − {η} =g(U2). Whenτ is empty, the setsg(U3)andg(U₃^∧)are empty, and the correct expression is given upon setting{η} =0.

Now, as in the first case, considerT ∈T^ζ, and for the purposes of a backward- slide, letDbe the vacancy immediately to the right of the final entry in the(s+2)th row ofT. However,x=n−1, here, implies that the (s+1)th and(s+2)th rows ofT are flush at their left edges, and therefore terms depicted in Fig.4do not arise.

Consequently,{ζ} =g(V2)where, as in the first case,V2is the set of SSYTx of shape ξ that results from performing a backward-slide on all the elements ofT^ζ.

Fig. 9 Map fromT^ζ toV3via a backward-slide

Fig. 10 Map fromV3toV₃^∨⊂T^γ via down-shifting of some entriesσ

As in the first case,U2andV2are in bijection, whenceg(U2)=g(V2). Thereupon, {ξ} − {ξ⁺} − {η} = {ζ}, and the required expression in the case for whichx < mand x=n−1 follows.

The case for whichx=mandx < n−1 is similar to the case just considered, but rotated 180^◦. Here, rows(s+1)and(s+2)of T ∈T^ξ are flush at their right ends. Consequently, forward-slidingC throughT necessarily results in this vacancy migrating to the end of the(s+2)th row, as in Fig.2. The resulting SSYT is then necessarily of shapeζ. With the setU2formed by enacting this forward-slide on all elements ofT^ξ, we obtain{ξ} =g(U2).

Now, as in the previous cases, considerT ∈T^ζ, and letDbe the vacancy immedi- ately to the right of the final entry in the(s+2)th row ofT. In this instance, though, D has more than one entry of T above it (provided thatσ is not empty). Thus in addition to the two terms arising from the migration ofDto the beginning of rows (s+1)and(s+2), as in Fig.4and Fig.5respectively, there is a term arising from the migration ofDdirectly upwards, as in Fig.9. LetV3be the set of all SSYTx that result in this third instance. As in the first case,V1andV2are defined to be the sets of SSYTx of shapesζ^∗andξ respectively that result from the first two instances. Then {ζ} =g(V1)+g(V2)+g(V3). Moreover,{ζ⁺} =g(V1)as in the first case, resulting in{ζ} − {ζ⁺} −g(V3)=g(V2).

The elements ofV3 are now treated in analogy with the treatment ofU3above.

Namely, we form the set V₃^∨ by, for each tableauV ∈V3, shifting downward each entry in the columns ofV to the right of the vacancy. This shift is depicted in Fig.10.

We see that each element ofV₃^∨is a SSYT of shape

γ=(σ\σs, m+σs, n, τ| ¯σ\ ¯σs, m+1,τ ).¯

Indeed, by reversing the above construction, we obtain V₃^∨ =T^γ. Therefore, g(V₃^∨)=g(V3)= {γ}. It now follows that {ζ} − {ζ⁺} − {γ} =g(V2), where we set{γ} =0 ifσ is empty.

As in the previous cases,U2andV2are in bijection, whenceg(U2)=g(V2), and thus{ξ} = {ζ} − {ζ⁺} − {γ}. This yields the required result in the case for which x=mandx < n−1.

The case for whichx=mandx=n−1 is an amalgam of the two previous cases.

Here, rows(s+1)and(s+2)ofT ∈T^ξare flush at their right ends, but the vacancy Chas more than one entry fromT below it. Consequently, forward-slidingCthrough T necessarily results in this vacancy migrating to the end of the(s+2)th row, as in Fig.2, or to the bottom of the column which originally containedC, as in Fig.7.

Then, in comparison with the case for whichx < mandx=n−1, the setU1does not arise, and we obtain{ξ} − {η} =g(U2). Here again, ifτ is empty, we set{η} =0.

Similarly, the backward-sliding process in this case is as in the case for which x =mandx < n−1, except that the setV1 does not arise, and consequently we obtain{ζ} − {γ} =g(V2). Here again, ifσ is empty, we set{γ} =0.

The familiar bijection betweenU2andV2then implies that{ξ} − {η} = {ζ} − {γ}, giving the required result in thisx=m=n−1 case, thereby completing the proof

of Lemma2.2.

In order to generalise this result and accommodate special cases of the type ap- pearing in (2.1), it is convenient to introduce the skew Schur functionsK_τ,^σ,_τ^σ_¯^¯(m, n|x) that, for positive integersm, n≥1, 0≤x≤min{m, n} +1 andσ, τ, σ , τ satisfying Hypothesis2.1, are defined as follows:

K_τ,^σ,_τ¯^σ¯(m, n|x)

=

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

{σ, m, n, τ| ¯σ , x,τ¯} ifx≤mandx≤n;

−{σ\σ_s, m+σ_s, n, τ| ¯σ\ ¯σ_s, x,τ¯} ifx=m+1 andx≤n;

−{σ, m, n+τ1, τ\τ1| ¯σ , x,τ¯\ ¯τ1} ifx≤mandx=n+1;

{σ\σ_s, m+σ_s, n+τ1, τ\τ1| ¯σ\ ¯σ_s, x,τ¯\ ¯τ1} ifx=m+1 andx=n+1.

(2.2) Ifs=0 then the term containingσ\σ_s is to be set to 0. Similarly, ift=0 then the term containingτ\τ1is to be set to 0.

Lemma 2.3 Letm, n, m, nbe positive integers for whichm+n=m+n and let x, xbe non-negative integers for whichx, x≤min{m, n, m, n} +1 then

K_τ,^σ,_τ^σ_¯^¯(m, n|x)−K_τ,^σ,_τ^σ_¯^¯(m, n|x)=K_τ,^σ,_τ^σ_¯^¯(m, n|x)−K_τ,^σ,_τ^σ_¯^¯(m, n|x). (2.3) Proof We first write the equation (2.1) in the form

K_τ,^σ,_τ^σ_¯^¯(p, q|y)−K_τ,^σ,_τ^σ_¯^¯(p+1, q−1|y)

=K_τ,^σ,_τ^σ_¯^¯(p, q|y+1)−K_τ,^σ,_τ^σ_¯^¯(p+1, q−1|y+1) (2.4) wherep≥1,q≥2, and 0≤y≤min{p, q−1}. If, in addition,y < y≤min{p+ 1, q}, then repeated use of (2.4) yields

K_τ,^σ,_τ¯^σ¯(p, q|y)−K_τ,^σ,_τ^σ_¯^¯(p+1, q−1|y)

=K_τ,^σ,_τ^σ_¯^¯(p, q|y)−K_τ,^σ,_τ^σ_¯^¯(p+1, q−1|y). (2.5) Without loss of generality, we only need to prove (2.3) in the case for whichm <

mandx < x. In this case K_τ,^σ,_τ^σ_¯^¯(m, n|x)−K_τ,^σ,_τ¯^σ¯(m, n|x)

=

m−1 i=m

K_τ,^σ,_τ¯^σ¯(i, m+n−i|x)−K_τ,^σ,_τ^σ_¯^¯(i+1, m+n−i−1|x)

=

m−1 i=m

K_τ,^σ,_τ¯^σ¯(i, m+n−i|x)−K_τ,^σ,_τ^σ_¯^¯(i+1, m+n−i−1|x)

=K_τ,^σ,_τ¯^σ¯(m, n|x)−K_τ,^σ,_τ^σ_¯^¯(m, n|x)

(2.6)

where (2.5) has been used to convert each summand of the first sum into the corre- sponding summand of the second sum. This proves (2.3).

2.2 An algebraic approach

As an alternative to the above combinatorial approach to Lemmas 2.2and2.3, an algebraic approach may be based on the use of the Jacobi-Trudi determinants, (1.6) or (1.13), which express a skew Schur function in terms of complete symmetric func- tions.

First, it is convenient to introduce the following family of determinants:

H_T^S(m, n|z)=

h_S1,1· · ·h_S1,s h_S1,s+mh_S1,s+m+n−zh_{S1,s+m+n−z+T1,1}· · · h_{S1,s+m+n−z+T1,t} ... . .. ... ... ... ... . .. ...

hS_s,1 · · ·hS_s,s hS_s,s+mhS_s,s+m+n−zhS_s,s+m+n−z+T_1,1 · · · hS_s,s+m+n−z+T_1,t

0 · · ·1 hm hm+n−z hm+n−z+T_1,1 · · · hm+n−z+T_1,t

0 · · ·0 hz hn hn+T_1,1 · · · hn+T_1,t

0 · · ·0 0 1 hT_1,1 · · · hT_1,t

... . .. ... ... ... ... . .. ... 0 · · ·0 0 0 h_Tt,1 · · · h_Tt,t

(2.7)

whereS andT ares×sandt×t matrices of integers, withs andt non-negative integers, whilemandnare positive integers andzis any integer. As usualhk=0 for k <0 andh₀=1. It is to be understood that any sequence 0· · ·1, whether vertical or horizontal, is a sequence of 0 s followed by a single 1 in the position indicated.

With this definition we have the following:

Lemma 2.4 Letm, n, m, nbe positive integers such thatm+n=m+n. Then the difference

H_T^S(m, n|z)−H_T^S(m, n|z) (2.8)

is independent ofzfor all integersz.

Proof SinceH_T^S(m, n|z)is the determinant of a matrix that is block triangular, save for the single subdiagonal elementh_z, it may be evaluated by adding to the determi- nant of the block triangular matrix the contribution arising fromh_zand its cofactor.

This follows from the fact that the expansion of the determinantH_T^S(m, n|z)is linear inh_z, that is to say of the formX+h_zY, with the termXcalculated by settingh_z=0 and the termY equal to the cofactor ofhz. Since, in addition, the determinant of a block triangular matrix is the product of the determinant of its diagonal blocks, we have

H_T^S(m, n|z)=

hS_1,1· · · hS_1,s hS_1,s+m

... . .. ... ... h_Ss,1 · · · h_Ss,s h_Ss,s+m 0 · · · 1 h_m

·

hnhn+T_1,1 · · ·hn+T_1,t

1 hT1,1 · · ·hT1,t

... ... . .. ... 0 h_Tt,1 · · ·h_Tt,t

−h_z ·

h_S1,1 · · ·h_S1,s h_S1,s+m+n−zh_{S1,s+m+n−z+T1,1}· · · h_{S1,s+m+n−z+T1,t} ... . .. ... ... ... . .. ...

h_Ss,1 · · ·h_Ss,s h_Ss,s+m+n−zh_{Ss,s+m+n−z+T1,1} · · · h_{Ss,s+m+n−z+T1,t} 0 · · ·1 h_m+n−z h_m+n−z+T1,1 · · · h_m+n−z+T1,t 0 · · ·0 1 h_T1,1 · · · h_T1,t ... . .. ... ... ... . .. ... 0 · · ·0 0 hT_t,1 · · · hT_t,t

.

(2.9) It can be seen from this that for allm, n, m, n∈Nwithm+n=m+nand for all integerszwe have the identity

H_T^S(m, n|z)−H_T^S(m, n|z)

=

hS_1,1 · · ·hS_1,s hS_1,s+m

... . .. ... ... h_Ss,1 · · ·h_Ss,s h_Ss,s+m 0 · · ·1 h_m

·

hnhn+T_1,1· · · hn+T_1,t

1 h_T1,1 · · · h_T1,t ... ... . .. ... 0 h_Tt,1 · · · h_Tt,t

−

h_S1,1 · · ·h_S1,s h_S1,s+m

... . .. ... ... h_Ss,1 · · ·h_Ss,s h_Ss,s+m

0 · · ·1 h_m

·

h_nh_n+T_1,1 · · ·h_n+T_1,t

1 hT_1,1 · · ·hT_1,t

... ... . .. ... 0 h_Tt,1 · · ·h_Tt,t

(2.10)

where it is to be noted that the resulting expression is independent ofz, as claimed.

To make the connection with Lemmas2.2and2.3by means of Jacobi-Trudi de- terminants, we introduce the following hypothesis.

Hypothesis 2.5 Let σ, τ, σ , τ satisfy Hypothesis2.1, and let the matricesS andT have matrix elements defined in terms of these by

S_ij=

⎧⎪

⎪⎪

⎪⎪

⎪⎨

⎪⎪

⎪⎪

⎪⎪

⎩

(σ_i+σ_i+1+ · · · +σ_j)

−(σ_i+σ_i+1+ · · · +σ_j−1)−i+j ifi≤j−1;

σ_i ifi=j;

σ_j−1 ifi=j+1;

−(σ_j+1+σ_j+2+ · · · +σ_i−1)

+(σj+σj+1+ · · · +σi−1)−i+j ifi > j+1,

(2.11)

for 1≤i, j≤s, and

Tij=

⎧⎪

⎪⎪

⎪⎪

⎪⎨

⎪⎪

⎪⎪

⎪⎪

⎩

(τi+τi+1+ · · · +τj)

−(τi+τi+1+ · · · +τj−1)−i+j ifi≤j−1;

τi ifi=j;

τj−1 ifi=j+1;

−(τj+1+τj+2+ · · · +τi−1)

+(τ_j+τ_j+1+ · · · +τ_i−1)−i+j ifi > j+1,

(2.12)

for 1≤i, j≤t.

We then have

Lemma 2.6 Assume thatS andT satisfy Hypothesis2.5. If 0≤x≤min{m, n} +1 then

H_T^S(m, n|x−1)=K_τ,^σ,_τ^σ_¯^¯(m, n|x). (2.13) Proof Letz=x−1. In the casez <min{m, n}, under the given hypothesis regarding SandT, comparing the determinant (2.7) with the general Jacobi-Trudi determinant (1.13) for a skew Schur function, expressed in overlap notation by way of (1.12), and noting thatσ_s=τ₁=1, immediately gives

H_T^S(m, n|x−1)= {σ, m, n, τ| ¯σ , x,τ¯}. (2.14) Thanks to the definition (2.2), this proves (2.13) in the casex≤min{m, n}.

In the z=m < ncase, if s=0 thenH_T^S(m, n|m)=0 since the first and sec- ond rows of determinant (2.7) coincide. On the other hand, fors >0 the entries of H_T^S(m, n|m)in the(s+1)th and(s+2)th rows all coincide apart from a single entry 1 in the(s+1)th row. Consideration of the cofactor of this element then yields

H_T^S(m, n|m)= −{σ\σs, m+σs, n, τ|σ\σs, m+1, τ} (2.15) fors >0. Once again, the definition (2.2) is such that this proves (2.13) in the case x−1=m < n.

Similarly in thez=n < mcase, ift=0 thenH_T^S(m, n|n)=0 since the(s+1)th and(s+2)th columns coincide. Fort >0 the entries ofH_T^S(m, n|n)in the(s+1)th