Parabolic Kazhdan-Lusztig polynomials for Hermitian symmetric pairs ^{1}

Francesco Brenti^{2} Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica, 1 00133 Roma, Italy brenti@mat.uniroma2.it

1 Introduction

In their fundamental paper [13] Kazhdan and Lusztig defined, for any Coxeter group W, a family of polynomials, indexed by pairs of elements of W, which have become known as the Kazhdan-Lusztig polynomials of W (see, e.g., [11, Chap.7] or [2, Chap.5]). These polynomials play an important role in several areas of mathematics, including the algebraic geometry and topology of Schubert varieties and representation theory (see, e.g., [2, Chap.5], and the references cited there). In order to prove the existence of these polynomials Kazhdan and Lusztig introduced another family of polynomials, usually called the R-polynomials, whose interest lies mainly in the fact that their knowledge is equivalent to that of the Kazhdan-Lusztig polynomials.

In 1987 Deodhar ([7]) introduced parabolic analogues of all these polynomials. These parabolic Kazhdan-Lusztig and R-polynomials reduce to the ordinary ones for the trivial parabolic subgroup of W and are also related to them in other ways (see, e.g., Proposition 2.4 below). Besides these connections the parabolic polynomials also play a direct role in several areas including the theories of generalized Verma modules ([6]), tilting modules ([15], [16]), quantized Schur algebras ([19]), Macdonald polynomials ([10], [9]), Schubert varieties in partial flag manifolds ([12]), and in the representation theory of the Lie algebra gl_{n} ([14]).

The purpose of this work is to study the parabolic Kazhdan-Lusztig polynomials for Hermitian symmetric pairs. More precisely, we give explicit combinatorial product formulas for these polynomials which imply, in particular, that they are always either zero or a monic power of q, and that they are combinatorial invariants.

The organization of the paper is as follows. In the next section we recall definitions, notation and results that are used in the rest of this work. In §3 we introduce and study the main new combinatorial concept of this work, namely a class of (possibly skew) shifted partitions that we call shifted-Dyck. In §4, using the results in the previous one and some from [5], we prove the main results of this work. Namely, we give explicit combinatorial product formulas for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs. These imply that these polynomals are combinatorial invariants. Finally, in §5, we give some applications of our main results. More precisely, we derive combinatorial closed product formulas for certain alternating sums of ordinary Kazhdan-Lusztig polynomials, and we prove a combinatorial invariance result for the Kazhdan-Lusztig polynomials studied in [3].

12000 Mathematics Subject Classification: Primary 05E99; Secondary 20F55.

2Partially supported by EU grant HPRN-CT-2001-00272. Part of this research was carried out while the author was a member of the Mittag-Leffler Institut in Djürsholm, Sweden, whose hospitality and financial support are gratefully acknowledged.

2 Preliminaries

In this section we collect some definitions, notation and results that are used in the rest of this work. We let P =^{def} {1, 2, 3, …} and N =^{def}P ∪{0}. For m, n ∈ N, m ≥ n, we let [n, m] =^{def} {n, n + 1, …, m − 1, m} and [n] =^{def} [1, n] (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|.

Given a set T we let S(T) be the set of all bijections π : T → T, and S_{n} =^{def} S([n]). If σ ∈ S_{n} then we write σ in disjoint cycle form (see, e.g., [17], p.17) and we usually omit writing the 1-cycles of σ. So, for example, if σ = (9, 7, 1, 3, 5)(2, 6) then σ(1) = 3, σ(2) = 6, σ(3) = 5, σ(4) = 4, etc. Given σ, τ ∈ S_{n} we let στ =^{def} σ ∘τ (composition of functions) so that, for example, (1, 2)(2, 3) = (1, 2, 3).

We follow Chapter 3 of [17] for poset notation and terminology. In particular, given a poset (P, ≤) and u, v ∈ P we let [u, v] =^{def} {z ∈ P : u ≤ z ≤ v} and call this an interval of P. We say that v covers u, denoted u ⊲ v (or, equivalently, that u is covered by v) if |[u, v]| = 2. The Hasse graph of P is the graph having P as vertex set and {{u, v} ⊆ P : u ⊲ v or v ⊲ u} as edge set. A poset is connected if its Hasse graph is a connected graph. The degree of an element v ∈ P is its degree as a vertex of the Hasse graph, namely |{u ∈ P : u ⊲ v or v ⊲ u}|. We say that u, v ∈ P are comparable if either u ≤ v or v ≤ u. If P has a minimum element, denoted ˆ0, then we call a subset of the form [ˆ0, u], for u ∈ P, a lower interval of P. We denote by J(P) the set of order ideals of P, partially ordered by set inclusion. Given any Q ⊆ P we will always consider Q as a poset with the partial ordering induced by P and call Q a subposet of P. If u, v ∈ P are such that {z ∈ P : z ≥ u, z ≥ v} has a minimum element, then we call this minimum element the join of u and v. Similarly, we define the meet of u and v if {z ∈ P : z ≤ u, z ≤ v} has a maximum element. We say that z ∈ P is minimal if there is no v ∈ P, v ≠ z, such that v ≤ z. Similarly, we define maximal. Given two posets P and Q, we write P ≅ Q to mean that they are isomorphic as posets. We note the following elementary observation, whose verification is omitted.

Proposition 2.1 Let P be a poset and X, Y ∈ J(P), X ⊆ Y. Then [X, Y] ≅ J(Y \ X).

We follow §7.2 of [18] for any undefined notation and terminology concerning partitions. Let H =^{def} {(i, j) ∈ P^{2} : i ≤ j}, with the ordering induced by the product ordering on P^{2}. We call the finite order ideals of H shifted partitions. We denote by S the set of all finite order ideals of H. We will always assume that S is partially ordered by set inclusion. It is well known that this makes S into a distributive lattice. Note that there is an obvious bijection between partitions into distinct parts and shifted partitions, given by

(λ_{1}, …, λ_{k}) ↔ {(i, j) ∈ P^{2} : 1 ≤ i ≤ k, i ≤ j ≤ λ_{i} + i − 1}.

For this reason we will freely identify these objects, and use expressions such as “the shifted partition (5, 2, 1).” We also identify each shifted partition with its diagram, which we draw rotated counterclockwise by \frac{3}{4}π radians with respect to the usual (Anglophone) convention. So, for example, the diagram of the shifted partition (5, 2, 1) is shown in Figure 1.

[figure]

Figure 1

We call the elements of H, and hence of a shifted partition, cells. Given a cell x = (i, j) ∈ H we define its level to be lv(x) =^{def} i + j − 1. Expressions such as “leftmost” or “to the right of” always refer to the rotated diagrams. In particular, given a cell x = (i, j) ∈ H (i, j ≥ 2) the cell directly below x is the cell x^{(1)} =^{def} (i − 1, j − 1) (see Figure 2). Similarly, we define directly above, directly northwest, etc... Also, we say that a cell y = (k, l) ∈ H is below x if l − k = j − i and

j ≥ l. We let δ_{n} =^{def} (n, n − 1, …, 2, 1).

Let μ, λ ∈ S, μ ⊆ λ. We then call λ \ μ a skew shifted partition. Note that, in poset theoretic language, skew shifted partitions are the finite convex subsets of H. Given a skew shifted

partition λ \ μ, λ = (λ_{1}, λ_{2}, …) and μ = (μ_{1}, μ_{2}, …), we define l(λ \ μ) =^{def} |{i ∈ P : λ_{i} > μ_{i}}|.

So, for example, l((5, 3, 1) \ (4, 3)) = 2. Given a skew shifted partition η and x = (i, j) ∈ H we define

d_{η}(x) =^{def} |{(k, l) ∈ η : l − k = j − i}|.

A connected skew shifted partition is uniquely determined, up to translation, by the two ordered sequences of the lengths of the sides of the “polygon” that it determines. For example, a skew shifted partition having the diagram depicted in Figure 2 is uniquely determined by the sequences (4, 2, 1, 2, 2, 1, 1, 1) and (3, 1, 1, 1, 1, 2, 2, 1, 1, 1) (in this order). We will use this “polygon notation” for skew shifted partitions in §5. Let η be a connected skew shifted partition. We say that a cell x = (i, j) ∈ η is an upper peak (respectively, lower valley) of η if it is maximal (respectively, minimal) in η and i ≠ j. We call an element x ∈ η an upper valley of η if x is covered by exactly two elements of η whose join is not in η. Similarly, we define a lower peak. If η and ρ are two skew shifted partitions then we write η ≈ ρ to mean that η is a translate of ρ.

We say that a skew shifted partition is a border strip if it never contains both a cell and the cell directly above it. For brevity, we call a connected border strip a cbs. Let λ, μ ∈ S be such that μ ⊆ λ. The outer border strip θ of λ \ μ is the set of cells x of λ \ μ such that the cell directly above x is not in λ \ μ. For example, the cells of the outer border strip of the skew shifted partition illustrated in Figure 2 are numbered from 1 to 13. We will usually number the cells of θ consecutively from left to right in this way, and identify them with their corresponding numbers. So, for example, 1 is the leftmost cell of θ, and if y ∈ θ, y > 1, then y − 1 is the cell of θ immediately to the left of y.

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; x; x^{(1)}]

Figure 2

We follow [11] for general Coxeter groups notation and terminology. In particular, given a Coxeter system (W, S) and u ∈ W we denote by l(u) the length of u in W, with respect to S, and we let D(u) =^{def} {s ∈ S : l(us) < l(u)}. For u, v ∈ W we let l(u, v) =^{def} l(v) − l(u). We denote by e the identity of W, and we let T =^{def} {usu^{−1} : u ∈ W, s ∈ S} be the set of reflections of W. Given J ⊆ S we let W_{J} be the parabolic subgroup generated by J and

W^{J} =^{def} {u ∈ W : l(su) > l(u) for all s ∈ J}.  (1)

Note that W^{∅} = W. If W_{J} is finite then we denote by w_{0}(J) its longest element. We will always assume that W^{J} is partially ordered by Bruhat order. Recall (see, e.g., [11], §5.9) that this means that x ≤ y if and only if there exist r ∈ N and t_{1}, …, t_{r} ∈ T such that t_{r} ⋯ t_{1} x = y and l(t_{i} ⋯ t_{1} x) > l(t_{i−1} ⋯ t_{1}x) for i = 1, …, r. Given u, v ∈ W^{J}, u ≤ v, we let

[u, v]^{J} =^{def} {z ∈ W^{J} : u ≤ z ≤ v},

and [u, v] =^{def} [u, v]^{∅}.

For J ⊆ S, x ∈ {−1, q}, and u, v ∈ W^{J} we denote by R_{u,v}^{J,x}(q) and P_{u,v}^{J,x}(q), the parabolic R-polynomials and parabolic Kazhdan-Lusztig polynomials (respectively) of W^{J} of type x (we refer the reader to [7] for the definitions of these polynomials, see also Proposition 2.3 below). It follows immediately from [7, §§2-3] and from well known facts (see, e.g., [11, §7.5] and [11, §§7.9-11]) that R_{u,v}^{∅,−1}(q) (= R_{u,v}^{∅,q}(q)) and P_{u,v}^{∅,−1}(q) (= P_{u,v}^{∅,q}(q)) are the (ordinary) R-polynomials and Kazhdan-Lusztig polynomials of W which we will denote simply by R_{u,v}(q) and P_{u,v}(q), as customary.

The following result is due to Deodhar, and we refer the reader to [7] for its proof. For

u, v ∈ W^{J} let μ_{J,q}(u, v) be the coefficient of q^{\frac{1}{2} (l(u,v)−1)} in P_{u,v}^{J,q}(q) (so μ_{J,q}(u, v) =^{def} 0 if l(u, v) is

even). We will often write μ(u, v) instead of μ_{J,q}(u, v) if there is no danger of confusion.

Proposition 2.2 Let (W, S) be a Coxeter system, J ⊆ S, and u, v ∈ W^{J}, u ≤ v. Then for each s ∈ D(v) we have that

P_{u,v}^{J,q}(q) = P̃ − ∑_{\{u≤w<vs: ws<w\}} μ_{J,q}(w, vs)q^{\frac{l(w,v)}{2}} P_{u,w}^{J,q}(q)

where

P̃ = \{ \begin{matrix}P_{us,vs}^{J,q} + qP_{u,vs}^{J,q}, & if us < u, \\ qP_{us,vs}^{J,q} + P_{u,vs}^{J,q}, & if u < us ∈ W^{J}, \\ 0, & if u < us ∉ W^{J}. \end{matrix}

The parabolic Kazhdan-Lusztig and R-polynomials are related to their ordinary counterparts in several ways, including the following one, which may be taken as their definition in most cases.

Proposition 2.3 Let (W, S) be a Coxeter system, J ⊆ S, and u, v ∈ W^{J}. Then we have that

R_{u,v}^{J,x}(q) = ∑_{w∈W_{J}}(−x)^{l(w)}R_{wu,v}(q),

for all x ∈ {−1, q}, and

P_{u,v}^{J,q}(q) = ∑_{w∈W_{J}}(−1)^{l(w)}P_{wu,v}(q).

Furthermore, if W_{J} is finite then

P_{u,v}^{J,−1}(q) = P_{w_{0}(J)u,w_{0}(J)v}(q).

A proof of this result can be found in [7] (see Propositions 2.12 and 3.4, and Remark 3.8). Yet another relation (which, however, we will not use) between parabolic and ordinary Kazhdan-Lusztig polynomials is given in [7, Proposition 3.5].

The purpose of this work is to study the parabolic Kazhdan-Lusztig polynomials for quotients W^{J} such that (W, W_{J}) is a Hermitian symmetric pair. These quotients have been classified (see, e.g., [3]) and there are five infinite families and two exceptional ones. Using (and abusing slightly) the standard notation for the classification of the finite Coxeter systems, the Hermitian symmetric pairs are: (A_{n}, A_{i−1} × A_{n−i}), (B_{n}, A_{n−1}), (B_{n}, B_{n−1}), (D_{n}, A_{n−1}), (D_{n}, D_{n−1}), (E_{6}, D_{5}), (E_{7}, E_{6}), (n ≥ 3, 1 ≤ i ≤ n). The parabolic Kazhdan-Lusztig polynomials for the pairs (A_{n}, A_{i−1} × A_{n−i}) (1 ≤ i ≤ n) have been computed in [4]. In this work we deal with the other ones.

We follow [2, Chap. 8] for combinatorial descriptions of the Coxeter systems of type B_{n} and D_{n} as permutation groups. In particular, we let S_{n}^{B} be the group of all bijections w of {−n, …, −1, 1, …, n} to itself such that w(−i) = −w(i) for all i ∈ [n], s_{j} =^{def} (j, j+1)(−j, −j−1) for j = 1, ..., n − 1, s_{0} =^{def} (1, −1), and B_{n} =^{def} {s_{0}, ..., s_{n−1}}. If v ∈ S_{n}^{B} then we write v = [a_{1}, …, a_{n}] to mean that v(i) = a_{i}, for i = 1, …, n. It is well known that (S_{n}^{B}, B_{n}) is a Coxeter system of type B_{n} and that the following holds. Given v ∈ S_{n}^{B} we let

inv(v) =^{def} |{(i, j) ∈ [n]^{2} : i < j, v(i) > v(j)}|,

N_{1}(v) =^{def} |{i ∈ [n] : v(i) < 0}| and

N_{2}(v) =^{def} |{(i, j) ∈ [n]^{2} : i < j, v(i) + v(j) < 0}|.

Proposition 2.4 Let v ∈ S_{n}^{B}. Then l(v) = inv(v) + N_{1}(v) + N_{2}(v), and D(v) = {s_{i} ∈ S_{B} : v(i) > v(i + 1)}, where v(0) =^{def} 0.

Let A_{n−1} =^{def} {s_{1}, …, s_{n−1}}. Then (S_{n}^{B})_{A_{n−1}} ≅ S_{n} and it is clear from Proposition 2.4 that v ∈ (S_{n}^{B})^{A_{n−1}} if and only if v^{−1}(1) < v^{−1}(2) < ⋯ < v^{−1}(n). In this case

v^{−1}(1) < ⋯ < v^{−1}(k) < 0 < v^{−1}(k + 1) < ⋯ < v^{−1}(n)

where k = N_{1}(v), and we associate to v ∈ (S_{n}^{B})^{A_{n−1}} the shifted partition

Λ_{B}(v) =^{def} (v^{−1}(−1), v^{−1}(−2), …, v^{−1}(−k)).  (2)

The next three results are known, and not hard to prove.

Proposition 2.5 The map Λ_{B} defined by (2) is a bijection between (S_{n}^{B})^{A_{n−1}} and {λ ∈ S : λ ⊆ δ_{n}}. Furthermore u ≤ v in (S_{n}^{B})^{A_{n−1}} if and only if Λ_{B}(u) ⊆ Λ_{B}(v), and l(v) = |Λ_{B}(v)|, for all u, v ∈ (S_{n}^{B})^{A_{n−1}}.

We find it sometimes convenient to identify a shifted partition in {λ ∈ S : λ ⊆ δ_{n}} with a lattice path with (1, 1) (up) and (1, −1) (down) steps starting at (0, 0) and having n steps. So, for example, the shifted partition (5, 2, 1) ⊆ δ_{7} corresponds to the lattice path illustrated in Figure 3. Given such a lattice path λ we denote by λ_{−} the lattice path which is the same as λ, except that its last (rightmost) step is down, and define λ_{+} similarly. Given j ∈ [n − 1] we say that a lattice path has a peak at j if its j-th step (from the left) is up and its (j + 1)-th step is down.

[figure]

Figure 3

Proposition 2.6 Let v ∈ (S_{n}^{B})^{A_{n−1}} and i ∈ [n]. Then the i-th step (from the left) of Λ_{B}(v) (seen as a lattice path) is an up-step if and only if v(n + 1 − i) < 0.

Lemma 2.7 Let v ∈ (S_{n}^{B})^{A_{n−1}} and j ∈ [n − 1]. Then l(vs_{j}) < l(v) if and only if Λ_{B}(v) has a peak at n − j. Furthermore, l(vs_{0}) < l(v) if and only if the last step of Λ_{B}(v) is up.

We let S_{n}^{D} be the subgroup of S_{n}^{B} defined by

S_{n}^{D} =^{def} {w ∈ S_{n}^{B} : N_{1}(w) ≡ 0 (mod 2)},

s̃_{0} =^{def} (1, −2)(2, −1), and S_{D} =^{def} {s̃_{0}, s_{1}, ..., s_{n−1}}. It is then well known that (S_{n}^{D}, S_{D}) is a Coxeter system of type D_{n}, and that the following holds (see, e.g., [2, §8.2]).

Proposition 2.8 Let v ∈ S_{n}^{D}. Then l(v) = inv(v) + N_{2}(v), and D(v) = {s_{i} ∈ S_{D} : v(i) > v(i + 1)} , where v(0) =^{def} −v(2).

Let v ∈ S_{n}^{D}. It is then clear from Proposition 2.8 that v ∈ (S_{n}^{D})^{A_{n−1}} if and only if v^{−1}(1) < ⋯ < v^{−1}(n). In this case

v^{−1}(1) < ⋯ < v^{−1}(k) < 0 < v^{−1}(k + 1) < ⋯ < v^{−1}(n)  (3)

where k = N_{1}(v), and we associate to v ∈ (S_{n}^{D})^{A_{n−1}} the shifted partition

Λ_{D}(v) =^{def} (v^{−1}(−1) − 1, v^{−1}(−2) − 1, …, v^{−1}(−k) − 1).  (4)

The next three results are known.

Proposition 2.9 The map Λ_{D} defined by (4) is a bijection between (S_{n}^{D})^{A_{n−1}} and {λ ∈ S : λ ⊆ δ_{n−1}}. Furthermore u ≤ v in (S_{n}^{D})^{A_{n−1}} if and only if Λ_{D}(u) ⊆ Λ_{D}(v), and l(v) = |Λ_{D}(v)|, for all u, v ∈ (S_{n}^{D})^{A_{n−1}}.

Proposition 2.10 Let v ∈ (S_{n}^{D})^{A_{n−1}} and i ∈ [n−1]. Then the i-th step (from the left) of Λ_{D}(v) (seen as a lattice path) is an up-step if and only if v(n + 1 − i) < 0. In particular, v(1) < 0 if and only if Λ_{D}(v) has an odd number of up-steps.

Lemma 2.11 Let v ∈ (S_{n}^{D})^{A_{n−1}} and j ∈ [2, n − 1]. Then l(vs_{j}) < l(v) if and only if Λ_{D}(v) has a peak at n − j. Furthermore, l(vs_{1}) < l(v) (respectively, l(vs̃_{0}) < l(v)) if and only if the last step of Λ_{D}(v) is up and Λ_{D}(v) has an even (respectively, odd) number of up-steps.

Let u ∈ S_{n}^{B}, and B_{n−1} =^{def} {s_{0}, …, s_{n−2}} ⊆ S_{B}. Then (S_{n}^{B})_{B_{n−1}} ≅ S_{n−1}^{B} and by Proposition

2.4 we have that

(S_{n}^{B})^{B_{n−1}} = {w ∈ S_{n}^{B} : 0 < w^{−1}(1) < ⋯ < w^{−1}(n − 1)}.

Therefore u ∈ (S_{n}^{B})^{B_{n−1}} if and only if there exist i ∈ [n] and ε ∈ {1, −1} such that

u = [1, 2, …, i − 1, εn, i, …, n − 1].

Let, for brevity, u_{εi} =^{def} [1, 2, …, i − 1, εn, i, …, n − 1]. It then follows easily from the definition of Bruhat order that

u_{n} < u_{n−1} < ⋯ < u_{1} < u_{−1} < ⋯ < u_{−n}.

So (S_{n}^{B})^{B_{n−1}}, partially ordered by Bruhat order, is a chain with 2n elements.

Let v ∈ S_{n}^{D}, and D_{n−1} =^{def} {s̃_{0}, s_{1}, …, s_{n−2}} ⊆ S_{D}. Then (S_{n}^{D})_{D_{n−1}} ≅ S_{n−1}^{D} and by Proposi-

tion 2.8 we have that

(S_{n}^{D})^{D_{n−1}} = {w ∈ S_{n}^{D} : w^{−1}(−2) < w^{−1}(1) < w^{−1}(2) < ⋯ < w^{−1}(n − 1)}.

Hence, if w ∈ (S_{n}^{D})^{D_{n−1}}, then 0 < w^{−1}(2) so

(S_{n}^{D})^{D_{n−1}} = {v_{εi} : i ∈ [n], ε ∈ {−1, 1}},

where

v_{εi} =^{def} \{ \begin{matrix}[ε1, 2, …, i − 1, ε n, i, …, n − 1], & if i ≥ 2, \\ [ε n, ε 1, 2, …, n − 1], & if i = 1, \end{matrix}

for i ∈ [n], ε ∈ {−1, 1}. Furthermore, it follows easily from the definition of Bruhat order (and from Proposition 2.8) that

v_{n} < v_{n−1} < ⋯ < v_{2} < v_{1} < v_{−2} < ⋯ < v_{−n},

v_{2} < v_{−1} < v_{−2}, and v_{−1} and v_{1} are incomparable.

3 Shifted Dyck skew shifted partitions

In this section we introduce and study the main new concept of this work, namely a class of skew shifted partitions that we call shifted Dyck. This class plays a fundamental role in the computation of the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs, and is the shifted analogue of the class of Dyck skew partitions introduced in [4]. The results in this section are used in the next one in the proof of our main theorem.

Let θ ⊆ H be a connected border strip (or, cbs, for short). Recall that we identify the cells of θ with the integers 1, 2, …, |θ| as explained in §2. We say that θ is almost Dyck if lv(x) ≥ lv(1) for all x ∈ θ. We say that θ is Dyck if it is almost Dyck and lv(|θ|) = lv(1).

Let θ be a cbs. Let x be the rightmost cell of θ such that lv(x) = lv(1). We define θ_{S} =^{def} θ ∪ {y^{(1)} : x < y ≤ |θ|} (recall that we denote by y^{(1)} the cell directly below y). So, for example, if θ is the cbs depicted in Figure 4 then θ_{S} is depicted in Figure 5. Note that, if θ is almost Dyck, then θ = θ_{S} if and only if θ is Dyck.

[figure]

Figure 4

[figure]

Figure 5

We can now give the crucial definition of this work.

Let η ⊆ H be a skew shifted partition. We define η to be shifted-Dyck (or, s-Dyck, for short) in the following inductive way:

i) η is s-Dyck if and only if each one of its connected components is s-Dyck;

ii) if η is connected then η is s-Dyck if and only if:

a) the outer border strip θ of η is almost Dyck, θ_{S} ⊆ η, and |θ_{S} \ θ| is even;

b) η \ θ_{S} is s-Dyck.

Finally, ∅ is s-Dyck.

Let η ⊂ H be an s-Dyck skew shifted partition. We define the depth of η, denoted dp (η), inductively by letting the depth of η be the sum of the depths of its connected components, and if η is connected letting

dp (η) =^{def} 1 + dp (η \ θ_{S})

(and dp (∅) =^{def} 0), where θ is the outer border strip of η. So, for example, the skew shifted partition depicted in Figure 6 is not s-Dyck, while that depicted in Figure 2 is and has depth 6.

Figure 6

We begin with the following elementary property. Let η ⊆ H be a skew shifted partition with only one rightmost cell. We denote by η′ any skew shifted partition whose diagram is the mirror image of that of η. Clearly, η′ is defined only up to translation.

Proposition 3.1 Let η be a skew shifted partition with only one rightmost cell. Then η is s-Dyck if and only if η′ is s-Dyck. Furthermore, in this case dp(η) = dp(η′).

Proof. Suppose η is s-Dyck. We may clearly assume that η is connected. We proceed by induction on |η|. Let m be the unique rightmost cell of η. Then m ∈ θ (where θ is the outer border strip of η) while m^{(1)} ∉ η (by the uniqueness of m). Hence, since η is s-Dyck, lv(m) = lv(1). Therefore θ is Dyck, and η \ θ = η \ θ_{S}. But η \ θ_{S} is s-Dyck, and η \ θ_{S} has only one rightmost cell. Therefore, by our induction hypothesis, (η \ θ_{S})′ is s-Dyck, and dp((η \ θ_{S})′) = dp(η \ θ_{S}). Hence (η \ θ)′ = η′ \ θ′ is s-Dyck, and therefore η′ is s-Dyck and dp(η′) = dp(η). □

The next two technical lemmas are needed in the proof of the main result of this section (Theorem 3.5).

In what follows, given a skew shifted partition η ⊆ H, we let, for brevity, η^{(1)} =^{def} η \θ_{S} where θ is the outer border strip of η.

Lemma 3.2 Let η be a skew shifted partition that is s-Dyck, and x be the leftmost cell of any connected component of η^{(1)}. Then

lv(x) ≥ lv(1) − d_{θ_{S}}(x),  (5)

where 1 is the leftmost cell of the connected component of η containing x.

Proof. Suppose first that d_{θ_{S}}(x) = 1. Let x′ be the cell directly above x and x′′ be the cell directly above x′. Since x′, x ∈ η, and x is the leftmost cell of its connected component of η^{(1)}, we deduce that y ∈ η \ η^{(1)} where y is the cell directly northwest of x (so, directly southwest of x′). Hence y ∈ θ_{S} and hence y ∈ θ (since d_{θ_{S}}(x) = 1). Therefore, since η is s-Dyck, lv(x) = lv(y) − 1 ≥ lv(1) − 1 and (5) holds.

Suppose now that d_{θ_{S}}(x) = 2. Let z be the rightmost cell of θ such that lv(z) = lv(1). Since x, x′, x′′ ∈ η, by our hypothesis on x we deduce similarly that y ∈ θ_{S} \ θ. Therefore lv(x) = lv(y) − 1 ≥ lv(z) − 2 = lv(1) − 2, as desired. □

Lemma 3.3 Let η be a skew shifted partition that is s-Dyck, and x ∈ θ. Then

lv(x) ≥ lv(1) + d_{η}(x) − 1,  (6)

where 1 is the leftmost cell of the connected component of η containing x.

Proof. We proceed by induction on d_{η}(x), the result being clear if d_{η}(x) = 1. Suppose d_{η}(x) ≥ 2, and let

x̂ =^{def} \{ \begin{matrix}x^{(1)}, & if d_{θ_{S}}(x) = 1, \\ x^{(2)}, & if d_{θ_{S}}(x) = 2, \end{matrix}

where x^{(2)} is the cell directly below x^{(1)}. Then x̂ is in the outer border strip of η^{(1)} (unless d_{η}(x) = d_{θ_{S}}(x) = 2, in which case (6) is clear). Therefore, using our induction hypothesis, we obtain that

lv(x) = lv(x̂) + 2d_{θ_{S}}(x)
≥ lv(ˆ1) + d_{η^{(1)}}(x̂) − 1 + 2d_{θ_{S}}(x)
= lv(ˆ1) + d_{η}(x) − 1 + d_{θ_{S}}(x)
≥ lv(1) + d_{η}(x) − 1 − d_{θ_{S}}(ˆ1) + d_{θ_{S}}(x)

by Lemma 3.2, where ˆ1 is the leftmost cell of the connected component of η^{(1)} that contains x̂, and (6) follows. □

Proposition 3.4 Let η be an s-Dyck skew shifted partition. Then below every upper peak of η there is either a lower peak or a lower valley.

Proof. We proceed by induction on |η|. Let x be an upper peak of η. Because η is s-Dyck, x cannot be the leftmost cell of η. Therefore x − 1, x + 1 ∈ η. If x^{(1)} ∉ η then clearly we are done. So assume x^{(1)} ∈ η. Let θ be the (almost Dyck, by our hypothesis) outer border strip of η. If d_{θ_{S}}(x) = 1 then x^{(1)} is an upper peak of η \ θ_{S} and hence, by induction, we are done. So assume d_{θ_{S}}(x) = 2. Then x^{(1)} ∈ θ_{S} and, since η is s-Dyck , d_{η}(x + 1) ≥ 2. If d_{η}(x − 1) = 1 then d_{θ_{S}}(x − 1) = 1 so, since η is s-Dyck , x − 1 would be the rightmost cell of θ such that lv(x − 1) = lv(1) which is a contradiction since lv(x + 1) = lv(x − 1). So d_{η}(x − 1) ≥ 2. Let x^{(2)} be the cell directly below x^{(1)}. If x^{(2)} ∉ η then clearly we are done, else x^{(2)} is an upper peak of η \ θ_{S} and the result again follows by induction. □

We can now prove the main result of this section.

Theorem 3.5 Let η be a skew shifted partition, and x be an upper peak of η. Suppose that η has a lower valley, y, below x, y ≠ x. Then the following are equivalent:

i) η is s-Dyck;

ii) exactly one of η \ {x}, η \ {x, y} is s-Dyck;

iii) η \ {y} is s-Dyck.

Furthermore, in this case

dp(η \ \{y\}) + 1 = dp(η) = \{ \begin{matrix}dp(η \ \{x\}) + 1, & if η \ \{x\} is s-Dyck, \\ dp(η \ \{x, y\}), & if η \ \{x, y\} is s-Dyck. \end{matrix}  (7)

Proof. We may clearly assume that η is connected. Note that η and η \{y} have the same outer border strip, which we denote by θ. Let z be the rightmost cell of θ such that lv(z) = lv(1).

We prove the equivalence of i) and iii) first.

We proceed by induction on d_{η}(x). Suppose d_{η}(x) = 2. If z ≤ x then, since d_{η}(x + 1) = 1, θ_{S} ⊈ η and θ_{S} ⊈ η \ {y} and the result holds. If z ≥ x + 1 then θ_{S} ⊆ η if and only if θ_{S} ⊆ η \ {y} and the single cell y is a connected component of η^{(1)} but not of (η \ {y})^{(1)}, which have the same connected components otherwise. So η^{(1)} is s-Dyck if and only if (η \ {y})^{(1)} is s-Dyck , and in this case dp(η^{(1)}) = dp((η \ {y})^{(1)}) + 1, and the result follows.

Suppose now that d_{η}(x) ≥ 3.

If z ≥ x + 1 then x^{(1)} is an upper peak of η^{(1)}, and η^{(1)} has the lower valley y below x^{(1)}. Therefore, by the induction hypothesis, η^{(1)} is s-Dyck if and only if η^{(1)} \ {y} is, and the result follows since η^{(1)} \ {y} = (η \ {y})^{(1)}.

If z = x then θ is not almost Dyck so the result holds.

If z ≤ x − 1 then z < x − 1 and therefore x^{(2)} (cell directly below x^{(1)}) is an upper peak of η^{(1)}, and η^{(1)} has the lower valley y below x^{(2)}. The result hence follows by induction as in the previous case if x^{(2)} ≠ y, and directly if x^{(2)} = y.

We now prove the equivalence of i) and ii).

Note first that, since y ≠ x, x > 1. If lv(1) ≥ lv(x − 1) − d_{η}(x) + 3 then, since x − 1 is in the outer border strips of all of η, η \ {x}, and η \ {x, y}, and d_{η}(x − 1) = d_{η\{x}}(x − 1) = d_{η\{x,y}}(x − 1) = d_{η}(x) − 1, we conclude from Lemma 3.3 that none of η, η \ {x}, and η \ {x, y} are s-Dyck and the result holds.

We may therefore assume that

lv(1) ≤ lv(x − 1) − d_{η}(x) + 2.

We now proceed by induction on d_{η}(x). We denote by θ′ (respectively, θ′′) the outer border strip of η \ {x} (respectively, η \ {x, y}).

If d_{η}(x) = 2 then lv(1) ≤ lv(x − 1). If lv(1) = lv(x − 1) then η \ {x} is not s-Dyck (since θ′ is not almost Dyck), and it is easy to verify that η is s-Dyck if and only if η \ {x, y} is, and in this case dp(η) = dp(η \ {x, y}), so the result holds in this case.

If lv(1) < lv(x − 1) then η \ {x, y} is not s-Dyck (since (x − 1)^{(1)} ∉ η \ {x, y}). If z < x − 1 then η and η \ {x} are not s-Dyck (since d_{η}(x − 1) = d_{η\{x}}(x − 1) = 1) and the result holds. So assume z > x + 1. Then θ′ = (θ \ {x}) ∪ {y}. Hence θ′ is almost Dyck if and only if θ is. Also, since z > x + 1, θ′_{S} = (θ_{S} \ {x}) ∪ {y} so θ_{S} ⊆ η if and only if θ′_{S} ⊆ η \ {x} and |θ_{S} \ θ| = |θ′_{S} \ θ′|. Furthermore η^{(1)} is s-Dyck if and only if (η \ {x})^{(1)} is s-Dyck (since they are equal except for one connected component equal to {y}), so we conclude that η is s-Dyck if and only if η \ {x} is, and in this case dp(η) = dp(η \ {x}) + 1, and the result holds.

Assume now that d_{η}(x) = 3. Then

lv(1) ≤ lv(x − 1) − 1.

If lv(1) = lv(x − 1) − 1 then by Lemma 3.3, applied to x^{(1)}, η \ {x} is not s-Dyck.

[figure: 1; z; x; y]

Figure 7

If z < x − 1 then (since lv(x) > lv(1), see Figure 7) lv(w) > lv(1) for all w ∈ θ, w > z. Also,

θ′′_{S} = (θ \ {x}) ∪ {x^{(1)}} ∪ {w^{(1)} : w ∈ θ, w > x}.  (8)

Suppose η is s-Dyck. Then θ is almost Dyck, θ_{S} ⊆ η, |θ_{S} \ θ| is even, and η \ θ_{S} is s-Dyck. Therefore, θ′′ = (θ \ {x}) ∪ {x^{(1)}} is almost Dyck and, by (8), θ′′_{S} ⊆ η \ {x, y} and |θ′′_{S} \ θ′′| = |θ| − x ≡ |θ| − z = |θ_{S} \ θ| (mod 2) (since lv(z) = lv(x) − 2). Furthermore, η^{(1)} and (η \ {x, y})^{(1)} have the same connected components except for the connected component η_{0} of (η \ {x, y})^{(1)} that contains (z + 1)^{(1)} (note that (z + 1)^{(1)} ∈ η because (z + 1)^{(1)} ∈ θ_{S}, but z^{(1)} ∉ η, by Lemma 3.3, since η is s-Dyck) which is replaced by η_{0} \ {w^{(1)}, w ∈ θ, z < w < x} and {y} in η^{(1)}. But η_{0} \ {w^{(1)} : w ∈ θ, z < w < x} is s-Dyck and {w^{(1)} : w ∈ θ, z < w < x} is a Dyck cbs and is the outer border strip of η_{0}. Therefore η_{0} is s-Dyck and hence (η \ {x, y})^{(1)} is s-Dyck, so η \ {x, y} is s-Dyck, and in this case dp(η) = dp(η \ {x, y}), as desired.

Conversely, suppose η \ {x, y} is s-Dyck. Then θ′′ is almost Dyck, θ′′_{S} ⊆ η \ {x, y}, |θ′′_{S} \ θ′′| is even, and (η \ {x, y})^{(1)} is s-Dyck. Therefore θ is almost Dyck, and η_{0} is s-Dyck (where η_{0} is the connected component of (η \{x, y})^{(1)} containing (x−1)^{(1)}). Since η_{0} is s-Dyck, its outer border strip, θ_{0}, is almost Dyck, therefore the leftmost cell a^{(1)} of θ_{0} must satisfy lv(a^{(1)}) ≤ lv((x−1)^{(1)}) (= lv(z) − 1). On the other hand, a (the cell directly above a^{(1)}) is in θ, and z < a < x, so lv(a^{(1)}) = lv(a)−2 ≥ lv(z)−1. Therefore lv(a^{(1)}) = lv(z)−1 and hence θ_{0} is Dyck, and a = z+1. Therefore θ_{0} = {w^{(1)} : w ∈ θ, z < w < x}. Since θ_{0} is a Dyck cbs we conclude that η_{0} \ θ_{0} is s-Dyck. Therefore θ_{S} ⊆ η, and |θ_{S} \θ| = |θ|−z ≡ |θ|−x = |θ′′_{S} \θ′′| ≡ 0 (mod 2). Furthermore, η^{(1)} and (η \ {x, y})^{(1)} are equal except for η_{0} which is replaced by η_{0} \ θ_{0} and {y} in η^{(1)}. Hence η^{(1)} is s-Dyck and therefore η is s-Dyck, and dp(η_{0}) = dp(η_{0} \ θ_{0}) + 1 = dp((η_{0} \ θ_{0}) ∪ {y}) so dp(η) = dp(η \ {x, y}), as desired.

If z > x + 1 then

θ_{S} = θ ∪ {w^{(1)} : w ∈ θ, z < w}  (9)

while

θ′′_{S} = (θ_{S} \ {x}) ∪ {x^{(1)}}.  (10)

This implies that θ is almost Dyck if and only if θ′′ is (and we may assume that this is the case) that |θ′′_{S} \ θ′′| = |θ_{S} \ θ| and that θ_{S} ⊆ η if and only if θ′′_{S} ⊆ η \ {x, y}. Furthermore,

(η \ {x, y})^{(1)} = η^{(1)} \ {x^{(1)}, y}.  (11)

So we only have to show that η^{(1)} is s-Dyck if and only if η^{(1)} \ {x^{(1)}, y} is. But η^{(1)} is a skew shifted partition, and x^{(1)} is an upper peak of η^{(1)} that has the lower valley y below it. Let a^{(1)} be the leftmost cell of the connected component of η^{(1)} that contains y. Then a (the cell directly above a^{(1)}) is in θ and lv(a − 1) < lv(a) by the choice of a^{(1)}. But a − 1 ∈ θ, hence lv(a − 1) ≥ lv(1) (we are assuming that θ is almost Dyck) and therefore lv(a) > lv(1) which implies that lv(a^{(1)}) ≥ lv(1) − 1 = lv((x − 1)^{(1)}) > l(y). Therefore, η^{(1)} \ {x^{(1)}} is not s-Dyck. Hence, since d_{η^{(1)}}(x^{(1)}) = 2, by what has been proved above, we conclude that η^{(1)} is s-Dyck if and only if η^{(1)} \ {x^{(1)}, y} is, and that dp(η^{(1)}) = dp(η^{(1)} \ {x^{(1)}, y}), so (7) follows from (11).

Suppose now that lv(1) ≤ lv(x − 1) − 2. If z < x − 1 then

θ′′ = θ′ = (θ \ {x}) ∪ {x^{(1)}}

and

θ′′_{S} = θ′_{S} = (θ_{S} \ {x}) ∪ {y}.

Therefore θ′′_{S} ⊈ η \ {x, y} and hence η \ {x, y} is not s-Dyck. Furthermore, note that θ is almost Dyck if and only if θ′ is, |θ_{S} \ θ| = |θ′_{S} \ θ′|, and θ_{S} ⊆ η if and only if θ′_{S} ⊆ η \ {x}. Finally, η^{(1)} and (η \ {x})^{(1)} are equal except for the connected component {y} that appears in η^{(1)} but not in (η \ {x})^{(1)}, so we conclude that η is s-Dyck if and only if η \ {x} is s-Dyck, and dp(η) = dp(η^{(1)}) + 1 = dp((η \ {x})^{(1)}) + 2 = dp(η \ {x}) + 1, and the result holds.

If z > x + 1 then

θ′′ = θ′ = (θ \ {x}) ∪ {x^{(1)}},

and

θ′′_{S} = θ′_{S} = (θ_{S} \ {x}) ∪ {x^{(1)}}.

Therefore θ is almost Dyck if and only if θ′ is, θ_{S} \ θ = θ′′_{S} \ θ′′ = θ′_{S} \ θ′, and θ_{S} ⊆ η if and only if θ′_{S} ⊆ η \ {x} if and only if θ′′_{S} ⊆ η \ {x, y}. Furthermore,

(η \ {x})^{(1)} = η^{(1)} \ {x^{(1)}},  (12)

and

(η \ {x, y})^{(1)} = η^{(1)} \ {x^{(1)}, y}.  (13)

But x^{(1)} is an upper peak of η^{(1)} that has the lower valley, y, below it, and d_{η^{(1)}}(x^{(1)}) = 2, so by our induction hypothesis we conclude that η^{(1)} is s-Dyck if and only if either η^{(1)} \ {x^{(1)}} or η^{(1)} \{x^{(1)}, y} are s-Dyck, but not both, and that in this case either dp(η^{(1)} \{x^{(1)}, y}) = dp(η^{(1)})

(if η^{(1)} \ {x^{(1)}, y} is s-Dyck) or dp(η^{(1)} \ {x^{(1)}}) = dp(η^{(1)}) − 1 (if η^{(1)} \ {x^{(1)}} is s-Dyck) and the result follows from (12) and (13).

Suppose now that d_{η}(x) ≥ 4. Then

lv(1) ≤ lv(x − 1) − 2.

Hence θ′′ = θ′ = (θ \ {x}) ∪ {x^{(1)}}. If θ is not almost Dyck then the result follows immediately. So assume that θ is almost Dyck. Let, for convenience,

x̂ =^{def} \{ \begin{matrix}x^{(1)}, & if z > x + 1, \\ x^{(2)}, & if z < x − 1, \end{matrix}

where x^{(2)} is the cell directly below x^{(1)}. Then

θ′′_{S} = θ′_{S} = (θ_{S} \ {x}) ∪ {x̂}.  (14)

It then follows from (14) that

(η \ {x})^{(1)} = η^{(1)} \ {x̂}  (15)

and

(η \ {x, y})^{(1)} = η^{(1)} \ {x̂, y}.  (16)

Now, from (14) we have that θ_{S} ⊆ η if and only if θ′_{S} ⊆ η \ {x} if and only if θ′′_{S} ⊆ η \ {x, y}, and |θ_{S} \ θ| = |θ′_{S} \ θ′| = |θ′′_{S} \ θ′′|. Furthermore, θ′ = θ′′ is almost Dyck. Finally, observe that x̂ is an upper peak of η^{(1)} that has the lower valley y below it. Hence, by the induction hypothesis, η^{(1)} is s-Dyck if and only if either η^{(1)} \ {x̂} or η^{(1)} \ {x̂, y} are s-Dyck, but not both, and in this case either dp(η^{(1)}) = dp(η^{(1)} \ {x̂, y}) (if η^{(1)} \ {x̂, y} is s-Dyck) or dp(η^{(1)}) = dp(η^{(1)} \ {x̂}) + 1 (if η^{(1)} \ {x̂} is s-Dyck), so the result follows from (15) and (16). □

We note the following consequence of the proof of the previous theorem, which will be used in the sequel.

Proposition 3.6 Let η be a skew shifted partition, and x be an upper peak of η. Suppose that η has a lower valley, y, below x, y ≠ x. Then η \ {x} and η \ {x, y} cannot both be s-Dyck.

We conclude this section with three technical lemmas which are needed in §5.

Lemma 3.7 Let n ∈ P, n ≥ 2, and μ be a shifted partition such that μ ⊆ δ_{n}. Then δ_{n} \ μ is s-Dyck if and only if there exist 0 ≤ i_{1} < ⋯ < i_{r} ≤ ⌊\frac{n−1}{2}⌋ (0 ≤ r ≤ ⌊\frac{n+1}{2}⌋) such that

μ = \{ \begin{matrix}(2i_{r} + 1, 2i_{r}, …, 2i_{1} + 1, 2i_{1}), & if n is odd, \\ (n, 2i_{r} + 1, 2i_{r}, …, 2i_{1} + 1, 2i_{1}), & if n is even. \end{matrix}  (17)

In this case, dp(δ_{n} \ μ) = ⌈\frac{n−l(μ)}{2}⌉.

Proof. We proceed by induction on n. If n ≤ 3 the result is easy to verify. Let μ = (μ_{1}, μ_{2}, …, μ_{l}).

Suppose that δ_{n} \ μ is s-Dyck. If μ_{1} = n then δ_{n} \ μ ≈ δ_{n−1} \ (μ_{2}, …, μ_{l}) and by induction the result holds. If μ_{1} < n then the outer border strip θ of δ_{n} \ μ is a 1 × n rectangle such that lv(i) = lv(1) + i − 1 for i = 1, …, n. Therefore, since δ_{n} \ μ is s-Dyck, we deduce that μ_{1} ≤ n − 2 and n is odd. Hence μ ⊆ δ_{n−2}, and δ_{n−2} \ μ = (δ_{n} \ μ) \ θ_{S} so the result follows by induction.

Conversely, suppose μ is of the form (17). If μ_{1} = n then δ_{n} \ μ ≈ δ_{n−1} \ (μ_{2}, …, μ_{l}) and we are done by induction. If μ_{1} < n then n is odd so, by (17), μ ⊆ δ_{n−2}. Hence θ (the outer border strip of δ_{n} \ μ) is almost Dyck, θ_{S} ⊆ δ_{n} \ μ and |θ_{S} \ θ| = n − 1 is even. Furthermore, (δ_{n} \ μ) \ θ_{S} = δ_{n−2} \ μ and this is s-Dyck by induction. Hence δ_{n} \ μ is s-Dyck, as desired. □

In what follows we will sometimes call, for brevity, a shifted partition μ satisfying the equivalent conditions of Lemma 3.7 almost even.

Lemma 3.8 Let n ∈ P, n ≥ 3, ν_{n} =^{def} (n, n − 1, …, 4, 3, 1), and μ be a shifted partition such that μ ⊆ ν_{n}. Then ν_{n} \ μ is s-Dyck if and only if there exist 2 ≤ i_{1} < ⋯ < i_{r} ≤ ⌊\frac{n−1}{2}⌋ (0 ≤ r ≤ ⌊\frac{n−3}{2}⌋) and (a, b) ∈ \{(3, 1), (2, 1), (2, 0), (3, 0)\} such that

μ = \{ \begin{matrix}(2i_{r} + 1, 2i_{r}, …, 2i_{1} + 1, 2i_{1}, a, b), & if n is odd, \\ (n, 2i_{r} + 1, 2i_{r}, …, 2i_{1} + 1, 2i_{1}, a, b), & if n is even. \end{matrix}  (18)

In this case, dp(ν_{n} \ μ) = ⌈\frac{n−l(μ)}{2}⌉ + dp((3, 1) \ (a, b)) − 1.

Proof. We proceed by induction on n. If n ≤ 4 the result is easy to verify. Let μ = (μ_{1}, μ_{2}, …, μ_{l}).

Suppose that ν_{n} \ μ is s-Dyck. If μ_{1} = n then ν_{n} \ μ ≈ ν_{n−1} \ (μ_{2}, …, μ_{l}) and by induction the result holds. If μ_{1} < n then, since ν_{n} \ μ is s-Dyck, μ_{1} ≤ n − 2 so the outer border strip θ of ν_{n} \ μ is a cbs of cardinality n such that lv(i) = lv(1) + i − 1 for i = 1, …, n − 2, lv(n − 1) = lv(n − 2) − 1, lv(n) = lv(n − 2). Therefore, since ν_{n} \ μ is s-Dyck, we deduce that μ_{n−1} = 0, μ_{n−2} = 0, μ_{n−3} ≤ 1, and n is odd. Hence μ ⊆ ν_{n−2} and ν_{n−2} \ μ = (ν_{n} \ μ) \ θ_{S}, so the result follows by induction.

Conversely, suppose μ is of the form (18). If μ_{1} = n then ν_{n} \ μ ≈ ν_{n−1} \ (μ_{2}, …, μ_{n−1}) and we are done by induction. If μ_{1} < n then n is odd so, by (18), μ_{1} ≤ n − 2 and hence μ_{n−4} ≤ 3. This, again by (18), implies that μ_{n−3} ≤ 1 and hence that μ ⊆ ν_{n−2}. Hence θ (the outer border strip of ν_{n} \μ) is almost Dyck, θ_{S} ⊆ ν_{n} \μ and |θ_{S} \θ| = n−1 is even. Furthermore, (ν_{n} \ μ) \ θ_{S} = ν_{n−2} \ μ and this is s-Dyck by induction. Hence ν_{n} \ μ is s-Dyck, as desired. □

Lemma 3.9 Let n ∈ P, n ≥ 3, and μ be a shifted partition such that μ ⊆ δ_{n}^{−} ( =^{def} (n, n − 1, …, 3, 2)). Then δ_{n}^{−} \ μ is s-Dyck if and only if there exist 2 ≤ i_{1} < ⋯ < i_{r} ≤ ⌊\frac{n−1}{2}⌋ (0 ≤ r ≤ ⌊\frac{n−3}{2}⌋) and (a, b) ∈ \{(3, 2), (3, 1), (1, 0), (2, 0)\} such that

μ = \{ \begin{matrix}(2i_{r} + 1, 2i_{r}, …, 2i_{1} + 1, 2i_{1}, a, b), & if n is odd, \\ (n, 2i_{r} + 1, 2i_{r}, …, 2i_{1} + 1, 2i_{1}, a, b), & if n is even. \end{matrix}  (19)

In this case, dp(δ_{n}^{−} \ μ) = ⌈\frac{n−l(μ)}{2}⌉ + dp((3, 2) \ (a, b)) − 1.

Proof. We proceed by induction on n. If n ≤ 4 the result is easy to verify. Let μ = (μ_{1}, μ_{2}, …, μ_{l}).

Suppose that δ_{n}^{−} \ μ is s-Dyck. If μ_{1} = n then δ_{n}^{−} \ μ ≈ δ_{n−1}^{−} \ (μ_{2}, …, μ_{l}) and by induction the result holds. If μ_{1} < n then since δ_{n}^{−} \ μ is s-Dyck, μ_{1} ≤ n − 2 so the outer border strip θ of δ_{n}^{−} \ μ is a cbs of cardinality n such that lv(i) = lv(1) + i − 1 for i = 1, …, n − 1, and lv(n) = lv(n − 1) − 1. Therefore, since δ_{n}^{−} \ μ is s-Dyck, we deduce that n is odd and μ ⊆ δ_{n−2}^{−}. But δ_{n−2}^{−} \ μ = (δ_{n}^{−} \ μ) \ θ_{S}, so the result follows by induction.

Conversely, suppose μ is of the form (19). If μ_{1} = n then δ_{n}^{−} \ μ ≈ δ_{n−1}^{−} \ (μ_{2}, …, μ_{l}) and we are done by induction. If μ_{1} < n then, by (19), n is odd, so μ_{1} ≤ n − 2 and hence μ_{n−4} ≤ 3. Therefore, again by (19), μ_{n−2} = 0. Hence θ is almost Dyck, θ_{S} ⊆ δ_{n}^{−} \ μ and |θ_{S} \ θ| = n − 1 is even, and μ ⊆ δ_{n−2}^{−}. But (δ_{n}^{−} \ μ) \ θ_{S} = δ_{n−2}^{−} \ μ is s-Dyck by induction, so δ_{n}^{−} \ μ is s-Dyck, as desired. □

4 Parabolic Kazhdan-Lusztig Polynomials

In this section, using the results in the previous one and some from [5], we prove the main result of this work. More precisely, we give explicit combinatorial formulas for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs. Our results imply that these polynomials are combinatorial invariants.

We begin with the Hermitian symmetric pairs (S_{n}^{B}, A_{n−1}) and (S_{n}^{D}, A_{n−1}). Let W^{J} ∈ {(S_{n}^{B})^{A_{n−1}}, (S_{n+1}^{D})^{A_{n}}} and u ∈ W^{J}. By (2), (4), and the comments following Proposition 2.5 we may associate to u a lattice path, which we will denote, for simplicity, by Λ(u), with (1, 1) and (1, −1) steps, starting at (0, 0) and having n steps. Furthermore, by Propositions 2.5 and 2.9, we have that, for all u, v ∈ W^{J}, u ≤ v if and only if Λ(u) lies (weakly) below Λ(v) (write Λ(u) ≤ Λ(v), if this is the case). Recall the identification between lattice paths and shifted partitions made before Proposition 2.6.

Theorem 4.1 Let W^{J} ∈ {(S_{n}^{B})^{A_{n−1}}, (S_{n}^{D})^{A_{n−1}}} and u, v ∈ W^{J}, u ≤ v. Then

P_{u,v}^{J,q}(q) = \{ \begin{matrix}q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}, & if λ \ μ is s-Dyck, \\ 0, otherwise, \end{matrix}

where μ =^{def} Λ(u), λ =^{def} Λ(v).

Proof. We proceed by induction on l(v) = |Λ(v)|, the result being clearly true if v = e. Let, for notational simplicity, P_{x,y}^{J} =^{def} P_{x,y}^{J,q}(q) for all x, y ∈ W^{J}. We may clearly assume that l(u, v) ≥ 2.

Assume first that W^{J} = (S_{n}^{B})^{A_{n−1}} (so Λ(z) = Λ_{B}(z) for all z ∈ W^{J}).

Suppose that λ \ μ has an upper peak x and let s = s_{i} ∈ S_{B} \ {s_{0}} be the corresponding element of D(v) (see Lemma 2.7). Note that Λ_{B}(vs) = λ \ {x}. Then we have from Proposition 2.2 that

P_{u,v}^{J} = P̃ − ∑_{\{u≤w<vs: ws<w\}} μ(w, vs)q^{\frac{l(w,v)}{2}} P_{u,w}^{J}  (20)

where

P̃ = \{ \begin{matrix}P_{us,vs}^{J} + qP_{u,vs}^{J}, & if us < u, \\ qP_{us,vs}^{J} + P_{u,vs}^{J}, & if u < us ∈ W^{J}, \\ 0, & if u < us ∉ W^{J}. \end{matrix}

Now let w ∈ W^{J} be such that u ≤ w < vs and ws < w, and ν =^{def} Λ_{B}(w). Then from Lemma 2.7 we have that ν has an upper peak, y, below x. Furthermore, y ≠ x since w ≤ vs. Note that this implies that x is not the leftmost cell of λ \ μ. Now, since l(vs) < l(v), we conclude from our induction hypothesis that if μ(w, vs) ≠ 0 then (λ \ {x}) \ ν is s-Dyck and dp((λ \ {x}) \ ν) = 1. This implies that d_{λ\ν}(x) ∈ {2, 3}. But x^{(1)} (the cell directly below x) is an upper valley of (λ \ {x}) \ ν, and x^{(2)} (the cell directly above y) is a lower peak of (λ \ {x}) \ ν (possibly x^{(1)} = x^{(2)}). Therefore d_{(λ\ν)\{x}}(x − 1) = d_{(λ\ν)\{x}}(x^{(1)}) + 1, and this contradicts the fact that (λ \ ν) \ {x} is s-Dyck and dp((λ \ ν) \ {x}) = 1. This shows that μ(w, vs) = 0 and hence that the sum on the right hand side of (20) is also equal to zero. Therefore

P_{u,v}^{J} = \{ \begin{matrix}P_{us,vs}^{J} + qP_{u,vs}^{J}, & if us < u, \\ qP_{us,vs}^{J} + P_{u,vs}^{J}, & if u < us ∈ W^{J}, \\ 0, & if u < us ∉ W^{J}. \end{matrix}  (21)

There are now three cases to consider.

a) u < us ∉ W^{J}. Then u(i)u(i + 1) > 0 and this, by Proposition 2.6, implies that λ \ μ has neither a lower valley nor a lower peak below x. But then, by Proposition 3.4, λ \ μ is not s-Dyck and the result follows from (21).

b) u < us ∈ W^{J}.

Then u(i) < 0 < u(i + 1) and this, by Proposition 2.6, implies that λ \ μ has a lower valley, y, below x and, clearly, Λ_{B}(us) = μ ∪ {y}.

Suppose that λ \ μ is not s-Dyck. Then, by Theorem 3.5, we conclude that (λ \ μ) \ {x, y} and (λ \ μ) \ {x} are not s-Dyck. Hence we conclude from (21) and our induction hypothesis that P_{u,v}^{J} = 0, as desired.

Suppose now that λ \ μ is s-Dyck. Then from Theorem 3.5 we conclude that exactly one of (λ \ μ) \ {x, y} and (λ \ μ) \ {x} is s-Dyck. If (λ \ μ) \ {x, y} is s-Dyck then from Theorem 3.5, (21), and our induction hypothesis we conclude that

P_{u,v}^{J} = q q^{\frac{1}{2} (|(λ\μ)\\{x,y\}|−dp((λ\μ)\\{x,y\}))}
= q q^{\frac{1}{2} (|λ\μ|−2−dp(λ\μ))}
= q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}

as desired. If (λ \ μ) \ {x} is s-Dyck then we conclude similarly that

P_{u,v}^{J} = q^{\frac{1}{2} (|(λ\μ)\\{x\}|−dp((λ\μ)\\{x\}))}
= q^{\frac{1}{2} (|λ\μ|−1−(dp(λ\μ)−1))}
= q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}

as desired.

c) u > us.

Then, by Lemma 2.7, λ \ μ has a lower peak below x. Let y be the cell directly below this lower peak. Then, clearly, Λ_{B}(us) = μ \ {y}.

Suppose that λ \ μ is not s-Dyck. Then, by Theorem 3.5 and Proposition 3.6, applied to η = λ \ (μ \ {y}) = (λ \ μ) ∪ {y}, η \ {x, y} = (λ \ μ) \ {x} and η \ {x} = ((λ \ μ) \ {x}) ∪ {y} are not s-Dyck. Hence we conclude from (21) and our induction hypothesis that P_{u,v}^{J} = 0, as desired.

Suppose now that λ \ μ is s-Dyck. Then, again from Theorem 3.5, we conclude that exactly one of (λ \ μ) \ {x} and ((λ \ μ) \ {x}) ∪ {y} is s-Dyck. If (λ \ μ) \ {x} is s-Dyck then from (21), Theorem 3.5, and our induction hypothesis we conclude that

P_{u,v}^{J} = q q^{\frac{1}{2} (|(λ\μ)\\{x\}|−dp((λ\μ)\\{x\}))}
= q q^{\frac{1}{2} (|(λ\μ)|−1−dp((λ\μ)∪\{y\}))}
= q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}

as desired. If ((λ \ μ) \ {x}) ∪ {y} is s-Dyck then we conclude similarly that

P_{u,v}^{J} = q^{\frac{1}{2} (|((λ\μ)\\{x\})∪\{y\}|−dp (((λ\μ)\\{x\})∪\{y\}))}
= q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}

and the result again follows.

Suppose now that λ \ μ has no upper peaks. Let μ = (μ_{1}, …, μ_{l}). Then (the lattice paths corresponding to) λ and μ coincide from (0, 0) up to a certain point P_{0} = (r + s, r − s), and to the right of this point all the steps of λ are up. So λ \ μ ≈ δ_{n−r−s} \ μ̃ where μ̃ = (μ_{r+1}, …, μ_{l}). In particular, by Lemma 2.7, s_{0} ∈ D(v). Note that Λ_{B}(vs_{0}) = λ_{−} (same as λ, but with the last step down).

Let w ∈ W^{J} be such that u ≤ w < vs_{0} and ws_{0} < w, and ν =^{def} Λ_{B}(w). Then from Lemma 2.7 we have that the last step of ν is up. Since l(vs_{0}) < l(v), we conclude from our induction hypothesis that if μ(w, vs_{0}) ≠ 0 then λ_{−} \ ν is s-Dyck and dp(λ_{−} \ ν) = 1. This implies that the vertical distance between the (right end of the) n-th step of λ_{−} and the (right end of the) n-th step of ν is zero. This, since λ_{−} \ ν is s-Dyck and dp(λ_{−} \ ν) = 1, implies that |λ_{−} \ ν| = 1. This shows that ν coincides with λ_{−} except that its (n − 1)-th and n-th steps are down and up, respectively, rather than up and down. Therefore w = vs_{0}s_{1}. This shows that μ(w, vs_{0}) = 0 unless w = vs_{0}s_{1}. Therefore

∑_{\{u≤w<vs_{0}: ws_{0}<w\}} μ(w, vs_{0})q^{\frac{l(w,v)}{2}} P_{u,w}^{J} = qP_{u,vs_{0}s_{1}}^{J},

(note that u ≤ vs_{0}s_{1} since |λ \ μ| ≥ 2). Hence, since us_{0} ∈ W^{J}, we conclude from Proposition 2.2 that

P_{u,v}^{J} = \{ \begin{matrix}P_{us_{0},vs_{0}}^{J} + qP_{u,vs_{0}}^{J} − qP_{u,vs_{0}s_{1}}^{J}, & if us_{0} < u, \\ qP_{us_{0},vs_{0}}^{J} + P_{u,vs_{0}}^{J} − qP_{u,vs_{0}s_{1}}^{J}, & if u < us_{0}. \end{matrix}  (22)

We now distinguish two cases.

i) us_{0} < u.

Then, by Proposition 2.4, u(1) < 0 and, by Lemma 2.7, the last step of μ is up. So Λ_{B}(us_{0}) = μ_{−}, and the last part of μ is 1.

Suppose λ \ μ is s-Dyck. Then, by Lemmas 3.7 and 3.8, ν \ μ is not s-Dyck (where ν =^{def} Λ_{B}(vs_{0}s_{1})) and l(μ̃) ≡ n − r − s (mod 2). Furthermore, by Lemmas 3.7 and 3.9, λ_{−} \ μ is s-Dyck if and only if μ_{l−1} ≥ 4 while λ_{−} \ μ_{−} is s-Dyck if and only if μ_{l−1} = 2. Therefore we conclude from (22) and our induction hypothesis that

P_{u,v}^{J} = \{ \begin{matrix}q^{\frac{1}{2} (|λ_{−}\μ_{−}|−dp(λ_{−}\μ_{−}))}, & if λ_{−} \ μ_{−} is s-Dyck, \\ q q^{\frac{1}{2} (|λ_{−}\μ|−dp(λ_{−}\μ))}, & if λ_{−} \ μ is s-Dyck. \end{matrix}

But, by Lemmas 3.7 and 3.9

dp(λ_{−} \ μ_{−}) = ⌈\frac{n − r − s − l(μ̃) + 1}{2}⌉ − 1 = dp(λ \ μ)

if λ_{−} \ μ_{−} is s-Dyck, while

dp(λ_{−} \ μ) = ⌈\frac{n − r − s − l(μ̃)}{2}⌉ + dp((3, 2) \ (1, 0)) − 1 = 1 + dp(λ \ μ)

if λ_{−} \ μ is s-Dyck, so the result holds in this case.

Suppose now that λ \ μ is not s-Dyck. If ν \ μ is not s-Dyck then, by Lemmas 3.8 and 3.9, λ_{−}\μ and λ_{−}\μ_{−} are not s-Dyck, and the result follows from (22) and our induction hypothesis. So assume ν \ μ is s-Dyck. Then it follows from Lemmas 3.8 and 3.9 that l(μ̃) ≢ n − r − s (mod 2) and that λ_{−} \ μ is s-Dyck if and only if μ_{l−1} = 3 while λ_{−} \ μ_{−} is s-Dyck if and only if μ_{l−1} = 2.

If λ_{−} \ μ is s-Dyck then we conclude from Lemmas 3.9 and 3.8 that

dp(ν \ μ) = ⌈\frac{n − r − s − l(μ̃)}{2}⌉ − 1 = dp(λ_{−} \ μ) − 1.

Therefore, by our induction hypothesis, P_{u,vs_{0}s_{1}}^{J} = q^{\frac{1}{2} (|ν\μ|−dp(ν\μ))} = P_{u,vs_{0}}^{J}, and the result follows from (22).

Similarly, if λ_{−} \ μ_{−} is s-Dyck then we conclude that

dp(ν \ μ) = ⌈\frac{n − r − s − l(μ̃)}{2}⌉ + dp((3, 1) \ (2, 1)) − 1
= ⌈\frac{n − r − s − l(μ̃) + 1}{2}⌉ + dp((3, 2) \ (2, 0)) − 1
= dp(λ_{−} \ μ_{−}).

Therefore, by induction, qP_{u,vs_{0}s_{1}}^{J} = q q^{\frac{1}{2} (|ν\μ|−dp(ν\μ))} = P_{us_{0},vs_{0}}^{J}, and the result follows from (22). ii) u < us_{0}.

Then, by Proposition 2.4, u(1) > 0 and hence, by Proposition 2.6, the last step of μ is down. So μ_{l} ≥ 2, and Λ_{B}(us_{0}) = μ_{+}.

Suppose λ\μ is s-Dyck. Then, by Lemmas 3.7 and 3.8, ν\μ is not s-Dyck, and l(μ̃) ≢ n−r−s (mod 2). Furthermore, by Lemmas 3.7 and 3.9, λ_{−} \ μ is s-Dyck if and only if μ_{l} = 2 while λ_{−} \ μ_{+} is s-Dyck if and only if μ_{l} ≥ 4. Therefore we conclude from (22) and our induction hypothesis that

P_{u,v}^{J} = \{ \begin{matrix}q^{\frac{1}{2} (|λ_{−}\μ|−dp(λ_{−}\μ))}, & if λ_{−} \ μ is s-Dyck, \\ qq^{\frac{1}{2} (|λ_{−}\μ_{+}|−dp(λ_{−}\μ_{+}))}, & if λ_{−} \ μ_{+} is s-Dyck. \end{matrix}

But, by Lemmas 3.7 and 3.9,

dp(λ_{−} \ μ) = ⌈\frac{n − r − s − l(μ̃)}{2}⌉ − 1 = dp(λ \ μ) − 1,

if μ_{l} = 2, while

dp(λ_{−} \ μ_{+}) = ⌈\frac{n − r − s − l(μ̃) − 1}{2}⌉ + dp((3, 2) \ (1, 0)) − 1
= ⌈\frac{n − r − s − l(μ̃) − 2}{2}⌉ + 1
= dp(λ \ μ)

if μ_{l} ≥ 4, so the result holds in this case.

Suppose now that λ \ μ is not s-Dyck. If ν \ μ is not s-Dyck then, by Lemmas 3.8 and 3.9, λ_{−}\μ and λ_{−}\μ_{+} are not s-Dyck, and the result follows from (22) and our induction hypothesis. So assume that ν \ μ is s-Dyck. Then it follows from Lemmas 3.8 and 3.9 that l(μ̃) ≡ n − r − s (mod 2) and that λ_{−} \ μ is s-Dyck if and only if μ_{l} = 2 while λ_{−} \ μ_{+} is s-Dyck if and only if μ_{l} = 3. Furthermore,

dp(ν \ μ) = ⌈\frac{n − r − s − l(μ̃)}{2}⌉ + dp((3, 1) \ (2, 0)) − 1
= ⌈\frac{n − r − s − l(μ̃)}{2}⌉ + 1
= dp(λ_{−} \ μ) + 1

if μ_{l} = 2, while

dp(ν \ μ) = ⌈\frac{n − r − s − l(μ̃)}{2}⌉ + dp((3, 1) \ (3, 0)) − 1
= ⌈\frac{n − r − s − l(μ̃) − 1}{2}⌉
= dp(λ_{−} \ μ_{+})

if μ_{l} = 3, so the result follows from (22) and our induction hypothesis.

Assume now that W^{J} = (S_{n}^{D})^{A_{n−1}}.

If λ \ μ has an upper peak then the proof is analogous to that of the corresponding case for (S_{n}^{B})^{A_{n−1}} (except that s ∈ S_{D} \ {s̃_{0}, s_{1}}).

So suppose that λ \ μ has no upper peaks. Let μ = (μ_{1}, …, μ_{l}). Then (the paths corresponding to) λ and μ coincide from (0, 0) up to a certain point P_{0} = (r + s, r − s), and to the right of this point all the steps of λ are up. So λ\μ ≈ δ_{n−1−r−s} \μ̃ where μ̃ =^{def} (μ_{r+1}, …, μ_{l}). In particular, by Lemma 2.11, there exists s ∈ {s̃_{0}, s_{1}} such that s ∈ D(v) (more precisely, s = s̃_{0} if λ has an odd number of up-steps and s = s_{1} if λ has an even number of up-steps). Furthermore, Λ_{D}(vs) = λ_{−}.

Let w ∈ W^{J} be such that u ≤ w < vs and ws < w, and ν =^{def} Λ_{D}(w). Then from Lemma 2.11 we have that the last step of ν is up and the number of up-steps of ν is of the same parity as that of λ. Since l(vs) < l(v), we conclude from our induction hypothesis that if μ(w, vs) ≠ 0 then λ_{−} \ ν is s-Dyck and dp(λ_{−} \ ν) = 1. This implies that the vertical distance between the (right end of the) (n − 1)-th step of λ_{−} and the (right end of the) (n − 1)-th step of ν is zero (else d_{λ_{−}\ν}(n − 2) > d_{λ_{−}\ν}(n − 1) > 0, which contradicts the fact that λ_{−} \ ν is s-Dyck and dp(λ_{−} \ ν) = 1). But this implies that ν has a number of up-steps which is of different parity than that of λ, which is a contradiction. This shows that μ(w, vs) = 0. Therefore

∑_{\{u≤w<vs: ws<w\}} μ(w, vs)q^{\frac{l(w,v)}{2}} P_{u,w}^{J} = 0.

Hence, we conclude from Proposition 2.2 that

P_{u,v}^{J} = \{ \begin{matrix}P_{us,vs}^{J} + qP_{u,vs}^{J}, & if us < u, \\ qP_{us,vs}^{J} + P_{u,vs}^{J}, & if u < us ∈ W^{J}, \\ 0, & if u < us ∉ W^{J}. \end{matrix}  (23)

There are now three cases to consider.

i) u < us ∉ W^{J}.

Assume that λ \ μ is s-Dyck.

If u(2) > 0 then, by Proposition 2.10, the last ((n − 1)-th) step of μ is down. Furthermore, since u ∈ W^{J}, u(1) < 0 if s = s̃_{0} while u(1) > 0 if s = s_{1}. Hence, by Proposition 2.10, μ has an odd number of up-steps if s = s̃_{0} and an even number of up-steps if s = s_{1}. Hence the last part of μ is ≥ 2 and μ has a number of up-steps of the same parity as that of λ. Therefore l(μ̃) ≡ n − 1 − r − s (mod 2), and this contradicts Lemma 3.7.

If u(2) < 0 then the last step of μ is up and μ has a number of up-steps of different parity as that of λ. Hence μ_{l} = 1 and l(μ̃) ≢ n − 1 − r − s (mod 2). This, by Lemma 3.7, is a contradiction.

Hence λ \ μ is not s-Dyck, and the result follows in this case.

ii) u < us ∈ W^{J}.

Then, since u ∈ W^{J}, u(2) > 0. Hence the last step of μ is down and reasoning as above we conclude that μ has a number of up-steps of different parity as that of λ. Therefore, the last part of μ is ≥ 2 and l(μ̃) ≢ n − 1 − r − s (mod 2). Also, Λ_{D}(us) = μ_{+}.

Suppose λ \ μ is s-Dyck. Then, by Lemmas 3.7 and 3.9, λ_{−} \ μ is s-Dyck if and only if μ_{l} = 2 while λ_{−} \μ_{+} is s-Dyck if and only if μ_{l} ≥ 4. Therefore we conclude from (23) and our induction hypothesis that

P_{u,v}^{J} = \{ \begin{matrix}q^{\frac{1}{2} (|λ_{−}\μ|−dp(λ_{−}\μ))}, & if λ_{−} \ μ is s-Dyck, \\ qq^{\frac{1}{2} (|λ_{−}\μ_{+}|−dp(λ_{−}\μ_{+}))}, & if λ_{−} \ μ_{+} is s-Dyck. \end{matrix}

But, by Lemmas 3.7 and 3.9,

dp(λ_{−} \ μ) = dp(λ \ μ) − 1,

if μ_{l} = 2, while

dp(λ_{−} \ μ_{+}) = ⌈\frac{n − 1 − r − s − l(μ̃) − 1}{2}⌉ + dp((3, 2) \ (1, 0)) − 1
= ⌈\frac{n − 1 − r − s − l(μ̃)}{2}⌉
= dp(λ \ μ)

if μ_{l} ≥ 4, so the result holds in this case.

Suppose now that λ \ μ is not s-Dyck. Then λ_{−} \ μ is not s-Dyck (else, by Lemma 3.9, μ̃ would be almost even), and λ_{−} \ μ_{+} is not s-Dyck (else, by Lemma 3.9, μ̃_{+} would be almost even) so, by induction, the result again holds.

iii) us < u.

Then, by Lemma 2.11, the last step of μ is up and μ has a number of up-steps of the same parity as that of λ, while Λ_{D}(us) = μ_{−}. Hence μ_{l} = 1 and l(μ̃) ≡ n − 1 − r − s (mod 2).

Suppose λ \ μ is s-Dyck. Then, by Lemmas 3.7, and 3.9, λ_{−} \ μ is s-Dyck if and only if μ_{l−1} ≥ 4 while λ_{−} \ μ_{−} is s-Dyck if and only if μ_{l−1} = 2. Therefore we conclude from (23) and our induction hypothesis that

P_{u,v}^{J} = \{ \begin{matrix}q^{\frac{1}{2} (|λ_{−}\μ_{−}|−dp(λ_{−}\μ_{−}))}, & if λ_{−} \ μ_{−} is s-Dyck, \\ q q^{\frac{1}{2} (|λ_{−}\μ|−dp(λ_{−}\μ))}, & if λ_{−} \ μ is s-Dyck. \end{matrix}

But, by Lemma 3.9

dp(λ_{−} \ μ_{−}) = ⌈\frac{n − 1 − r − s − l(μ̃) + 1}{2}⌉ − 1 = dp(λ \ μ)

if λ_{−} \ μ_{−} is s-Dyck, while

dp(λ_{−} \ μ) = ⌈\frac{n − 1 − r − s − l(μ̃)}{2}⌉ + dp((3, 2) \ (1, 0)) − 1 = 1 + dp(λ \ μ)

if λ_{−} \ μ is s-Dyck, so the result holds in this case.

Suppose now that λ \ μ is not s-Dyck. Then λ_{−} \ μ is not s-Dyck (else, by Lemma 3.9, μ would be almost even) and λ_{−} \ μ_{−} is not s-Dyck (else, by Lemma 3.9, μ would be almost even) so, by (23) and our induction hypothesis, the result again holds.

This concludes the induction step and hence the proof. □

We illustrate the preceding theorem with an example. Let W^{J} = (S_{6}^{B})^{A_{5}}, u = [−2, 3, 4, −1, 5, 6], v = [−4, −3, 5, −2, −1, 6]. Then Λ_{B}(u) = (4, 1) and Λ_{B}(v) = (5, 4, 2, 1) so, by Theorem 4.1 and our definitions, P_{u,v}^{J,q}(q) = q^{\frac{1}{2} (7−1)} = q^{3}. On the other hand, if W^{J} = (S_{6}^{D})^{A_{5}}, then Λ_{D}(u) = (3) and Λ_{D}(v) = (4, 3, 1) so by Theorem 4.1 and our definitions P_{u,v}^{J,q}(q) = 0.

We now consider the Hermitian symmetric pairs (S_{n}^{B}, B_{n−1}) and (S_{n}^{D}, D_{n−1}).

Theorem 4.2 Let u, v ∈ (S_{n}^{B})^{B_{n−1}}, u ≤ v. Then

P_{u,v}^{J,q}(q) = \{ \begin{matrix}1, & if l(u, v) ≤ 1, \\ 0, & otherwise. \end{matrix}

Proof. We proceed by induction on l(u, v), the result being clear if l(u, v) ≤ 1. So assume that l(u, v) ≥ 2. Then from [7, Proposition 3.1], [5, Theorem 3.2], [8, Corollary 2.2], and our induction hypothesis we have that

q^{l(u,v)}P_{u,v}^{J,q} (\frac{1}{q}) − P_{u,v}^{J,q}(q) = (−1)^{l(u,c)}(1 − q) + (−1)^{l(u,v)}(1 − q)

where c is the only element of [u, v]^{J} covered by v, and the result follows. □

Recall the notation v_{εi} (ε ∈ {−1, 1}, i ∈ [n]) introduced in §2 for the elements of (S_{n}^{D})^{D_{n−1}}.

Theorem 4.3 Let u, v ∈ (S_{n}^{D})^{D_{n−1}}, u < v, l(u, v) ≥ 2. Then

P_{u,v}^{J,q}(q) = \{ \begin{matrix}q^{l(v)−n}, & if 1 ≤ 2n − l(u) − l(v) ≤ 2, \\ 0, & otherwise. \end{matrix}

Proof. We proceed by induction on l(u, v), the result being easy to check if l(u, v) = 2. So assume l(u, v) ≥ 3. If [u, v]^{J} is a chain then 2n − l(u) − l(v) ∉ {1, 2} and the result follows as in Theorem 4.2. If [u, v]^{J} is not a chain then there exists i, j ∈ [2, n] such that u = v_{i} and v = v_{−j}. Note that 2n − l(v_{i}) − l(v_{−j}) = i + 2 − j. Then from [7, Proposition 3.1], [5, Theorem 3.3], [8, Corollary 2.2], and our induction hypothesis we conclude that

q^{i+j−2} P_{v_{i},v_{−j}}^{J,q} (\frac{1}{q}) − P_{v_{i},v_{−j}}^{J,q}(q) = ∑_{a=1}^{i−1} R_{v_{i},v_{a}}^{J,q}(q) P_{v_{a},v_{−j}}^{J,q}(q) + ∑_{b=1}^{j} R_{v_{i},v_{−b}}^{J,q}(q) P_{v_{−b},v_{−j}}^{J,q}(q)
= ∑_{a∈[i−1]∩{j−1,j}} R_{v_{i},v_{a}}^{J,q}(q) q^{j−2} + R_{v_{i},v_{−j}}^{J,q}(q) + R_{v_{i},v_{−(j−1)}}^{J,q}(q)

= \{ \begin{matrix}−(1 − q) + (1 − q)(1 − q^{i−1}), & if j = i + 1, \\ (q − 1) q^{i−2} + (1 − q)(1 − q^{i−1}) + q − 1, & if j = i, \\ 0, & otherwise, \end{matrix}

and the result follows. □

Note that from Proposition 2.3 we have that P_{u,v}^{J,−1}(q) = P_{w_{0}(J)u,w_{0}(J)v}(q) for all u, v ∈ W^{J} and all Hermitian symmetric pairs (W, W_{J}). On the other hand, the polynomials P_{w_{0}(J)u,w_{0}(J)v}(q) have been computed (for u, v ∈ W^{J} and (W, W_{J}) a Hermitian symmetric pair) in [3]. Thus, the results in this section, together with the main result of [4], complete the computation of the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs.

Corollary 4.4 Let (W, W_{J}) be a Hermitian symmetric pair and u, v ∈ W^{J}, u ≤ v. Then P_{u,v}^{J,q}(q) is either zero or a monic power of q.

Proof. This follows immediately from Theorems 4.1, 4.2, and 4.3, the main result of [4, §5], and computer calculations. □

The parabolic Kazhdan-Lusztig polynomials for the exceptional Hermitian symmetric pairs have been computed by implementing in Maple 6 the recursions given by [7, Proposition 3.1]. These implementations used two Maple packages for handling finite Coxeter groups (Version 2.3) and posets (Version 2.2) developed by John Stembridge.

In the case of lower intervals, more can be said.

Corollary 4.5 Let (W, W_{J}) be a Hermitian symmetric pair and v ∈ W^{J}. If P_{e,v}^{J,q}(q) ≠ 0 then

P_{e,v}^{J,q}(q) = q^{∑_{j∈T (v)}(j−1)},

where T (v) has the same meaning as in [5, Corollary 3.5].

Proof. If W^{J} = (S_{n})^{S_{B}\{s_{0},s_{i}}} for some i ∈ [n − 1] then the result follows immediately from Corollaries 5.2 and 3.5 of [4]. Assume now that W^{J} ∈ {(S_{n}^{B})^{A_{n−1}}, (S_{n}^{D})^{A_{n−1}}}. Let λ =^{def} Λ(v) (notation as in Theorem 4.1). We claim that λ is s-Dyck if and only if λ = δ_{i} for some i ≡ 1 (mod 2). It follows immediately from our definitions that δ_{i} is s-Dyck if i is odd, and that dp(δ_{i}) = \frac{i+1}{2}. Conversely, suppose λ = (λ_{1}, λ_{2}, …) is s-Dyck. We proceed by induction on λ_{1}, our claim being easy to check if λ_{1} ≤ 2. So suppose λ_{1} ≥ 3. Let θ be the outer border strip of λ. Since λ \ θ_{S} is s-Dyck we conclude from our induction hypothesis that λ \ θ_{S} = δ_{i} for some i ≡ 1 (mod 2). Therefore, since λ is s-Dyck, λ = δ_{i+2}. Hence, by Theorem 4.1, we conclude that Λ(v) = δ_{i} for some i odd, and the result follows from Corollary 3.7 of [5] and Theorem 4.1. Finally, for the other Hermitian symmetric pairs the result follows immediately from Theorems 3.2 and 3.3 of [5], Theorems 4.2 and 4.3 and from computer calculations. □

The results in this section, and simple examples, show that (as for the polynomials R_{u,v}^{J,q}(q), see the comments following Corollary 3.5 of [5]) given a Hermitian symmetric pair (W, W_{J}) and u, v ∈ W^{J} there may not exist w ∈ W^{J} such that P_{u,v}^{J,q}(q) = P_{e,w}^{J,q}(q).

Let w_{0}^{J} be the longest element of W^{J}. For a finite Coxeter group W let E(W) ⊂ P be its set of exponents.

Corollary 4.6 Let (W, W_{J}) be a Hermitian symmetric pair. Then there exists e ∈ E(W) such that, for all v ∈ W^{J}, if P_{v,w_{0}^{J}}^{J,q} (q) ≠ 0 then

P_{v,w_{0}^{J}}^{J,q} (q) = q^{(e−1)r},

for some r ∈ N.

Proof. If W^{J} = (S_{n})^{S_{B}\{s_{0},s_{i}}} for some i ∈ [n−1] then the result follows directly from Corollary 4.4. Assume now that W^{J} ∈ {(S_{n}^{B})^{A_{n−1}}, (S_{n+1}^{D})^{A_{n}}}. Let μ =^{def} Λ(v). By Theorem 4.1 we have that P_{v,w_{0}^{J}}^{J,q} (q) ≠ 0 if and only if δ_{n} \ μ is s-Dyck. But it is easy to see from the proof of Lemma 3.7, by induction on n, that if δ_{n} \μ is s-Dyck then |δ_{n} \μ| ≡ dp(δ_{n} \μ) (mod 4), and the result follows from Theorem 4.1 (with e = 3). Finally, the result follows immediately from Theorems 4.2 and 4.3 and from computer calculations (with e = 4 and e = 5) for the other Hermitian symmetric pairs. □

It is a long standing open problem in the theory of Kazhdan-Lusztig polynomials to decide if they depend only on the poset isomorphism class of the interval determined under Bruhat order by the elements that index them (see, e.g., [2, §5.6, p.161]). It is therefore natural to ask the same question for the parabolic Kazhdan-Lusztig polynomials. We conclude this section by showing, using the previous results, that this is true for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs.

We need first the following purely combinatorial result on skew shifted partitions. Let θ be a skew shifted partition and E(θ) be the set of all elements x ∈ θ such that θ \ {x} is connected, |{a ∈ θ : a ⊲ x}| ≤ 1, and |{a ∈ θ : a ⊳ x}| ≤ 1. Note that |E(θ)| depends only on the isomorphism class of θ as a poset.

Lemma 4.7 Let θ, η be two connected skew shifted partitions that are isomorphic as posets, |θ| ≥ 4. Then:

i) either θ ≈ η or θ ≈ η′, if |E(θ)| = 2;

ii) θ ≈ η if |E(θ)| ≥ 3.

Proof. Clearly, the leftmost and rightmost cells of θ are in E(θ). Let x be a cell of E(θ) that is neither the leftmost cell, nor one of the rightmost cells, of θ. Then necessarily

|{a ∈ θ : a ⊲ x}| = |{a ∈ θ : a ⊳ x}| = 1.

Let a (respectively, b) be the only element of θ that covers (respectively, covered by) x. Then a and b must lie on opposite sides of x (else x would be either the leftmost cell, or one of the rightmost cells, of θ). Hence θ \ {x} is not connected, which is a contradiction since x ∈ E(θ). This shows that E(θ) consists exactly of the leftmost and rightmost cells of θ.

If |E(θ)| = 2 then θ is a finite convex subset of P^{2} (i.e., a skew partition) and the result follows from Lemma 5.5 of [4].

So assume |E(θ)| ≥ 3. Then θ has at least two rightmost cells. Let, for y ∈ E(θ), n(y) =^{def} |{x ∈ E(θ) \ {y} : x is comparable to y}|. Note that the rightmost cells of θ are a chain while the leftmost cell of θ is comparable to at most two rightmost cells of θ. Therefore n(1) ≤ 2 while n(y) ≥ |E(θ)| − 2 if y is any rightmost cell of θ. There are now two cases to distinguish.

If there is a unique element y ∈ E(θ) such that

n(y) = min{n(x) : x ∈ E(θ)},  (24)

then y is the leftmost cell of θ. Let (a_{1}, b_{1}, …, a_{r}, b_{r}), (c_{1}, d_{1}, …, c_{s}, d_{s}) be the polygon notation of θ introduced in §2. Let x_{1} be the maximal element of θ which is closest to y (in the sense of the distance in the Hasse graph of θ). Then the distance between y and x_{1} is a_{1} − 1. Now let y_{1} be the upper valley of θ which is closest to x_{1}. Then the distance between x_{1} and y_{1} is b_{1}. Now let x_{2} be the closest element to y_{1} among the maximal elements of θ which are different from x_{1}. Then the distance between x_{2} and y_{1} is a_{2}. Continuing in this way we obtain a sequence x_{1}, y_{1}, …, y_{r−1}, x_{r} of elements of θ such that y_{1}, …, y_{r−1} are all the upper valleys of θ. Let y_{r} be the element of E(θ) \ {y} which is closest to x_{r}. Then the distance between x_{r} and y_{r} is b_{r} − 1. This shows that the sequence (a_{1}, b_{1}, …, a_{r}, b_{r}) depends only on the isomorphism class of θ as a poset. Similarly, we obtain the same conclusion for (c_{1}, d_{1}, …, c_{s}, d_{s}), and the result follows.

If there is more than one element y such that (24) holds then 4 ≥ |E(θ)|. If |E(θ)| = 3 then either θ ≈ (k, l) or θ ≈ (δ_{k} \ (k − 1, k − 2, …, l + 1, l − 1, …, 3, 2, 1)) for some k > l > 0, k ≥ 3. If θ has exactly one maximal and one minimal element then k = l + 1 and the result follows. Otherwise |θ| = k + l and 2(l − 1) is the number of elements of θ of degree 3, so k and l depend only on the isomorphism class of θ as a poset, and the result again follows. If |E(θ)| = 4 then n(1) = 2 and θ ≈ (3, 2, 1). Hence, in any case, we conclude that θ ≈ η. □

We can now prove that parabolic Kazhdan-Lusztig and R-polynomials of Hermitian symmetric pairs are combinatorial invariants. Recall the notation Λ(u) defined before Theorem 4.1 for u ∈ W^{J} and W^{J} ∈ {(S_{n}^{B})^{A_{n−1}}, (S_{n}^{D})^{A_{n−1}}}, and the identification between shifted partitions and lattice paths pointed out after Proposition 2.5.

Corollary 4.8 Let (W, W_{J}) be a Hermitian symmetric pair, and u, v, w, z ∈ W^{J} be such that [u, v]^{J} ≅ [w, z]^{J} (as posets). Then

P_{u,v}^{J,q}(q) = P_{w,z}^{J,q}(q)

(and hence also R_{u,v}^{J,q}(q) = R_{w,z}^{J,q}(q), R_{u,v}^{J,−1}(q) = R_{w,z}^{J,−1}(q), and P_{u,v}^{J,−1}(q) = P_{w,z}^{J,−1}(q)).

Proof. If W^{J} = (S_{n})^{S_{B}\{s_{0},s_{i}}} for some i ∈ [n − 1] then the result follows from Corollary 5.6 of [4].

So assume that W^{J} ∈ {(S_{n}^{D})^{A_{n−1}}, (S_{n}^{B})^{A_{n−1}}} for some n ≥ 2. Then by Propositions 2.5, 2.9 and 2.1 we have that [u, v]^{J} ≅ [Λ(u), Λ(v)] ≅ J(Λ(v) \ Λ(u)), and similarly for [w, z]^{J}. Therefore J(Λ(v) \ Λ(u)) ≅ J(Λ(z) \ Λ(w)) and this, by a well known result in the theory of partially ordered sets (see, e.g., [17, Prop. 3.4.2]), implies that Λ(v) \ Λ(u) ≅ Λ(z) \ Λ(w), as posets. Assume first that Λ(v) \ Λ(u) is connected. If |Λ(v) \ Λ(u)| ≤ 3 the result is easy to verify. If |E(Λ(v) \ Λ(u))| ≥ 3 then by Lemma 4.7 we conclude that Λ(v) \ Λ(u) ≈ Λ(z) \ Λ(w) and the result follows from Theorem 4.1. If |E(Λ(v) \ Λ(u))| = 2 then by Lemma 4.7, and its proof, we conclude that either Λ(v) \ Λ(u) ≈ Λ(z) \ Λ(w) or Λ(v) \ Λ(u) ≈ (Λ(z) \ Λ(w))′ and the result follows from Theorem 4.1 and Proposition 3.1. If Λ(v) \ Λ(u) is not connected then the connected components of Λ(v) \ Λ(u) and Λ(z) \ Λ(w) are pairwise isomorphic as posets, and the result follows from the previous considerations, and the fact that a skew shifted partition is s-Dyck if and only if each one of its connected components is s-Dyck.

Finally, for the other Hermitian symmetric pairs the result follows immediately from Theorems 4.2 and 4.3 and from computer calculations. □

5 Applications

In this section we give some consequences of our main results. More precisely, we derive combinatorial closed product formulas for certain alternating sums of ordinary Kazhdan-Lusztig polynomials, and we prove a combinatorial invariance result for certain Kazhdan-Lusztig polynomials studied in [3].

We begin with the following consequence of our main results for the ordinary Kazhdan-Lusztig polynomials.

Corollary 5.1 Let (W, W_{J}) be a Hermitian symmetric pair, and u, v ∈ W^{J}, u ≤ v. Then ∑_{w∈W_{J}} (−1)^{l(w)}P_{wu,v}(q) is either zero or a monic power of q.

Proof. This follows immediately from Corollary 4.4 and Proposition 2.3. □

Note that the exact power of q in Corollary 5.1 is explicitly determined in Theorems 4.1, 4.2 and 4.3, and Theorem 5.1 of [4].

One of the most celebrated conjectures about the Kazhdan-Lusztig polynomials is the socalled “combinatorial invariance conjecture” (see, e.g., [2, p.161], and the references cited there). This conjecture states that the Kazhdan-Lusztig polynomial P_{u,v}(q) depends only on the isomorphism class of [u, v] as a poset. Using Corollary 4.8 we can prove a (slightly different, and computationally simpler) statement for the Kazhdan-Lusztig polynomials studied in [3]. Recall (see, e.g., [2, Prop. 2.4.4]) that given u ∈ W there exist unique elements u_{J} ∈ W_{J} and u^{J} ∈ W^{J} such that u = u_{J}u^{J}. Furthermore, l(u) = l(u_{J}) + l(u^{J}).

Corollary 5.2 Let (W, W_{J}) be a Hermitian symmetric pair and u, v ∈ W be such that D(u), D(v) ⊇ J. Then P_{u,v}(q) depends only on

{x ∈ [u, v] : D(x) ⊇ J}  (25)

as a poset.

Proof. Let w, z ∈ W be such that D(w), D(z) ⊇ J, and suppose that {x ∈ [w, z] : D(x) ⊇ J} is isomorphic to (25) as a poset. We will show that then P_{u,v}(q) = P_{w,z}(q). We claim that

{x ∈ W : D(x) ⊇ J} ≅ W^{J}  (26)

as posets. To see this note first that if x ∈ W then D(x) ⊇ J if and only if w_{0}(J)x^{−1} ∈ W^{J}, and in this case

l(w_{0}(J)x^{−1}) = l(x^{−1}) − l(w_{0}(J)) = l(x) − l(w_{0}(J)).  (27)

In fact, if D(x) ⊇ J then xs < x for all s ∈ J which implies that sx^{−1} < x^{−1} for all s ∈ J. Writing x^{−1} = x_{J}x^{J} with x_{J} ∈ W_{J} and x^{J} ∈ W^{J} we conclude that sx_{J}x^{J} < x_{J}x^{J} for all s ∈ J. But sx_{J} ∈ W_{J} so l(sx_{J}x^{J}) = l(sx_{J}) + l(x^{J}) which implies that l(sx_{J}) < l(x_{J}) for all s ∈ J. Since x_{J} ∈ W_{J} this implies, by well known facts (see, e.g., [2, Prop.2.3.1]) that x_{J} = w_{0}(J). Hence x^{−1} = w_{0}(J)x^{J} so w_{0}(J)x^{−1} ∈ W^{J} and l(x^{−1}) = l(w_{0}(J)) + l(x^{J}). Conversely, if w_{0}(J)x^{−1} ∈ W^{J} then there exists y ∈ W^{J} such that x^{−1} = w_{0}(J)y. Therefore, for any s ∈ J, we have that l(sx^{−1}) = l(sw_{0}(J)y) = l(sw_{0}(J))+l(y) < l(w_{0}(J))+l(y) = l(x^{−1}) so J ⊆ D(x). Also, if x, y ∈ W then yx^{−1} ∈ T if and only if w_{0}(J)(y^{−1}x)w_{0}(J)^{−1} ∈ T. This shows, by the definition of Bruhat order and by the fact that both posets in (26) have the chain property ([2, Thm.2.5.5]), that if x, y ∈ W are such that D(x), D(y) ⊇ J then x ≤ y if and only if w_{0}(J)x^{−1} ≤ w_{0}(J)y^{−1}. Therefore the map x ↦ w_{0}(J)x^{−1} is a poset isomorphism from {x ∈ W : D(x) ⊇ J} to W^{J}. Therefore, in particular, {x ∈ [u, v] : D(x) ⊇ J} ≅ [w_{0}(J)u^{−1}, w_{0}(J)v^{−1}]^{J}. We therefore conclude from our assumptions that [w_{0}(J)u^{−1}, w_{0}(J)v^{−1}]^{J} ≅ [w_{0}(J)w^{−1}, w_{0}(J)z^{−1}]^{J}. This, by Corollary 4.8, Proposition 2.3, and a well known property of the Kazhdan-Lusztig polynomials (see, e.g., [2, Chap. 5, Ex. 12]), implies that P_{u,v}(q) = P_{u^{−1},v^{−1}}(q) = P_{w_{0}(J)u^{−1},w_{0}(J)v^{−1}}^{J,−1}(q) = P_{w_{0}(J)w^{−1},w_{0}(J)z^{−1}}^{J,−1}(q) = P_{w^{−1},z^{−1}} = P_{w,z}(q), as desired. □

Note that Corollary 5.2 generalizes, even for Hermitian symmetric pairs of type A, Corollary 6.3 of [4].

Acknowledgments. Most of the computer calculations in this paper have been carried out using a Maple package for finite Coxeter groups and a Maple package for handling posets developed by John Stembridge. I would like to thank the referee for a thorough and careful reading of the manuscript.

References

[1] A. Björner, private communication, March 1992.

[2] A. Björner, F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, 231, Springer-Verlag, New York, 2005.

[3] B. Boe, Kazhdan-Lusztig polynomials for Hermitian symmetric spaces, Trans. Amer. Math. Soc., 309 (1988), 279-294.

[4] F. Brenti, Kazhdan-Lusztig and R-polynomials, Young’s lattice, and Dyck partitions, Pacific J. Math., 207 (2002), 257-286.

[5] F. Brenti, Parabolic Kazhdan-Lusztig R-polynomials for Hermitian symmetric pairs, preprint.

[6] L. Casian, D. Collingwood, The Kazhdan-Lusztig conjecture for generalized Verma modules, Math. Zeit., 195 (1987), 581-600.

[7] V. Deodhar, On some geometric aspects of Bruhat orderings. II. The parabolic analogue of Kazhdan-Lusztig polynomials, J. Algebra, 111 (1987), 483-506.

[8] V. Deodhar, Duality in parabolic setup for questions in Kazhdan-Lusztig theory, J. Algebra, 142 (1991), 201-209.

[9] J. Haglund, M. Haiman, N. Loehr, A combinatorial formula for Macdonald polynomials, J. Amer. Math. Soc., 18 (2005), 735-761.

[10] J. Haglund, M. Haiman, N. Loehr, J. Remmel, A. Ulyanov, A combinatorial formula for the character of the diagonal coinvariants, Duke Math. J., 126 (2005), 195-232.

[11] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990.

[12] M. Kashiwara, T. Tanisaki, Parabolic Kazhdan-Lusztig polynomials and Schubert varieties, J. Algebra, 249 (2002), 306-325.

[13] D. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math., 53 (1979), 165-184.

[14] B. Leclerc, J.-Y. Thibon, Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials, Adv. Studies Pure Math., 28 (2000), 155-220.

[15] W. Soergel, Kazhdan-Lusztig polynomials and a combinatoric for tilting modules, Represent. Theory, 1 (1997), 83-114.

[16] W. Soergel, Character formulas for tilting modules over Kac-Moody algebras, Represent. Theory, 1 (1997), 115-132.

[17] R. P. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[18] R. P. Stanley, Enumerative Combinatorics , vol.2, Cambridge Studies in Advanced Mathematics, no.62, Cambridge Univ. Press, Cambridge, 1999.

[19] M. Varagnolo, E. Vasserot, On the decomposition matrices of the quantized Schur algebra, Duke Math. J., 100 (1999), 267-297.