Séminaire Lotharingien de Combinatoire 57 (2008), Article B57e

A DECOMPOSITION OF SCHUR FUNCTIONS AND AN ANALOGUE OF THE ROBINSON–SCHENSTED–KNUTH ALGORITHM

S. MASON

Abstract. We exhibit a weight-preserving bijection between semi-standard Young tableaux and semi-skyline augmented fillings to provide a combinatorial proof that the Schur functions decompose into nonsymmetric functions indexed by compositions. The insertion procedure involved in the proof leads to an analogue of the Robinson–Schensted– Knuth Algorithm for semi-skyline augmented fillings. This procedure commutes with the Robinson–Schensted–Knuth Algorithm, and therefore retains many of its properties.

1. Introduction

Given a partition λ = (λ_{1}, λ_{2}, …), the Schur function s_{λ} = s_{λ}(x) in the variables x = (x_{1}, x_{2}, …) is the formal power series s_{λ} = ∑_{T} x^{T}, where the sum is over all semi-standard Young tableaux T of shape λ. A semi-standard Young tableau is a diagram consisting of rows of squares such that the i^{th} row contains λ_{i} squares, called cells. This diagram, called the Young (or Ferrers) diagram, is drawn in the first quadrant, French style, as in [1]. Each of these cells is then assigned a positive integer entry so that the entries are weakly increasing along rows and strictly increasing along columns, where the rows are read from left to right and the columns are read from bottom to top. The values assigned to the cells of λ collectively form the multiset {1^{a_{1}}, 2^{a_{2}}, …, n^{a_{n}}}, for some n, where a_{i} is the number of times i appears in T. The weight of the semi-standard Young tableau (SSYT) T is given by x^{T} = ∏_{i=1}^{n} x_{i}^{a_{i}}. The sum of the weights of all SSYT of shape λ is the Schur function s_{λ}. See [8] for a more detailed discussion of symmetric functions and Schur functions in particular.

The Macdonald polynomials H̃_{λ}(x; q, t) are a class of functions symmetric in x = (x_{1}, x_{2}, …) with coefficients in ℚ(q, t). Macdonald introduced them in [5] and conjectured that their expansion in terms of Schur polynomials should have positive coefficients. A combinatorial formula for the Macdonald polynomials is proved by Haglund, Haiman, and Loehr in [2]. A corresponding combinatorial formula for the integral form Macdonald polynomials, J_{λ}, is obtained from the plethystic substitution which transforms the H̃_{λ} polynomials into integral form.

Building on this work, Haglund, Haiman, and Loehr [3] derive a combinatorial formula for nonsymmetric Macdonald polynomials, which gives a new decomposition of J_{λ} into nonsymmetric components. Letting q = t = ∞ in this decomposition and using the fact that J_{λ}(x; q, q) = s_{λ}(x) produces the identity

2000 Mathematics Subject Classification. Primary 05E05; Secondary 05E10.

Key words and phrases. algebraic combinatorics, symmetric functions, Macdonald polynomials.

Work partially supported by NSF postdoctoral research fellowship DMS-0603351.

(1.1)  s_{λ}(x) = ∑_{γ∼λ} Ê_{γ}(x; 0, 0),

summed over all rearrangements γ of the partition λ, denoted γ ∼ λ. (A rearrangement of a partition λ is an ordered sequence of non-negative integers (a weak composition), γ, whose parts, when rearranged into weakly decreasing order, form the partition λ.) Here Ê_{γ}(x; 0, 0) is the specialization of the nonsymmetric Macdonald polynomial studied by Marshall [6]. (We use the form Ê instead of E and replace q and t with q^{−1} and t^{−1} because the associated combinatorics is more elegant in this setting.) The polynomial Ê_{γ}(x; 0, 0) can be described combinatorially through objects called semi-skyline augmented fillings constructed using the statistics from [3].

We provide a combinatorial proof of this decomposition of the Schur functions in Section 3 by constructing a weight-preserving bijection Ψ between semi-standard Young tableaux and semi-skyline augmented fillings. We build a semi-skyline augmented filling through an insertion procedure similar to Schensted insertion. This procedure is the fundamental operation in an analogue of the Robinson–Schensted–Knuth algorithm.

Theorem 1.1. There exists a bijection between ℕ−matrices with finite support and pairs (F, G) of semi-skyline augmented fillings of compositions which rearrange the same partition.

This bijection is described in Section 4. We prove that it commutes with the Robinson– Schensted–Knuth (RSK) algorithm and retains the symmetry of the RSK algorithm plus many of its other properties. We also describe the standardization of a semi-skyline augmented filling (SSAF) and prove that the RSK analogue commutes with standardization.

2. Combinatorial description of the functions Ê_{γ}(x; 0, 0)

The functions Ê_{γ}(x; 0, 0) are obtained from the integral form nonsymmetric Macdonald polynomials Ê_{γ}(x; q, t) by letting q and t approach zero. Haglund, Haiman, and Loehr provide a combinatorial formula for nonsymmetric Macdonald polynomials [3] which can be specialized to obtain a combinatorial formula for nonsymmetric Schur functions. Several definitions are necessary in order to describe this formula.

2.1. Statistics on fillings. Let γ = (γ_{1}, γ_{2}, …) be a weak composition of n into m parts. The column diagram of γ is the figure dg′(γ) consisting of n cells arranged into columns, as in [3]. The i^{th} column contains γ_{i} cells, and the number of cells in a column is called the height of that column. A cell a in a column diagram is denoted a = (i, j), where i is the column index and j is the row index.

The augmented diagram of γ, defined by d̂g(γ) = dg′(γ) ∪ {(i, 0) : 1 ≤ i ≤ m} is the column diagram with m extra cells adjoined in row 0. In this paper the adjoined row, called the basement, always contains the numbers 1 through m in strictly increasing order. (We italicize the basement entries to avoid confusion.)

The augmented diagram for γ = (0, 2, 0, 3, 1, 2, 0, 0, 1) is depicted below.

d̂g(γ) = _{1 2 3 4 5 6 7 8 9}

An augmented filling, σ̂, of an augmented diagram d̂g(γ) is a function σ̂ : d̂g(γ) → ℤ_{+}, which can be pictured as an assignment of positive integer entries to the cells of γ. Let σ̂(i) denote the entry in the i^{th} cell of the augmented diagram encountered when d̂g(γ) is read across rows from left to right, beginning at the highest row and working down to the bottom row. This ordering of the cells is called the reading order. A cell a = (i, j) precedes a cell b = (i′, j′) in the reading order if either j′ < j or j′ = j and i′ > i. The reading word read(σ̂) is obtained by recording the non-basement entries in reading order. The content of a filling σ̂ is the multiset of non-basement entries which appear in the filling. (See Figure 2.1.)

A pair of cells a and b are called attacking if either a and b are in the same row or a and b are in adjacent rows, with the entry in the higher row strictly to the right of the entry in the lower row. (That is, a = (i_{1}, j_{1}) and b = (i_{2}, j_{2}) are attacking if either j_{1} = j_{2}, or j_{2} − j_{1} = 1 and i_{1} < i_{2}, or j_{1} − j_{2} = 1 and i_{2} < i_{1}.) A non-attacking filling is a filling such that σ̂(a) ≠ σ̂(b) for every pair of attacking cells a and b.

Haglund, Haiman and Loehr introduce the statistics Des(σ̂) and Inv(σ̂) to describe the nonsymmetric Macdonald polynomials. As in [1], a descent of σ̂ is a pair of entries σ̂(a) > σ̂(b), where the cell a is directly above b. (If b = (i, j), then a = (i, j + 1).) Call Des(σ̂) = {a ∈ dg′(γ) : σ̂(a) > σ̂(b) is a descent} the descent set and define the leg of u (denoted l(u)) to be the number of cells above u in the column of d̂g(γ) containing u. Let

maj(σ̂) = ∑_{u∈Des(σ̂)}(l(u) + 1).

Consider the cell u = (i, j) and let C_{u} be the column containing u. The arm of u, denoted a(u), is the number of cells to the right of u in row i appearing in columns whose height is weakly less than the height, h, of C_{u} plus the number of cells to the left of u in row i − 1 appearing in columns whose height is strictly less than h.

Let a_{1} = (i_{1}, j_{1}), a_{2} = (i_{2}, j_{2}), and a_{3} = (i_{3}, j_{3}) be three cells in d̂g(γ) such that column i_{1} is taller than or equal in height to column i_{2}. If j_{1} = j_{2}, j_{1} − j_{3} = 1, and i_{1} = i_{3}, then a_{1}, a_{2},

σ = 3 2  3  1 2  4 5 6  9 1 2 3 4 5 6 7 8 9

Figure 2.1. read(σ) = 3 2 3 1 2 4 5 6 9, content(σ) = {1, 2^{2}, 3^{2}, 4, 5, 6, 9}

and a_{3} are said to form a type A triple, as depicted below.

\begin{matrix}a_{1} \\ a_{3} \end{matrix} ⋯ a_{2}

Define for x, y ∈ ℤ_{+}

I(x, y) = \{ \begin{matrix}1 & if x > y \\ 0 & if x ≤ y \end{matrix} .

Let σ̂ be an augmented filling and let {σ̂(a_{1}), σ̂(a_{2}), σ̂(a_{3})} be the entries of σ̂ in the cells {a_{1}, a_{2}, a_{3}}, respectively, of a type A triple. The triple {a_{1}, a_{2}, a_{3}} is called a type A inversion triple if and only if I(σ̂(a_{1}), σ̂(a_{2})) + I(σ̂(a_{2}), σ̂(a_{3})) − I(σ̂(a_{1}), σ̂(a_{3})) = 1.

Similarly, consider three cells {a_{1} = (i_{1}, j_{1}), a_{2} = (i_{2}, j_{2}), a_{3} = (i_{3}, j_{3})} ∈ λ such that column i_{2} is strictly taller then column i_{1}. The cells {a_{1}, a_{2}, a_{3}} are said to form a type B triple if j_{1} = j_{2}, i_{2} = i_{3}, and j_{3} − j_{2} = 1, as shown below.

a_{1} … \begin{matrix}a_{3} \\ a_{2} \end{matrix}

Let σ̂ be an augmented filling and let {σ̂(a_{1}), σ̂(a_{2}), σ̂(a_{3})} be the entries of σ̂ in the cells {a_{1}, a_{2}, a_{3}} of a type B triple. The triple {a_{1}, a_{2}, a_{3}} is called a type B inversion triple if and only if I(σ̂(a_{3}), σ̂(a_{1})) + I(σ̂(a_{1}), σ̂(a_{2})) − I(σ̂(a_{3}), σ̂(a_{2})) = 1.

Let inv(σ̂) be the number of type A inversion triples plus the number of type B inversion triples. Let coinv(σ̂) be the number of type A or B triples which are not inversion triples. These two statistics appear in the formula for nonsymmetric Macdonald polynomials E_{γ} given by Haglund, Haiman, and Loehr [3]. For our purposes it will be more convenient to work with the integral form nonsymmetric Macdonald polynomials Ê_{γ} studied by Marshall [6], which are related to the E_{γ} via the equation Ê_{γ_{p},...,γ_{1}}(x_{n}, …, x_{1}; 1/q, 1/t) = E_{γ}(x_{1}, x_{2}, …, x_{n}; q, t).

Theorem 2.1 ([3]). The nonsymmetric Macdonald polynomials Ê_{γ} are given by the formula

(2.1)  Ê_{γ}(x; q, t) = ∑_{σ: γ→[n] non-attacking} x^{σ}q^{maj(σ̂)}t^{coinv(σ̂)} ∏_{\begin{matrix}u∈dg′(γ) \\ σ̂(u)≠σ̂(d(u)) \end{matrix}} \frac{1 − t}{1 − q^{l(u)+1}t^{a(u)+1}} ,

where x^{σ} = ∏_{u∈dg′(μ)} x_{σ(u)}.

We are concerned only with the polynomial Ê_{γ}(x; 0, 0), so setting q and t equal to zero produces the polynomial

Ê_{γ}(x; 0, 0) = ∑_{σ: γ→[n] non-attacking} x^{σ}0^{maj(σ̂)}0^{coinv(σ̂)} ∏_{\begin{matrix}u∈dg′(γ) \\ σ̂(u)≠σ̂(d(u)) \end{matrix}} \frac{1 − 0}{1 − 0^{l(u)+1}0^{a(u)+1}}

= ∑_{σ: γ→[n] non-attacking maj(σ̂)=coinv(σ̂)=0} x^{σ}

A non-attacking filling F satisfying maj(F) = coinv(F) = 0 is called a semi-skyline augmented filling, SSAF. In the following section, we provide a simpler definition of a semiskyline augmented filling.

2.2. Semi-skyline augmented fillings. Let F be a semi-skyline augmented filling. The condition maj(F) = 0 implies that

maj(F) = ∑_{a∈Des(F)}(l(a) + 1) = 0.

Since maj(F) is increased by at least 1 for each element in the descent set of F, we must have Des(F) = ∅. The condition coinv(F) = 0 implies that every triple of cells in F must be an inversion triple. Therefore a semi-skyline augmented filling is a non-attacking filling with no descents such that every triple is an inversion triple.

The following two lemmas demonstrate that any filling satisfying these descent and inversion conditions must be a non-attacking filling.

Lemma 2.2. Let F be a descentless augmented filling such that every triple of F is an inversion triple. If the cells a and b are in the same row of F, then F (a) ≠ F (b).

Proof. Suppose a and b are in the same row of F. We may assume that a is to the left of b. Assume first that the column containing a is weakly taller than the column containing b. The cell a is directly on top of some cell c, so {a, b, c} is a type A triple as depicted below.

\begin{matrix}a \\ c \end{matrix} … b

The triple must be a Type A inversion triple, so I(F (a), F (b)) + I(F (b), F (c)) − I(F (a), F (c)) = 1. We know that F contains no descents, so I(F (a), F (c)) = 0. Therefore I(F (a), F (b)) + I(F (b), F (c)) = 1 implies that either F (a) > F (b) and F (b) ≤ F (c) or F (a) ≤ F (b) and F (b) > F (c). If F (a) ≤ F (b), then F (b) > F (c) implies that F (a) < F (b), for otherwise F (a) = F (b) > F (c), which contradicts the fact that F (a) ≤ F (c).

Next suppose that the column containing b is strictly taller than the column containing a. There must be a cell d on top of b such that {a, d, b} is a type B triple as depicted below.

a … \begin{matrix}d \\ b \end{matrix}

There are no descents in F, so F (d) ≤ F (b). Every triple of F is an inversion triple, so I(F (d), F (a))+I(F (a), F (b))−I(F (d), F (b)) = 1 implies that I(F (d), F (a))+I(F (a), F (b))− 0 = 1. We only need to consider the situation in which F (a) ≤ F (b), which implies that I(F (a), F (b)) = 0. This means that I(F (d), F (a)) = 1, so F (a) < F (d). But F (d) ≤ F (b), so F (a) < F (d) ≤ F (b) and therefore F (a) < F (b). So F (a) ≠ F (b). □

Lemma 2.3. Let F be a descentless augmented filling such that every triple of F is an inversion triple. For each pair of cells a and b in F, with a to the left of b in the row immediately below b, we have F (a) ≠ F (b).

Proof. Consider two cells a and b in the augmented filling situated as described. There exists a cell d immediately below b and possibly a cell c immediately above a as depicted below.

\begin{matrix}c \\ a \end{matrix} … \begin{matrix}b \\ d \end{matrix}

If the column containing a is taller than or equal to the column containing b, then a lies directly below the cell c which must have F (c) ≤ F (a). Since the triple {c, b, a} is a type A triple, it must satisfy I(F (c), F (b)) + I(F (b), F (a)) − I(F (c), F (a)) = 1. Since F (c) ≤ F (a), we have I(F (c), F (a)) = 0 and hence I(F (c), F (b)) + I(F (b), F (a)) = 1. We only need to consider the situation in which F (b) ≤ F (a), which implies that I(F (b), F (a)) = 0. In this case, I(F (c), F (b)) = 1, so F (b) < F (c) ≤ F (a). This means that F (a) > F (b) and hence F (a) ≠ F (b).

If the column containing b is strictly taller than the column containing a, the triple {a, b, d} is a type B triple and must satisfy I(F (b), F (a)) + I(F (a), F (d)) − I(F (b), F (d)) = 1. There are no descents in F, so F (b) ≤ F (d), which means that I(F (b), F (d)) = 0. Therefore either I(F (b), F (a)) = 1 or I(F (a), F (d)) = 1. If I(F (b), F (a)) = 1, then F (b) > F (a) and we are done. Assume I(F (b), F (a)) = 0 and I(F (a), F (d)) = 1. This means that F (a) > F (d) ≥ F (b). So F (a) > F (b) and hence F (a) ≠ F (b). □

Corollary 2.4. The descent and inversion conditions used to describe the semi-skyline augmented fillings are enough to guarantee that the filling is non-attacking.

Corollary 2.4 follows immediately from Lemmas 2.2 and 2.3. It allows us to reformulate the combinatorial interpretation of Ê_{γ}(x; 0, 0) as follows.

Definition 2.5. Let γ be a weak composition of n into m parts (where m ∈ ℤ^{+} ∪ {∞}). The polynomial Ê_{γ}(x; 0, 0) in the variables x = (x_{1}, x_{2}, ..., x_{k}) is the formal power series

Ê_{γ}(x; 0, 0) = ∑_{F ∈SSAF (γ)} x^{F} ,

where SSAF (γ) is the set of all descentless fillings of d̂g(γ) in which every triple is an inversion triple.

The combinatorial interpretation of Ê_{(1,0,3,2)}(x; 0, 0) is depicted in Figure 2.2. Notice that the first row of the i^{th} column contains the entry i, since any smaller entry j would attack

3 3 4 1  3 4 1 2 3 4  2 3 4 1  3 4 1 2 3 4  1 3 4 1  3 4 1 2 3 4  3 3 2 1  3 4 1 2 3 4

3 3 4 1 3 4  2 3 4 1 3 4  1 3 4 1 3 4  3 3 2 1 3 4

2 3 2 1  3 4 1 2 3 4  1 3 2 1  3 4 1 2 3 4  2 2 4 1  3 4 1 2 3 4  1 2 4 1  3 4 1 2 3 4

2 3 2 1 3 4  1 3 2 1 3 4  2 2 4 1 3 4  1 2 4 1 3 4

Figure 2.2. All possible SSAFs of shape (1, 0, 3, 2) with the reading word listed below each filling. Ê_{(1,0,3,2)}(x; 0, 0) = x_{1}x_{3}^{3}x_{4}^{2} + x_{1}x_{2}x_{3}^{2}x_{4}^{2} + x_{1}^{2}x_{3}^{2}x_{4}^{2} + x_{1}x_{2}x_{3}^{3}x_{4} + x_{1}x_{2}^{2}x_{3}^{2}x_{4} + x_{1}^{2}x_{2}x_{3}^{2}x_{4} + x_{1}x_{2}^{2}x_{3}x_{4}^{2} + x_{1}^{2}x_{2}x_{3}x_{4}^{2}.

the basement entry j and any larger entry would create a descent. The following lemma characterizes the type B triples in an SSAF.

Lemma 2.6. If {a, b, c} is a type B triple in a semi-skyline augmented filling F with a and c in the same row and b directly above c, then F (a) < F (c).

Proof. Let {a, b, c} be a type B triple situated as described:

a … \begin{matrix}b \\ c \end{matrix}

Lemma 2.2 implies that F (a) ≠ F (c). If F (a) > F (c), then consider the cells e and g immediately below a and c as shown.

\begin{matrix}a \\ e \end{matrix} … \begin{matrix}c \\ g \end{matrix}

The descent condition implies that F (a) ≤ F (e), which means that I(F (c), F (e)) = 0, since F (c) < F (a) ≤ F (e). Lemma 2.3 therefore implies that F (c) < F (e). Since {e, c, g} form a type B inversion triple, we must have I(F (c), F (e)) + I(F (e), F (g)) − I(F (c), F (g)) = 1. Therefore 0+I(F (e), F (g))−I(F (c), F (g)) = 1 implies that I(F (e), F (g)) = 1. By definition this means that F (e) > F (g). We now have the same situation as above, but one row lower in the diagram. Repeating the argument eventually implies that the basement entry in the column containing a is greater than the basement entry in the column containing b, a contradiction. Therefore F (a) < F (c). □

Given any type B triple {a, b, c} as described in Lemma 2.6, the descent condition implies that F (b) ≤ F (c). If F (a) ≥ F (b), then Lemma 2.6 and the fact that the filling is nonattacking implies that F (b) < F (a) < F (c). This means that I(F (b), F (a))+I(F (a), F (c))− I(F (b), F (c)) = 0 + 0 − 0 = 0, so {b, a, c} is a type B non-inversion triple. Thus F (a) < F (b) ≤ F (c). Therefore Lemma 2.6 completely characterizes the relative values of the cells in a type B inversion triple.

Lemma 2.7. Consider two cells a_{1} = (i_{1}, j_{1}) and a_{2} = (i_{2}, j_{2}) in an augmented diagram d̂g(γ) such that i_{2} = i_{1} − 1 and j_{2} < j_{1}. Let a_{3} = (i_{3}, j_{3}) be the cell directly on top of a_{2}. (Then j_{3} = j_{2} + 1 and i_{3} = i_{2}.) If F is a semi-skyline augmented filling and F (a_{1}) ≤ F (a_{2}), then F (a_{3}) > F (a_{1}).

Proof. The cells a_{1}, a_{2}, a_{3} form a type A triple. The filling F must not contain any descents, so F (a_{3}) ≤ F (a_{2}). If F (a_{3}) ≤ F (a_{1}), then I(F (a_{3}), F (a_{1}))+I(F (a_{1}), F (a_{2}))−I(F (a_{3}), F (a_{2})) = 0 + 0 − 0 = 0 ≠ 1. However, if F (a_{3}) > F (a_{1}), then I(F (a_{3}), F (a_{1})) + I(F (a_{1}), F (a_{2})) − I(F (a_{3}), F (a_{2})) = 1 + 0 − 0 = 1, as required. Therefore F (a_{3}) > F (a_{1}). □

Lemmas 2.2, 2.3, 2.6, and 2.7 provide several conditions on the cells in a semi-skyline augmented filling. These conditions are used to describe the bijection between semi-standard Young tableaux and semi-skyline augmented fillings and to prove Theorem 1.1.

3. Two equivalent bijections between SSAFs and SSYTs

Recall that we seek a weight-preserving bijection between semi-standard Young tableaux of shape λ and semi-skyline augmented fillings whose shape rearranges λ. Such a bijection provides the first combinatorial proof that

(3.1)  ∑_{γ∼λ} Ê_{γ}(x; 0, 0) = s_{λ}(x),

where the sum is over all infinite weak compositions γ which rearrange λ, denoted γ ∼ λ. Set x_{i} = 0 for i > n to obtain the equation

∑_{γ∼λ} Ê_{γ}(x_{1}, x_{2}, …, x_{n}; 0, 0) = s_{λ}(x_{1}, x_{2}, …, x_{n}).

3.1. A weight-preserving bijection between SSAFs and reverse SSYTs. Assume that F is a semi-skyline augmented filling of a weak composition γ of n into infinitely many parts whose largest part is equal to m. Let R_{i} be the set of entries in the i^{th} row of F. The collection {R_{i}}_{i∈[m]} of all sets of row entries is called the row set of F.

Recall that a reverse semi-standard Young tableau is a filling of a partition shape with positive integer values whose entries are strictly decreasing along rows and weakly decreasing along columns, where the rows are read from left to right and the columns are read from bottom to top. We construct a reverse semi-standard Young tableau ρ(F) by placing the entries from the set R_{i} into the i^{th} row of ρ(F) in decreasing order from left to right. (See

F 3 4 2  4 1  3  5 1 2 3 4 5  ρ  3 4 4 2 5 3 1 ρ(F)

Figure 3.1. The map ρ(F)

Figure 3.1.) The entries in R_{i} are distinct since F is a non-attacking filling. Therefore the row entries of ρ(F) are strictly decreasing.

To see that the column entries of ρ(F) are weakly decreasing, notice that any element in R_{i} lies immediately above an element of R_{i−1} in F. No descents occur in F, so the k^{th} largest element, α, in R_{i} must be less than or equal to at least k of the elements in R_{i−1}. The entry α appears in ρ(F) immediately on top of the k^{th} largest element, β, of R_{i−1}. At least k elements in R_{i−1} are greater than or equal to α, so β ≥ α. Therefore the column entries of ρ(F) are weakly decreasing and ρ(F) is indeed a reverse semi-standard Young tableau.

The inverse of the map ρ sends a reverse semi-standard Young tableau P to a semi-skyline augmented filling ρ^{−1}(P) as follows. Assume that the first i rows of P, denoted {P_{1}, P_{2}, … P_{i}} have been mapped to a semi-skyline augmented filling. Consider the largest element, α_{1}, in the (i + 1)^{th} row P_{i+1}. There exists an element greater than or equal to α_{1} in the i^{th} row of the SSAF since α_{1} is immediately above such an element in P. Place α_{1} on top of the leftmost such element.

Assume that the largest k − 1 entries in P_{i+1} have been placed into the SSAF. The k^{th} largest element, α_{k}, of R_{i+1} is then placed into the SSAF. There are at least k elements of P_{i} which are greater than or equal to α_{k}, so at most k − 1 of these are already directly beneath an element of P_{i+1}. Place α_{k} on top of the leftmost entry β in row k−1 such that β ≥ α_{k} and the cell immediately above β is empty. Again, such a β exists since the number of entries in row P_{i+1} which are greater than or equal to α_{k} is less than or equal to the number of entries in row P_{i} which are greater than or equal to α_{k}. Continue this procedure until all entries in P_{i+1} have been mapped into the (i + 1)^{th} row and then repeat for the remaining rows of P to obtain the semi-skyline augmented filling ρ^{−1}(P). (See Figure 3.2.)

We must prove that ρ^{−1}(P) is a semi-skyline augmented filling, and that this is the only SSAF with row entries {P_{i}}.

Lemma 3.1. The filling ρ^{−1}(P) = F′ is a semi-skyline augmented filling.

Proof. By construction, the filling has no descents. Therefore, we must show that all triples are inversion triples. First consider a type A triple of cells, {a, b, c} where a and b are cells in the i^{th} row and c is the cell immediately below a as depicted below.

\begin{matrix}a \\ c \end{matrix} … b

8 12 13 11 8 14 13 10 8 14 13 11 8 6 P  ρ^{−1}  8 12 8  13 11 8  10 13 14 6  8  11 13 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Figure 3.2. The map ρ^{−1}(P)

The column containing a and c lies to the left of the column containing b and therefore must be weakly taller than the column containing b.

The filling is constructed in such a way that F′(a) ≤ F′(c). Therefore I(F′(a), F′(c)) = 0. We want to show 1 = I(F′(a), F′(b)) + I(F′(b), F′(c)) − I(F′(a), F′(c)) = I(F′(a), F′(b)) + I(F′(b), F′(c)) − 0. If I(F′(a), F′(b)) = 0, then F′(a) < F′(b), since a and b are in the same row of F′. Since F′(b) > F′(a), the entry F′(b) was inserted into F′ before the entry F′(a). Since F′(b) was not placed on top of c, the entry F′(c) must be less than F′(b). Therefore I(F′(b), F′(c)) = 1. So I(F′(a), F′(b)) + I(F′(b), F′(c)) − I(F′(a), F′(c)) = 0 + 1 − 0 = 1 and {a, b, c} is a type A inversion triple.

If I(F′(a), F′(b)) = 1, then F′(a) > F′(b). This implies that F′(b) < F′(c), since F′(a) ≤ F′(c). So I(F′(a), F′(b)) + I(F′(b), F′(c)) − I(F′(a), F′(c)) = 1 + 0 − 0 = 1. So every type A triple in F′ is a type A inversion triple.

Next consider a type B triple {a, b, c} such that a and b are in the i^{th} row and a is to the left of b as shown below.

a … \begin{matrix}c \\ b \end{matrix}

Let c be the cell immediately on top of b. Then the column containing b and c is strictly taller than the column containing a. We have the equation I(F′(c), F′(a))+I(F′(a), F′(b))− I(F′(c), F′(b)) = I(F′(c), F′(a)) + I(F′(a), F′(b)) − 0 since F′(c) ≤ F′(b).

If I(F′(a), F′(b)) = 1, then F′(a) > F′(b). Since F′(c) was not placed on top of F′(a), there must be an entry F′(d) greater than F′(c) which was already on top of F′(a) when F′(c) was inserted. If this is the case, then the same situation occurs in row i + 1. Repeat this argument until a row r is reached such that the column containing b and c contains an entry α in row r but the column containing a does not. (Such a row must exist since the triple is a type B triple.) Then the entry α would have been placed on the column containing a, which is a contradiction. Therefore I(F′(a), F′(b)) = 0.

Since I(F′(a), F′(b)) = 0 implies F′(a) ≤ F′(b) and the row entries of P are distinct, we have F′(a) < F′(b). Since F′(c) was not placed on top of F′(a), either F′(c) > F′(a) or there was already an entry larger than F′(c) on top of a. If there was already an entry on top of a, then the situation is precisely the situation described in the previous paragraph, shifted one row higher. Therefore F′(c) > F′(a) and I(F′(c), F′(a)) + I(F′(a), F′(b)) − I(F′(c), F′(b)) = 1 + 0 − 0 = 1 and hence {a, b, c} is a type B inversion triple. □

Lemma 3.2. The SSAF ρ^{−1}(P) is the only SSAF with row entries {P_{i}}.

Proof. Let K be an arbitrary SSAF whose row entries are given by the collection {P_{i}}. Find the lowest row r of K whose entries appear in a different order from their appearance in row r of ρ^{−1}(P) = F′. Consider the largest element, δ, of P_{r} whose position in K does not agree with its position in F′. Then δ was placed in the cell on top of the left-most possible cell a in F′ such that α = F′(a) ≥ δ. Therefore in K the entry δ must reside in a cell c of a column strictly to the right of the column containing a in K. The situation is depicted below, where b is the cell immediately below the cell c containing δ = K(c) in K and the entry δ is shown as the entry in its cell.

K  F′ row r − 1 row r  ^{a … \begin{matrix}δ \\ b \end{matrix}}  ^{\begin{matrix}δ \\ a \end{matrix} … b}

If the column containing δ and the cell b is strictly taller than the column containing the cell a in K, then the triple {a, b, c} is a type B triple. We have I(δ, K(a)) + I(K(a), K(b)) − I(δ, K(b)) = 0 + I(K(a), K(b)) − 0. We know that K(a) < K(b) by Lemma 2.6. So I(K(a), K(b)) must equal 0 and hence {a, b, c} is not a type B inversion triple.

If the column containing a is weakly taller in K than the column containing b and c, then the cell d immediately on top of a in K contains an entry K(d) which is less than δ. (If it were greater than δ, this would contradict the assumption that δ is the greatest value for which the row placement differs.) In particular, K(d) < δ = K(c) implies that I(K(d), K(c)) + I(K(c), K(a)) − I(K(d), K(a)) = 0 + 0 − 0 = 0. So the triple {d, c, a} is a type A triple that is not a type A inversion triple.

Therefore, regardless of which column is taller, K contains at least one non-inversion triple. So K is not a semi-skyline augmented filling. □

The above implies that the map ρ^{−1} sends a reverse semi-standard Young tableau P to the only possible semi-skyline augmented filling whose row entries are the same as the row entries of P. In fact, let {R_{i}}_{j} be any collection of sets of positive integers such that the number of entries in R_{i} which are greater than or equal to α is great than or equal to the number of entries in R_{i+1} which are greater than or equal to α, for all i ≥ 1 and all positive integers α. Any set with this property could be the set of row entries for a reverse semistandard Young tableau. So applying the map ρ produces a semi-skyline augmented filling, the only semi-skyline augmented filling with row entries {R_{i}}_{j}.

3.2. An analogue of Schensted insertion. Schensted insertion is a procedure for inserting a positive integer k into a semi-standard Young tableau T. It is the fundamental operation of the Robinson–Schensted–Knuth (RSK) algorithm. We define a procedure for inserting a positive integer k into a semi-skyline augmented filling F using a similar “scanning and bumping” technique. In Section 4 we use this procedure to describe an analogue of the RSK algorithm.

Let F be a semi-skyline augmented filling of a weak composition γ of n into m parts. Then F = (F (j)), where F (j) is the entry in the j^{th} cell in reading order. (Here we include the cells in the basement, so j goes from 1 to n + m.) Let ĵ be the cell immediately above j. If the cell is empty, set F (ĵ) = 0. We define the operation k → F, for k ≤ m.

Procedure 3.3. The insertion k → F:

P1. Set i := 1, set x_{1} := k, set p_{0} = ∅, and set j := 1.

P2. If F (j) < x_{i} or F (ĵ) ≥ x_{i}, then increase j by 1 and repeat this step. Otherwise, set x_{i+1} := F (ĵ) and set F (ĵ) := x_{i}. Set p_{i} = (a, b + 1), where (a, b) is the j^{th} cell in reading order. (This means that the entry x_{i} ‘bumps’ the entry x_{i+1} from the cell p_{i}.)

P3. If x_{i+1} ≠ 0 then increase i by 1, increase j by 1, and repeat step P2.

P4. Set t_{k} equal to p_{i} and terminate the algorithm.

Notice that this procedure produces a sequence I_{k} = (x_{1}, x_{2}, …, x_{r}) of entries which are affected by the insertion of k, called the insertion sequence. The sequence P_{k} = (p_{1}, p_{2}, …, p_{r}) records which cells are affected by the insertion of k, with t_{k} (the termination cell) denoting the new cell created at the termination of the insertion. This sequence is called the insertion path of k.

Lemma 3.4. Let x_{i} be an entry in I_{k} and let α_{i} be the first occurrence in F of the value x_{i} after p_{i−1} in reading order. Then x_{i} is inserted into a row above α_{i} by the procedure k → F.

Proof. Let s be the cell containing α_{i} in F and let a be the cell immediately above s. The entry x_{i} must appear before a in the reading order of F since F is a non-attacking filling. (If x_{i} is x_{1}, we think of x_{i} as appearing before all letters of F in reading order.) The entry in a must be less than x_{i} by the choice of α_{i}. Therefore if x_{i} reaches a during the insertion of k, then x_{i} will replace the entry in a. So x_{i} appears in a row above α_{i}. □

Lemma 3.4 implies that each entry x_{i} is inserted into a row of F which is higher than the next row containing an entry equal in value to x_{i}. In particular, this means each entry appears in k → F above the basement entry of equal value, since every value appears in the basement. Therefore the procedure k → F terminates in finitely many steps. (See Figure 3.3 for an example.) To see that the resulting figure is indeed a semi-skyline augmented filling, we need the following lemma.

Lemma 3.5. The set of entries in a given row of the figure k → F is equal to the set of entries in the corresponding row of the figure (ρ(F) ← k).

Proof. To prove this, we determine which entry of F is bumped to a lower row of F during (k → F) and show that this is the same entry bumped to a lower row of ρ(F) during (ρ(F) ← k).

If R_{i} is the collection of row entries appearing in row i of F, let \overline{R}_{i} = R_{i} ∪ x_{j}, where x_{j} is the last entry bumped from a row higher than row i. Let |\overline{R}_{i}^{≥u}| be the number of entries

F 3 4 2 1  4 5 1 2 3 4 5 6 7 4 → I_{k} = (4)  4 4 2 1  4 5 1 2 3 4 5 6 7 3 → I_{k} = (4, 3) P_{k} = ((4, 3))  4 4 3 1  4 5 1 2 3 4 5 6 7 2 → I_{k} = (4, 3, 2) P_{k} = ((4, 3), (5, 2))  4 4 3 1 2 4 5 1 2 3 4 5 6 7 4 → F I_{k} = (4, 3, 2) P_{k} = ((4, 3), (5, 2), (2, 1)) t_{k} = (2, 1)

Figure 3.3. The insertion 4 → F

in \overline{R}_{i} which are greater than or equal to u. Similarly, let |R_{i−1}^{≥u}| be the number of entries in row i − 1 of F which are greater than or equal to u. We claim that if v is the largest entry in row i such that |\overline{R}_{i}^{≥v}| > |R_{i−1}^{≥v}|, then v is the entry in row i which is bumped down to row i − 1. If no such v exists, then no entry is bumped to row i − 1 and the insertion procedure is terminated at row i.

To see this, let v be the largest entry in \overline{R}_{i} such that |\overline{R}_{i}^{≥v}| > |R_{i−1}^{≥v}|. If no such v exists, then the m^{th} largest entry in \overline{R}_{i} is less than or equal to m entries in row i−1, for all m. This means that each entry in \overline{R}_{i} can be inserted into row i, and so the procedure terminates at row i, as predicted by the claim.

Assume next that such a v exists. Since F is an SSAF, the pigeonhole principle implies that |R_{i}^{≥u}| ≤ |R_{i−1}^{≥u}| for all u in row i. Therefore the largest v which satisfies |\overline{R}_{i}^{≥v}| > |R_{i−1}^{≥v}| must be less than or equal to x_{j}. If v = x_{j}, then all the entries greater than or equal to x_{j} in row i − 1 are immediately below entries greater than x_{j} and therefore x_{j} is bumped down to the following row, as claimed.

If v < x_{j}, then there exists an entry in row i − 1 of F which is greater than or equal to x_{j} but lies immediately beneath an entry, α, less than x_{j}. During the insertion, x_{j} bumps the leftmost such α. Note that α must be greater than or equal to v since all the entries greater than or equal to v in row i − 1 must lie beneath entries greater than or equal to v. If α = v, then all the entries greater than or equal to α in row i − 1 lie immediately beneath entries greater than or equal to α, so α is bumped to the next row as claimed. If α > v, there exists an entry smaller than α that sits on top of an entry greater than or equal to α. By the construction of F, this entry is to the right of α, so α will bump this entry. Again, since all entries greater than or equal to v in row i − 1 lie below entries greater than or equal to v, this entry is greater than or equal to v. The same argument as above shows that either this bumped entry is v or this entry bumps another entry in row i. Therefore, the entry v is eventually bumped. Since all the entries greater than or equal to v in row i − 1 lie below entries greater than or equal to v, the entry v cannot bump anything in row i. Therefore v is the entry bumped to the next row down, as claimed.

Now consider the insertion ρ(F) ← k. This insertion procedure scans columns rather than rows, but the insertion path moves weakly south as it progresses through the columns from left to right. To see this, consider an entry α bumped from row i of ρ(F). Then α will be inserted into the column directly to its right on top of an entry weakly greater than α. The entry immediately to the right of α is strictly less than α, so α cannot be inserted on top of this entry or at any higher row. Therefore α is inserted into a row weakly lower than the row from which it is bumped.

If α is bumped to a row lower than row i, this means that the set of entries in row i − 1 which are greater than or equal to α has cardinality less than the cardinality of the set containing α and the entries in row i which are greater than or equal to α. Therefore an entry α is bumped to a lower row if α is the greatest entry in row i such that |\overline{R}_{i}^{≥α}| > |R_{i−1}^{≥α}|, which is the same condition under which an entry is bumped to a lower row during k → F. Therefore the set of entries in a given row of the figure k → F is equal to the set of entries in the corresponding row of the figure (ρ(F) ← k). □

Proposition 3.1. If F is a semi-skyline augmented filling and k is an arbitrary positive integer, then the figure k → F is a semi-skyline augmented filling. In particular, the insertion procedure commutes with the map ρ in the sense that

ρ(k → F) = (ρ(F) ← k),

where ρ(F) ← k is the reverse Schensted insertion of k into ρ(F).

Proof. Lemma 3.5 states that the row entries of k → F are the same as those of (ρ(F) ← k). The semi-skyline augmented filling ρ^{−1}(ρ(F) ← k) is the only semi-skyline augmented filling with these row entries by Lemma 3.2, so we must prove that ρ^{−1}(ρ(F) ← k) and k → F are the same semi-skyline augmented filling. In other words, we must show that the row entries of k → F appear in the same positions as in ρ^{−1}(ρ(F) ← k).

To see this, we prove that every triple in k → F is an inversion triple. Consider first a type A triple in k → F, as depicted below.

\begin{matrix}a \\ c \end{matrix}  b

Let α, β, γ be the entries contained in the cells a, b, c respectively. This triple is a noninversion triple if α < β ≤ γ. The cell a cannot be the termination cell for k → F. (If it were, then c and b would violate Lemma 2.6 in F.) If b were the termination cell, then β must have been bumped from a cell to the right of a for otherwise β would have bumped α. If the column containing β before β was bumped were taller than the column containing a, then c, the cell containing β, and the cell below β would form a type B non-inversion triple in F. Otherwise it must be that a, c, and the cell containing β would form a type A non-inversion triple in F. Since all triples in F are inversion triples, this is a contradiction. Therefore a type A non-inversion triple in k → F can only appear if some of the cells in the triple were bumped by the insertion.

The entries in the cells of the triple are weakly increasing in reading order, so at most one of these entries is affected by the insertion procedure. If α bumped a smaller entry, then the cells a, b, and c would form a type A non-inversion triple in F. The entry β could not have bumped an entry from the cell b for the same reason that it cannot be the termination cell. Therefore the only cell in this triple that could be affected by the insertion procedure is c. If γ bumped a smaller entry, κ, from the cell c, then κ < β, for otherwise a, b, c would be a type A non-inversion triple in F.

This implies that the entry κ must be smaller than the entry δ in the cell d directly below b, and so the entry ϵ in the cell e directly below c must be smaller than the entry δ, for otherwise the cells c, d, e form a type A non-inversion triple in F. But then if γ appeared before β in reading order, γ would have bumped β. So γ was bumped from a cell after b in reading order. If γ appeared on the same row of F as b, the cell containing γ would form an inversion triple with either b and d or d and the cell immediately below γ in F, depending on the column heights. Therefore γ must have been bumped from a cell on the same row as c. Lemma 2.6 implies that the column containing γ in F must be shorter than the column containing a, since γ > α. The entry above γ must therefore be greater than β so that these two cells together with the cell b form a type A inversion triple in F. This means that γ must be bumped by an entry greater than β. Repeating the above argument implies that the entry which bumps γ must come from the same row as γ, and continued repetition implies that every entry in the insertion must be bumped from the same row as γ, which contradicts the fact that the insertion algorithm begins at the highest cell in the diagram. Therefore this situation cannot happen and every type A triple is an inversion triple.

Next consider a type B triple in k → F, as depicted below.

a  \begin{matrix}c \\ b \end{matrix}

Let α, β, γ be the entries contained in the cells a, b, c respectively. This triple is a noninversion triple if γ ≤ α < β. The cell c cannot be the termination cell for k → F. To see this, notice that if c were the termination cell, then γ was bumped from a cell to the right of the column containing a. (Otherwise γ would be placed on top of a.) But if γ appears to the right of a in F, then the cell containing γ, the cell beneath it, and the cell a form a type B non-inversion triple in F.

If the insertion algorithm terminates at the cell a, then the entry α must have been bumped from a cell after c in reading order. If α were in the same row of F as c, then Lemma 2.6 implies that the column containing α is weakly shorter than the column containing c and b, since α ≤ β. But then c, b, and the cell containing α form a type A non-inversion triple. If α were in the same row of F as b, then c, b, and the cell containing α in F would constitute a type B non-inversion triple unless the column containing α were weakly taller in F than the column containing b and c. In this case, the entry which bumps α must be less than β since it must be inserted on top of an entry that is greater than β. (The entry below α in F is greater than β since these two cells together with b form a type A inversion triple in F.)

Then we are in the same situation as before and can repeat the argument indefinitely to show that no entry is bumped from the row above a, which contradicts the fact that the insertion algorithm begins at the first cell in reading order. Therefore a type B non-inversion triple in k → F can only appear if some of the cells in the triple were bumped by the insertion.

The entries in the cells of the triple are weakly decreasing in reading order, so at most one of these entries is affected by the insertion procedure. If γ bumped a smaller entry from the cell c, then this entry would be less than α and Lemma 2.6 implies that the triple a, b, c would be a type B non-inversion triple in F. If α bumps an entry from the cell a, then α must be bumped from a cell after c in reading order, for otherwise α would bump γ. If the entry α is bumped from the row containing c, then the column containing α in F must be weakly shorter than the column containing c and b since α > β. But then the cell containing α together with c and b form a type A non-inversion triple. Therefore α must be bumped from the row containing a. Lemma 2.6 implies that the column containing α in F must be taller than or equal in height to the column containing c, since γ ≤ α. The entry above α must therefore be greater than γ so that these two cells together with the cell c form a type A inversion triple in F. This means that α must be bumped by an entry greater than or equal to γ. Repeating the above argument implies that the entry which bumps α must come from the same row as α, and continued repetition implies that every entry in the insertion must be bumped from the same row as α, which contradicts the fact that the insertion algorithm begins at the highest cell in the diagram. Therefore the entry α could not have bumped a smaller entry from the cell a. The entry β could not have bumped a smaller entry from the cell b, for if so then a, b, c would be a type B non-inversion triple in F by Lemma 2.6. Therefore this situation cannot happen and every type B triple is an inversion triple. □

The insertion procedure k → F is closely connected to Schensted insertion. Let reverse Schensted insertion be the variation of Schensted insertion which maps a positive integer k into a reverse semi-standard Young tableau [8]. This is equivalent to altering the Schensted insertion procedure described by Knuth [4] by reversing the directions of the inequalities, and scanning columns rather than rows.

3.3. The bijection Ψ between SSYT and SSAF. Let T be a semi-standard Young tableau. We may associate to T the word col(T), which consists of the entries from each column of T, read top to bottom from columns left to right, as in Figure 3.4. In general, any word w can be decomposed into its maximal strictly decreasing subwords, called column words. This decomposition is called col(w). For example, if w = 3 5 4 2 2 1, then col(w) = 3 · 5 4 2 · 2 1.

Begin with an arbitrary SSYT T and the empty SSAF ϕ whose basement row contains all the letters of ℤ_{+}. Let k be the rightmost letter in col(T). Insert k into ϕ to obtain the SSAF (k → ϕ). Then let k′ be the next letter in col(T) reading right to left. Obtain the SSAF (k′ → (k → ϕ)). Continue in this manner until all the letters of col(T) have been inserted. The resulting diagram is the SSAF Ψ(T). (See Figure 3.5.)

Lemma 3.5 implies that that the entries in the rows of Ψ(T) are precisely the entries in the rows of the reverse SSYT P obtained by applying reverse Schensted insertion to col(T).

10

9 11
8 10 10
4 7 8 2 5 5
1 2 3 5 10

Figure 3.4. Here col(T) = 10 9 8 4 2 1 · 11 10 7 5 2 · 10 8 5 3 · 5 · 10

The shape of P is equal to the transpose of the shape of T ([4], [7]). This implies that the shape of Ψ(T) is a rearrangement of the shape of T.

The map Ψ is therefore a weight-preserving map from semi-standard Young tableaux of shape λ to semi-skyline augmented fillings whose shape rearranges λ. We now show that Ψ is a bijection.

Note that Ψ is invertible, since reverse Schensted insertion is an invertible procedure and Ψ commutes with reverse Schensted insertion by Proposition 3.1. To describe the inverse directly, consider an arbitrary SSAF F. Consider the set S of nonzero columns of F. (In Figure 3.5, S contains the third, fifth, seventh, eighth, tenth, and eleventh columns.) The highest cell in each of these columns is a cell which was created during the reverse Schensted insertion of the leftmost column of col(T), since the SSAF produced by the insertion of all columns except the leftmost column has the shape of the diagram of T with the leftmost column omitted. Pick the shortest such column, C_{1}, where if two columns have equal height then the column farther to the right is considered to be shorter.

The cell c_{1} at the top of column C_{1} of F is the cell at which the insertion of the leftmost letter of col(T) terminates. Delete F (c_{1}) and scan the reading word in reverse order to determine which entry (if any) bumped the entry F (c_{1}). (Any entry, β, greater than F (c_{1}) beneath an entry less than F (c_{1}) would have bumped F (c_{1}).) If such an entry is found, replace it with F (c_{1}) and then scan the reading word in reverse order beginning at that

10 9 11 8 10 10 4 7 8 2 5 5 1 2 3 5 10 T  Ψ  4 10 2  5  1 10 2  5  8 10 9 3  5  7 8 10 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 F

Figure 3.5. The map Ψ : T → F takes a SSYT T to an SSAF F.

4 9

2  5  1 10
2  5  8 10 7
3  5  8 10 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
F

Figure 3.6. The SSAF obtained by removing the 7 in the seventh column of F.

position to determine the previous bumping entry and replace it with the entry which bumped F (c_{1}). Continue until the first letter of the reading word is reached. The last bumping entry is therefore the first entry of col(T).

For example, in Figure 3.5, the entry 7 in the seventh column was the last to be placed into F. It was bumped by the 9 in the eleventh column, which was bumped by the 10 in the fourth row of the tenth column. This 10 was not bumped from any other position, so the 10 is the first letter in the word col(T). Removing the 7 in this manner produces the SSAF pictured in Figure 3.6.

Repeat this procedure using the resulting SSAF for the second smallest column C_{2} in S to obtain the second letter of col(T). Continue in this manner until the highest cell in each of the columns in S has been removed. At this point the first column of T has been recovered. Then repeat the entire procedure with the new SSAF, whose nonzero columns are each one cell shorter than the nonzero columns in the original SSAF. Continue this procedure until there are no columns remaining. The resulting word is col(T).

The map Ψ : SSY T → SSAF is a weight-preserving, shape-rearranging bijection. This proves combinatorially that

s_{λ}(x) = ∑_{γ^{+}=λ} Ê_{γ}(x; 0, 0),

since the left-hand side consists of all monomials x^{T} where T is a semi-standard Young tableau of shape λ while the right-hand side consists of all monomials x^{F} where F is a semi-skyline augmented filling of shape γ, where γ^{+} = λ.

3.4. A basis for ℚ[x]. Let γ be a weak composition of n into m parts, where m ∈ ℤ^{+} ∪ {∞}. The monomial corresponding to the composition γ is x^{γ} = ∏_{i=1}^{m} x_{i}^{γ_{i}}. The monomials corresponding to compositions with infinitely many parts form a ℚ-basis for ℚ[x], where x = {x_{1}, x_{2}, …}.

Recall that the reverse dominance order on weak compositions γ and μ is given by

μ ≤ γ if and only if ∑_{i=k}^{∞} μ_{i} ≤ ∑_{i=k}^{∞} γ_{i}, ∀k ≥ 1.

Let NK_{γ,μ} be the coefficient of x^{μ} in Ê_{γ}(x; 0, 0). Then NK_{γ,μ} is equal to the number of semi-skyline augmented fillings of shape γ and content μ. The bijection presented in Section 3.3 implies that

K_{λ,μ} = ∑_{γ^{+}=λ} NK_{γ,μ},

where K_{λ,μ} is the Kostka number, equal to the number of SSYT of shape λ and weight μ.

Proposition 3.2. Suppose that γ and μ are both weak compositions of n into k parts and NK_{γ,μ} ≠ 0. Then μ ≤ γ in the reverse dominance order. Moreover, NK_{γ,γ} = 1.

Proof. Assume that NK_{γ,μ} ≠ 0. By definition, this means that there exists a semi-skyline augmented filling of shape γ and content μ. Suppose that an entry m appears in one of the first m − 1 columns. Then this column contains a descent, since the basement entry of this column is less than m. Therefore all entries greater than or equal to m must appear after the (m − 1)^{th} column. So ∑_{i=m}^{∞} μ_{i} ≤ ∑_{i=m}^{∞} γ_{i} for each m, as desired.

Moreover if μ = γ, then the entries in the i^{th} column must all be equal to i. To see that this augmented filling is a semi-skyline augmented filling, consider first a type A triple as shown.

\begin{matrix}α \\ α \end{matrix} … δ

Here δ > α, so I(α, δ) + I(δ, α) − I(α, α) = 0 + 1 − 0 = 1 implies that the triple is indeed a type A inversion triple.

Next consider a type B triple as shown below.

α … \begin{matrix}β \\ β \end{matrix}

Since α < β, we have I(β, α) + I(α, β) − I(β, β) = 1 + 0 − 0 = 1. Therefore the triple is indeed a type B inversion triple.

Since all triples are inversion triples and there are no descents, the filling is a semi-skyline augmented filling. It is the only SSAF of shape γ and content γ, so NK_{γ,γ} = 1. □

Corollary 3.6. The polynomials Ê_{γ}(x; 0, 0) are a ℚ-basis for ℚ[x].

Proof. Proposition 3.2 is equivalent to the assertion that the transition matrix from the polynomials Ê_{γ}(x; 0, 0) to the monomials (with respect to the reverse dominance order) is upper triangular with 1’s on the main diagonal. Since this matrix is invertible, the Ê_{γ}(x; 0, 0) are a basis for all polynomials. □

Notice that restriction to compositions of n into m parts implies that the Ê_{γ}(x; 0, 0) form a basis for polynomials of degree n in m variables.

4. An analogue of the Robinson–Schensted–Knuth Algorithm

The insertion procedure utilized in the above bijection is an analogue of Schensted insertion, the fundamental operation of the Robinson–Schensted–Knuth (RSK) Algorithm.

Theorem 4.1 (Robinson–Schensted–Knuth [7]). There exists a bijection between ℕmatrices of finite support and pairs of semi-standard Young tableaux of the same shape.

We apply the same procedure to arrive at an analogue of the RSK Algorithm for semiskyline augmented fillings. Recall that Theorem 1.1 states that there exists a bijection between ℕ-matrices of finite support and pairs of semi-skyline augmented fillings whose shapes are rearrangements of the same partition. Composing the RSK algorithm with the bijection Φ between semi-standard Young tableaux and semi-skyline augmented fillings proves Theorem 1.1. We now provide a direct bijection that commutes with this composition.

4.1. The map Φ : ℕ-matrices ⟶ SSAF × SSAF. Let A = (a_{i,j}) be an ℕ-matrix with finite support. There exists a unique two-line array corresponding to A which is defined by the non-zero entries in A. Let a_{i,j} be the first non-zero entry encountered when scanning the entries of A from left to right, top to bottom. Place an i in the top line and a j in the bottom line a_{i,j} times. When this has been done for each non-zero entry, one obtains the following array.

w_{A} = ( \begin{matrix}i_{1} & i_{2} & ... \\ j_{1} & j_{2} & ... \end{matrix} )

Notice that if i_{r} = i_{r+1}, then j_{r} ≤ j_{r+1} in w_{A}. Every two-line array with this property can be obtained from a matrix with finite support. We may therefore consider two-line arrays with this property instead of matrices of finite support.

Procedure 4.2. The map Φ : w_{A} ⟶ SSAF × SSAF:

P1. Set r := l, where l is the length of w_{A}. Let F = ϕ = G, where ϕ is the empty SSAF. P2. Set F := (j_{r} → F). Let h_{r} be the height of the column in (j_{r} → F) at which the

insertion procedure (j_{r} → F) terminates.

P3. Place i_{r} on top of the leftmost column of height h_{r} − 1 in G such that doing so does not create a descent. Set G equal to the resulting figure.

P4. If r − 1 ≠ 0, repeat step P2 for r := r − 1. Else terminate the algorithm.

Notice that the entries in the top row of the array are weakly increasing when read from left to right. This means that if h_{r} > 1, placing i_{r} on top of the leftmost column of height h_{r} − 1 in G does not create a descent. If h_{r} = 1, we claim that the i_{r}^{th} column of G does not contain an entry from a previous step. To see this, argue by contradiction. Assume there exists an entry i_{m} in the i_{r}^{th} column, where m > r. Then the entries j_{m}, j_{m−1}, … j_{r} of the array w_{A} form a weakly decreasing sequence by the nature of the array. The properties of the reverse Schensted insertion of j_{r} imply that the termination of the insertion of j_{r} into F must occur in a higher row of F than the termination of the insertion of j_{m}. This contradicts the assumption that i_{r} and i_{m} are inserted into columns of the same height.

\begin{aligned}5 3 6 1 2 1 4 3 & 1 2 2 3 3 4 4 5 & ρ & 1 3 2  5 1  3 4  6 1 2 3 4 5 6 & F & 3 2  4 3 1 2  4 5 1 2 3 4 5 6 & G \\ & Figure 4.1. Φ : A → SSAF × SSAF \end{aligned}

In this way the shape of G becomes a rearrangement of the shape of F. When the process is complete, the result is a pair (F, G) = Φ(A) of fillings whose shapes are rearrangements of the same partition (see Figure 4.1). To see that F and G are indeed semi-skyline augmented fillings, we prove that the map Φ produces precisely the pair of SSAFs obtained by applying the reverse RSK algorithm to A followed by the map ρ^{−1}.

Proposition 4.1. If (P, Q) is the pair of reverse semi-standard Young tableaux obtained by applying the reverse RSK algorithm to the matrix A, then (ρ^{−1}(P), ρ^{−1}(Q)) = Φ(A) = (F, G).

Proof. Proposition 3.1 implies that ρ^{−1}(P) = F. We must prove that ρ^{−1}(Q) = G, where Q is the recording tableau. Consider the insertion of an element i_{r} into G. The position of i_{r} in G is determined by the termination of insertion (j_{r} → F). Let h_{r} denote the height of the column at which the insertion of (j_{r} → F) terminates. The entry i_{r} appears in row h_{r} of G by definition. By Proposition 3.1, the reverse Schensted insertion of j_{r} terminates in row h_{r} of P. Hence i_{r} appears in row h_{r} of Q. Therefore the entries in the rows of Q are the same as those in the rows of G.

Recall that ρ^{−1}(Q) is the unique SSAF whose rows contain precisely the row entries of Q. The row entries of Q are inserted into ρ^{−1}(Q) in decreasing order, so that an entry α appears in the leftmost available column such that the entry immediately below α in this column is greater than or equal to α.

The top line of the array w_{A} is a weakly increasing sequence, so its entries are inserted into G in weakly decreasing order. Therefore the entries in a given row r are inserted into G in decreasing order. An entry i_{r} is placed on top of the leftmost possible column which does not create a descent. To see that the entries in a given row of ρ^{−1}(Q) appear in the same columns as the entries in a given column of G, argue by induction on the entries in the top line of the array w_{A}.

Consider first the entry i_{l}, where l is the length of w_{A}. This entry appears in the first row of G, in the i_{l}^{th} column. This entry also appears in the i_{l}^{th} column of ρ^{−1}(Q), since that is the leftmost possible position for i_{l} in ρ^{−1}(Q).

Assume that the entries i_{l}, i_{l−1}, …, i_{r} appear in the same columns in G as they do in ρ^{−1}(Q). Consider the entry i_{r−1}. This entry appears on top of the entry α in ρ^{−1}(Q). Therefore α ≥ i_{r−1}. This fact and the fact that α appears in a lower row of G than i_{r−1} imply that α is inserted into G before i_{r−1}. Since all the entries which were inserted into G before i_{r−1} appear in the same columns as in ρ^{−1}(Q), there is no entry on top of α in G during the insertion of i_{r−1}. This means that if i_{r−1} is not placed on top of α, then i_{r−1} is placed in a column to the left of the column containing α. Let β be the entry under i_{r−1} in this situation. Then β appears in this same position in ρ^{−1}(Q). Since i_{r−1} is not on top of β in ρ^{−1}(Q), there must be an entry γ > i_{r−1} on top of β in ρ^{−1}(Q). But if this were the case, then γ would also be on top of β in G since by assumption, all entries greater than i_{r−1} are in the same positions in G as they are in ρ^{−1}(Q). This contradicts the assumption that i_{r−1} is placed on top of β. Therefore the entries of G are in precisely the same positions as in ρ^{−1}(Q), so ρ^{−1}(Q) = G. □

Proposition 4.1 implies in particular that F and G are indeed semi-skyline augmented fillings. The semi-skyline augmented filling G records the column to which a cell is added in F. Therefore F and G are rearrangements of the same shape. These two facts imply that ρ is a map from ℕ-matrices to pairs of semi-skyline augmented fillings which are rearrangements of the same shape.

4.2. The inverse of the map Φ. Let (F, G) be a pair of semi-skyline augmented fillings whose shapes are rearrangements of the same partition λ. Then (ρ(F), ρ(G)) is a pair of reverse semi-standard Young tableaux of shape λ. Since the reverse Robinson–Schensted– Knuth algorithm is invertible, this pair (ρ(F), ρ(G)) comes from a unique matrix A of finite support. This matrix is Φ^{−1}((F, G)).

We describe the computation of this inverse without mapping through the reverse semistandard Young tableau pair. Let G_{rs} be the highest occurrence of the smallest entry of G in reading order. (Here G_{rs} is the element of G in row r and column s.)

Let s′ be the rightmost column of height r in F. Then F_{rs′} is the termination cell for the insertion of the last letter, j_{1} in the array corresponding to the matrix A. Delete F_{rs′} from F and G_{rs} from G. Scan right to left, bottom to top (backwards through the reading word) starting with the cell directly to the left of F_{rs′} to determine which cell (if any) bumped F_{rs′}. If there exists a cell k before F_{rs′} in the reading word such that F (k) > F_{rs′} and the cell directly on top of k has value less than or equal to F_{rs′}, this F (k) bumped F_{rs′} by the argument from Section 3.3. Replace F (k) by F_{rs′} and repeat the procedure with F (k) starting from the cell k. Continue working backward through the reading word until there are no more letters in the reading word. The resulting entry is the letter j_{1}. (Notice that this is the same procedure used in the map Ψ^{−1} in Section 3.3, so we have already proved that this procedure does in fact yield the inverse of the insertion of j_{1}.)

Next find the highest occurrence of the smallest entry j_{2} of the new recording filling. Repeat the procedure to find i_{2}. Continue until there are no more entries in the insertion and recording tableaux. Then all of the i and j values of the array w_{A} have been determined.

Corollary 4.3. The RSK algorithm commutes with the above analogue Φ. That is, if (P, Q) is the pair of SSYT produced by the RSK algorithm applied to a matrix A, then (Ψ(P), Ψ(Q)) = Φ(A).

Proof. The pair (P, Q) maps bijectively to the pair (S, T) of reverse SSYT produced by applying the reverse RSK algorithm to A. Proposition 4.1 states that (ρ^{−1}(S), ρ^{−1}(T)) = (F, G) = Φ(A). Proposition 3.1 implies that (Ψ(P), Ψ(Q)) = (ρ^{−1}(S), ρ^{−1}(T)), so (Ψ(P), Ψ(Q)) = (F, G) as desired. □

The algorithm Φ retains many of the properties of the Robinson–Schensted–Knuth Algorithm. Several of these properties are listed below, although this list is by no means complete.

Corollary 4.4. Assume that Φ(A) = (F, G). Then Φ(A^{t}) = (G, F).

Corollary 4.5. Let Φ(A) = (F, G). Let B be a matrix such that the bottom line of w_{B} is Knuth equivalent to the bottom line of w_{A}. Then Φ(B) = (F, G′) for some SSAF G′.

Corollaries 4.4 and 4.5 follow directly from the fact that the algorithm Φ commutes with the Robinson–Schensted–Knuth Algorithm.

4.3. Standardization. A standard Young tableau of shape λ is a semi-standard Young tableau whose weight is ∏_{i=1}^{n} x_{i}, where n = |λ|. Any semi-standard Young tableau T can be mapped to a standard Young tableau through a procedure called standardization.

Definition 4.6. Let γ be a weak composition of n. A skyline augmented filling (SAF) of shape γ is an SSAF of weight ∏_{i=1}^{n} x_{i}. Let F_{γ} denote the number of skyline augmented fillings of shape γ.

Notice that F_{γ} = 0 for certain compositions γ. This means that our analogue of standardization, skylining, must alter the shape of such compositions.

Procedure 4.7 (Skylining(F)). Assume that F is an SSAF of shape γ, where |γ| = n. Consider the reading word as a collection of row words for F. Standardize the reading word for F in the usual manner. Then place the new entries back into the original shape of F, maintaining the same order. If the lowest entry, α_{j} of the j^{th} column is not equal to j, shift the entire column to rest immediately on top of the α_{j}^{th} column. Denote the result by sk(F).

The entries in the first row of F are always strictly increasing from left to right. Therefore the shifting does not permute the order of the non-zero columns. Notice that if a appears before c in reading order, then F (a) ≤ F (c) ⇔ sk(F (a)) < sk(F (c)). Therefore I(F (a), F (b)) + I(F (b), F (c)) − I(F (a), F (c)) remains the same after skylining. The same is true for I(F (c), F (a)) + I(F (a), F (b)) − I(F (c), F (b)) since F (a) < F (c). This means that skylining preserves the inversion triples. This fact and the fact that there are no descents within the columns of F imply that the figure sk(F) is indeed a semi-skyline augmented filling.

Proposition 4.2. The bijection Ψ commutes with standardization.

Proof. Let T be a semi-standard Young tableau and Ψ(T) the corresponding SSAF. We saw in section 3.1 that the SSAFs are in bijective correspondence with reverse SSYTs, so it is enough to consider the reverse SSYT R corresponding to T.

F = 4 10 2  5  1 10 2  5  8 10 9 3  5  7 8 10 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17

sk(F) = 5 13 2  6  1  14 3  7  10  15 12 4  8 9 11  16 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17

Figure 4.2. An SSAF F and its standardization sk(F)

The set of entries in a given row r of R are sent to a new set of row entries under standardization. However, the new entries are the same entries which appear in row r of the skylining of Ψ(T) by the definition of sk(Ψ(T)). There is only one SSAF with the same row entries as the standardization of R, so this must be sk(Ψ(T)). □

References

[1] J. Haglund, M. Haiman, and N. Loehr, A combinatorial formula for Macdonald polynomials, J. Amer. Math. Soc. 18 (2005), no. 3, 735–761.

[2] , Combinatorial theory of Macdonald polynomials I: Proof of Haglund’s formula, Proc. Natl. Acad. Sci. USA 102 (2005), no. 8, 2690–2696.

[3] , A combinatorial formula for non-symmetric Macdonald polynomials, Amer. J. Math. 130 (2008), 359-383.

[4] Donald E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970), 709–727.

[5] I. G. Macdonald, A new class of symmetric functions, Actes du 20^{e} Séminaire Lotharingien, Publications I. R. M. A. 372/S-20 (1988), 131–171; electronically available as: Séminaire Lotharingien Combin. 20 (1988), Article B20a, 41 pp.

[6] Dan Marshall, Symmetric and nonsymmetric Macdonald polynomials. On combinatorics and statistical mechanics, Ann. Comb. 3 (1999), no. 2-4, 385–415.

[7] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191.

[8] Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1998.

Davidson College

  E-mail address: samason@davidson.edu
  URL: http://www.davidson.edu/math/mason