Flag-Symmetric and Locally Rank-Symmetric Partially Ordered Sets

Richard P. Stanley^{1}

Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139 e-mail: rstan@math.mit.edu

Submitted: June 15, 1994; Accepted: May 26, 1995

This paper is dedicated to someone who has made

Fascinating Original Approaches To Algebraic combinatorics,

on the occasion of his sixtieth birthday.

Abstract

For every finite graded poset P with ˆ0 and ˆ1 we associate a certain formal power series F_{P} (x) = F_{P} (x_{1}, x_{2}, …) which encodes the flag f-vector (or flag h-vector) of P. A relative version F_{P/Γ} is also defined, where Γ is a subcomplex of the order complex of P. We are interested in the situation where F_{P} or F_{P/Γ} is a symmetric function of x_{1}, x_{2}, . . .. When F_{P} or F_{P/Γ} is symmetric we consider its expansion in terms of various symmetric function bases, especially the Schur functions. For a class of lattices called q-primary lattices the Schur function coefficients are just values of Kostka polynomials at the prime power q, thus giving in effect a simple new definition of Kostka polynomials in terms of symmetric functions. We extend the theory of lexicographically shellable posets to the relative case in order to show that some examples (P, Γ) are relative Cohen-Macaulay complexes. Some connections with the representation theory of the symmetric group and its Hecke algebra are also discussed.

1Partially supported by NSF grant #DMS-9206374.

1 Basic definitions.

Let P be a finite graded poset of rank n, with ˆ0 and ˆ1. (For undefined poset terminology, see [26].) Let ρ denote the rank function of P, so ρ(ˆ0) = 0 and ρ(ˆ1) = n. Write ρ(s, t) = ρ(t) − ρ(s) when s ≤ t in P. R. Ehrenborg [9, Def. 3] suggested looking at the formal power series (in the variables x = (x_{1}, x_{2}, …))

F_{P} (x) = ∑_{ˆ0=t_{0}≤t_{1}≤···≤t_{k−1}<t_{k}=ˆ1} x_{1}^{ρ(t_{0},t_{1})}x_{2}^{ρ(t_{1},t_{2})} ⋯ x_{k}^{ρ(t_{k−1},t_{k})},  (1)

where the sum is over all multichains from ˆ0 to ˆ1 such that ˆ1 occurs exactly once. It is easily seen that F_{P} (x) makes sense as a formal power series, i.e., the coefficient of every monomial is finite. (If we had summed over arbitrary multichains ˆ0 = t_{0} ≤ t_{1} ≤ ⋯ ≤ t_{k−1} ≤ t_{k} = ˆ1, then we would obtain infinite coefficients.) Our main concern in this paper will be with posets P for which F_{P} (x) is a symmetric function of x. Such a poset P we say is flag-symmetric. We now explain the reason for this terminology.

For any integer m ≥ 1, let [m] = {1, 2, …, m}. Write S = {m_{1}, …, m_{j}}_{<} to mean that S = {m_{1}, …, m_{j}} and m_{1} < ⋯ < m_{j}. If S = {m_{1}, …, m_{j}}_{<} ⊆ [n − 1], then define α_{P} (S) to be the number of chains ˆ0 < t_{1} < ⋯ < t_{j} < ˆ1 in P such that S = {ρ(t_{1}), …, ρ(t_{j})}. The function α_{P} is called the flag f-vector of P (sometimes denoted f̃_{P}).

We will use symmetric function notation and terminology from Macdonald [15]. In particular, m_{λ} denotes the monomial symmetric function and s_{λ} the Schur function indexed by the partition λ of n (denoted λ ⊢ n or |λ| = n).

1.1 Proposition. Let P be as above. Then

F_{P} (x) = ∑_{{S=\{m_{1},...,m_{j} \}< \atop S⊆[n−1]}} ∑_{1≤i_{1}<···<i_{j+1}} x_{i_{1}}^{m_{1}}x_{i_{2}}^{m_{2}−m_{1}} ⋯ x_{i_{j+1}}^{n−m_{j}}α_{P} (S).  (2)

In particular, P is flag-symmetric if and only if

F_{P} (x) = ∑_{λ⊢n} α_{P} (S_{λ})m_{λ},  (3)

where if λ = (λ_{1}, …, λ_{ℓ}) with λ_{ℓ} > 0, then S_{λ} = {λ_{1}, λ_{1} +λ_{2}, …, λ_{1} +λ_{2} +⋯+λ_{ℓ−1}}.

Proof. Equation (2) is an immediate consequence of (1) (by considering the support of the multichain ˆ0 = t_{0} ≤ t_{1} ≤ ⋯ ≤ t_{k−1} < t_{k} = ˆ1), while (3) follows immediately from (2). □

1.2 Corollary. Let P be as above. Then P is flag-symmetric if and only if for all S = {m_{1}, …, m_{j}}_{<} ⊆ [n − 1], we have that α_{P} (S) depends only on the multiset {m_{1}, m_{2} − m_{1}, m_{3} − m_{2}, …, n − m_{j}}, not on the order of its elements.

For instance, if n = 4 then P is flag-symmetric if and only if α(1) = α(3) and α(1, 2) = α(1, 3) = α(2, 3).

An important function related to the flag f-vector α_{P} is the flag h-vector β_{P} (sometimes denoted h̃_{P}), defined for all S ⊆ [n − 1] by

β_{P} (S) = ∑_{T ⊆S}(−1)^{|S−T |}α_{P} (T).  (4)

Equivalently,

α_{P} (S) = ∑_{T ⊆S} β_{P} (T).  (5)

The flag h-vector often has combinatorial or algebraic significance. See for example [26, §3.12] for the combinatorial significance. If P is a Cohen-Macaulay poset (defined in [4] or [26, p. 123]), then β_{P} (S) is the dimension of a certain homology group and is therefore nonnegative. In general, however, β_{P} (S) may be negative. For instance, if P consists of two disjoint 2-element chains with a ˆ0 and ˆ1 adjoined, then P is flag-symmetric and β_{P} (1, 2) = −1.

We would like to express F_{P} (x) in terms of the flag h-vector β_{P}. To do this, let S ⊆ [n−1] and following Gessel [10] define a homogeneous power series G(x) of degree n (say with rational coefficients) in the variables x = (x_{1}, x_{2}, …) to be quasisymmetric if x_{i_{1}}^{a_{1}} ⋯ x_{i_{k}}^{a_{k}} has the same coefficient as x_{j_{1}}^{a_{1}} ⋯ x_{j_{k}}^{a_{k}} whenever i_{1} < ⋯ < i_{k} and j_{1} < ⋯ < j_{k}. Thus every symmetric function is quasisymmetric, but not conversely. For instance, ∑_{i<j} x_{i}x_{j}^{2} is quasisymmetric but not symmetric. Given S ⊆ [n − 1], define the quasisymmetric function Q_{S,n}(x) by

Q_{S,n}(x) = ∑_{{1≤a_{1}≤a_{2}≤···≤an \atop a_{i}<a_{i+1}if i∈S}} x_{a_{1}}x_{a_{2}} ⋯ x_{a_{n}}.  (6)

Sometimes we write Q_{S} for Q_{S,n} when it is clear that we are dealing with power series of degree n. It is easy to see that the Q_{S,n}’s form a linear basis for the space of all quasisymmetric functions of degree n with rational coefficients, so this space has dimension 2^{n−1}.

1.3 Proposition. Let P be as above. Then

F_{P} (x) = ∑_{S⊆[n−1]} β_{P} (S)Q_{S}(x).

Proof. In view of (2) and (5) we need to show that for each T ⊆ [n − 1],

∑_{{S⊇T \atop S=\{m_{1},...,m_{j} \}<}} ∑_{1≤i_{1}<···<i_{j+1}} x_{i_{1}}^{m_{1}}x_{i_{2}}^{m_{2}−m_{1}} ⋯ x_{i_{j+1}}^{n−m_{j}} = Q_{T} (x).

But this is a routine verification, looking at all possible ways of choosing each symbol ≤ to be either < or = in the definition (6). □

There is a generalization of flag-symmetric functions which will arise in a natural way in Sections 4 and 5. Given a poset P with ˆ0 and ˆ1, define its reduced order complex Δ̃(P) to be the set of chains of P − {ˆ0, ˆ1}, regarded as an abstract simplicial complex (see e.g. [26, p. 120]). Let Γ be a subcomplex of Δ̃(P), i.e., a subset of Δ̃(P) such that if σ ∈ Γ and σ′ ⊂ σ, then σ′ ∈ Γ. (Thus Ø ∈ Γ unless Γ = Ø.) The pair (Δ̃(P), Γ) is an instance of a relative simplicial complex [27, p. 205], and the set

Δ̃(P)/Γ = {σ : σ ∈ Δ̃(P), σ ∉ Γ}

is a cocomplex, i.e., a collection C of sets such that if σ, τ ∈ C and σ ⊆ σ′ ⊆ τ, then σ′ ∈ C. A cocomplex is simply a convex subset (in the sense of [26, p. 98]) of a boolean algebra. We will write simply P/Γ for Δ̃(P)/Γ and call P/Γ a P -cocomplex.

We can extend the definition of F_{P} (x), α_{P} (S), and β_{P} (S) in an obvious way to F_{P/Γ}(x), α_{P/Γ}(S), and β_{P/Γ}(S). Namely, in (1) we sum only over multichains whose support, with ˆ0 and ˆ1 removed, is contained in Δ̃(P)/Γ, while α_{P/Γ}(S) counts only chains in Δ̃(P)/Γ for which the ranks of their elements are the elements of S. We define β_{P/Γ}(S) in exact analogy with (4) or (5). Proposition 1.1, Corollary 1.2, and Proposition 1.3 continue to hold with P replaced with P/Γ. As before, if F_{P/Γ} is a symmetric function then we say that the cocomplex P/Γ is flag-symmetric.

We now give a simple sufficient condition for a poset P to be flag-symmetric. A graded poset P_{0} ∪ P_{1} ∪ ⋯ ∪ P_{n} of rank n is called rank-symmetric if p_{i} = p_{n−i} for all i, where p_{i} = #P_{i}. A graded poset P with ˆ0 and ˆ1 is called locally rank-symmetric if every interval is rank-symmetric. In particular, P is locally rank-symmetric if it is locally self-dual, i.e., every interval is self-dual.

1.4 Theorem. A locally rank-symmetric poset P (which is assumed to be finite, graded, with ˆ0 and ˆ1) is flag-symmetric.

Proof. It is convenient, though not necessary, to use the language of incidence algebras. Let I(P) denote the incidence algebra of P, say over the real numbers, as defined in [26, Ch. 3.6]. Let η_{j} ∈ I(P) be defined by

η_{j}(s, t) = \{ \begin{matrix}1, & if ρ(s, t) = j \\ 0, & otherwise. \end{matrix}

The statement that P is locally rank-symmetric is equivalent to the fact that η_{j}η_{k} = η_{k}η_{j} for all j, k. Now note that if j_{1} +⋯+j_{r} = n, where j_{i} > 0, then η_{j_{1}} ⋯ η_{j_{r}}(ˆ0, ˆ1) = α_{P} (S), where S = {j_{1}, j_{1} + j_{2}, …, j_{1} + ⋯ j_{r−1}}. If the η_{j}’s commute then η_{j_{1}} ⋯ η_{j_{r}} is independent of the order of the factors, and evaluating at [ˆ0, ˆ1] yields flag-symmetry by Corollary 1.2. □

Note. The above proof is essentially the same as that appearing in [26, solution to Exercise 3.65].

Local rank-symmetry seems to be the most general “natural” condition for a poset P to be flag-symmetric. A poset could “accidentally” have a flag f-vector which would make it flag-symmetric, but local rank-symmetry forces every interval to be well-behaved, not just the entire poset. Note that P is locally rank-symmetric if and only if it is locally flag-symmetric, i.e., every interval is flag-symmetric.

We wish to give a generalization of Theorem 1.4 to P -cocomplexes. First we must come up with the correct definition of a locally rank-symmetric P -cocomplex. For this definition to make sense, it will be necessary to consider a restricted class of subcomplexes Γ of Δ̃(P). Let X be an order ideal of non-singleton intervals of P, i.e., a collection of intervals [s, t] with s < t such that if [s, t] ∈ X and s ≤ u < v ≤ t, then [u, v] ∈ X. Define Γ = Γ_{X} to consist of all chains t_{1} < t_{2} < ⋯ < t_{r−1} of P − {ˆ0, ˆ1} such that if we also set t_{0} = ˆ0 and t_{r} = ˆ1, then [t_{i−1}, t_{i}] ∉ X for some 1 ≤ i ≤ r. Note that since X is an order ideal of non-singleton intervals, Γ_{X} is a subcomplex of Δ̃(P). We then call P/Γ_{X} a simple P -cocomplex. Define a simple P -cocomplex P/Γ_{X} to be locally rank-symmetric if for all s < t in P and all 0 < i < ρ(s, t), the number of u ∈ [s, t] for which ρ(s, u) = i, [s, u] ∈ X, and [u, t] ∈ X is equal to the number of v ∈ [s, t] for which ρ(s, v) = ρ(s, t) − i, [s, v] ∈ X, and [v, t] ∈ X.

1.5 Theorem. A locally rank-symmetric simple P -cocomplex P/Γ_{X} is flag-sym-metric.

Proof. Just as in the proof of Theorem 1.4, define η_{j} = η_{j,X} ∈ I(P) by

η_{j}(s, t) = \{ \begin{matrix}1, & if ρ(s, t) = j and [s, t] ∈ X \\ 0, & otherwise. \end{matrix}

The statement that P/Γ_{X} is locally rank-symmetric is equivalent to the fact that η_{j}η_{k} = η_{k}η_{j} for all j, k. Now note that if j_{1} + ⋯ + j_{r} = n where j_{i} > 0, then η_{j_{1}} ⋯ η_{j_{r}}(ˆ0, ˆ1) is equal to the number of chains ˆ0 = t_{0} < t_{1} < ⋯ < t_{r} = ˆ1 in P such that ρ(t_{i−1}, t_{i}) = j_{i} and such that [t_{i−1}, t_{i}] ∈ X for 1 ≤ i ≤ r. This last condition is equivalent to {t_{1}, …, t_{i}} ∉ Γ_{X}, so η_{j_{1}} ⋯ η_{j_{r}}(ˆ0, ˆ1) = α_{P/Γ_{X}}(S), where S = {j_{1}, j_{1} + j_{2}, …, j_{1} + ⋯ + j_{r−1}}. Just as in the proof of Theorem 1.4, we conclude that P/Γ_{X} is flag-symmetric. □

2 Schur positivity.

A symmetric function f can be uniquely expanded as a linear combination f = ∑ c_{λ}s_{λ} of Schur functions s_{λ} [15, (3.3) on p. 24]. We say that f is Schur positive if each c_{λ} ≥ 0. When P (or more generally P/Γ) is flag-symmetric, it is natural to expand F_{P} in terms of Schur functions and ask what can be said about the coefficients c_{λ} = ⟨F_{P} , s_{λ}⟩ (where ⟨·, ·⟩ denotes the usual scalar product on symmetric functions [15, p. 34]).

2.1 Proposition. If F_{P} (or F_{P/Γ}) is Schur positive then β_{P} (S) ≥ 0 (or β_{P/Γ}(S) ≥ 0) for all S ⊆ [n − 1].

Proof. Immediate from Proposition 1.3 and the fact (a consequence, e.g., of [10, Thm. 3 and Thm. 7]) that s_{λ} is a nonnegative linear combination of the Q_{S,n}’s. □

2.2 Proposition. If F_{P} is Schur positive then P is rank-unimodal, i.e., p_{0} ≤ p_{1} ≤ ⋯ ≤ p_{⌊n/2⌋}. (Thus p_{⌊n/2⌋} = p_{⌈n/2⌉} ≥ p_{⌈n/2⌉+1} ≥ ⋯ ≥ p_{n} since p_{i} = p_{n−i}).

Proof. It is easy to compute that for 0 ≤ 2i ≤ n, the coefficient of s_{n−i,i} in F_{P} is α_{P} (i) − α_{P} (i − 1) (where α_{P} (0) = 1). Since α_{P} (j) = p_{j}, the proof follows. □

It is easy to find examples of locally rank-symmetric posets P for which β_{P} (S) < 0 for some S, and hence by Proposition 2.1 F_{P} is not Schur positive. For instance, P can be any disjoint union of at least two chains with the same number m ≥ 2 of elements, with a ˆ0 and ˆ1 adjoined. In fact, Bill Doran has given an example of a locally rank-symmetric (in fact, locally self-dual) poset P of rank 4 which is not rank-unimodal. This poset satisfies F_{P} = m_{4} + 13m_{31} + 12m_{22} + 24m_{211} + 36m_{1111} = s_{4} + 12s_{31} − s_{22} + s_{1111}. Recall, however, that we mentioned in the previous section that Cohen-Macaulay posets P do satisfy β_{P} (S) ≥ 0. More generally, there is a notion [27, p. 205] of a Cohen-Macaulay cocomplex Δ/Γ (or equivalently a relative Cohen-Macaulay simplicial complex (Δ, Γ)). This suggests the following conjecture.

2.3 Conjecture. Let P/Γ be a flag-symmetric Cohen-Macaulay P -cocomplex. Then F_{P/Γ} is Schur positive.

Possibly the hypothesis that P/Γ is flag-symmetric and Cohen-Macaulay in Conjecture 2.3 is too weak. The correct hypothesis may be that P/Γ is locally ranksymmetric and Cohen-Macaulay.

Besides checking numerous examples (see Section 3), we have a small additional piece of evidence for Conjecture 2.3. Suppose that P/Γ is flag-symmetric of rank ab, where a, b > 1. Define a cocomplex T_{a}(P/Γ) by

T_{a}(P/Γ) = {t ∈ P/Γ : ρ(t) is divisible by a}.

Thus T_{a}(P/Γ) is a T_{a}(P)-cocomplex, and T_{a}(P/Γ) has rank b. Moreover,

α_{T_{a}(P/Γ)}(c_{1}, …, c_{i}) = α_{P/Γ}(ac_{1}, …, ac_{i}).  (7)

It follows that T_{a}(P/Γ) is also flag-symmetric. When Γ = Ø, T_{a}(P) is a rank-selected subposet of P [4, §0][26, Ch. 3.12]. Hence by [4, Thm. 5.2] or [25, Thm. 5.3], T_{a}(P) is Cohen-Macaulay whenever P is Cohen-Macaulay. By similar reasoning, T_{a}(P/Γ) is Cohen-Macaulay whenever P/Γ is Cohen-Macaulay.

Define a linear operator T_{a} on homogeneous symmetric functions of degree ab by

T_{a}(m_{λ}) = \{ \begin{matrix}m_{μ}, & if λ = aμ \\ 0, & otherwise. \end{matrix}

In other words, T_{a}(f) is obtained by writing f as a linear combination of monomials x^{α}, replacing x^{α} with x^{α/a} if α/a has integer coordinates, and otherwise replacing x^{α} with 0. Thus if deg f = ab, then deg T_{a}(f) = b. It follows from (7) that

F_{T_{a}(P/Γ)} = T_{a}(F_{P/Γ}).  (8)

2.4 Theorem. If λ ⊢ ab then T_{a}(s_{λ}) is Schur positive.

Proof. Let s_{λ} = ∑_{μ⊢ab} K_{λμ}m_{μ}, so K_{λμ} is a Kostka number. Thus

T_{a}(s_{λ}) = ∑_{ν⊢b} K_{λ,aν}m_{ν}.

Let ⟨·, ·⟩ denote the usual scalar product on symmetric functions. It follows that for each ρ ⊢ b we have

⟨s_{ρ}, T_{a}(s_{λ})⟩ = ⟨s_{ρ}, ∑_{ν⊢b} K_{λ,aν}m_{ν}⟩
= ⟨s_{ρ}, ∑_{ν}⟨s_{λ}, h_{aν}⟩m_{ν}⟩
= ∑_{ν}⟨s_{ρ}, m_{ν}⟩ · ⟨s_{λ}, h_{aν}⟩
= ⟨s_{λ}, ∑_{ν}⟨s_{ρ}, m_{ν}⟩h_{aν}⟩,

using the bilinearity of the scalar product together with [15, (6.7)(vii) on p. 57].

Consider the algebra endomorphism φ_{a} of the ring of symmetric functions defined by φ_{a}(h_{i}) = h_{ai}. If we apply φ_{a} to the Jacobi-Trudi matrix defining the Schur function s_{ρ} [15, (3.4) on p. 25 and (5.4) on p. 40], then we obtain the Jacobi-Trudi matrix for the skew Schur function of skew shape (aρ + (a − 1)δ)/(a − 1)δ, where if ℓ(ρ) = ℓ then δ = (ℓ − 1, ℓ − 2, …, 1, 0). Hence

φ_{a}(s_{ρ}) = s_{(aρ+(a−1)δ)/(a−1)δ}.

Thus

∑_{ν}⟨s_{ρ}, m_{ν}⟩h_{aν} = φ_{a} (∑_{ν}⟨s_{ρ}, m_{ν}⟩h_{ν})
= φ_{a}(s_{ρ})
= s_{(aρ+(a−1)δ)/(a−1)δ}.

It follows that ⟨T_{a}(s_{λ}), s_{ρ}⟩ is just the Littlewood-Richardson coefficient

⟨T_{a}(s_{λ}), s_{ρ}⟩ = ⟨s_{λ}s_{(a−1)δ}, s_{aρ+(a−1)δ}⟩.

Since such coefficients are always nonnegative [15, (9.2) on p. 68], the proof follows. □

2.5 Corollary. If F_{P/Γ} is Schur positive, then F_{T_{a}(P/Γ)} is also Schur positive.

Proof. Immediate from (8) and Theorem 2.4. □

3 Examples.

In this section we discuss numerous examples of flag-symmetric and locally ranksymmetric posets. The most interesting examples known to us turn out to be distributive and modular lattices, so we will deal with them first.

3.1 Theorem Let L be a finite distributive lattice. The following four conditions are equivalent.

(a) L is locally self-dual.

(b) L is locally rank-symmetric.

(c) L is flag-symmetric.

(d) L is a product of chains.

Proof. It is easy to see that (d) ⇒ (a), while (a) ⇒ (b) is obvious and Theorem 1.4 shows that (b) ⇒ (c). The difficult implication is (c) ⇒ (d), but this is equivalent to Exercise 4.23 of [26] (solution on p. 285). □

We wish to compute F_{L} when L is a product of chains. We use the following lemma, whose proof is an immediate consequence of the relevant definitions.

3.2 Lemma. Suppose that P and Q are flag-symmetric (respectively, locally ranksymmetric). Then the direct product P ×Q is also flag-symmetric (respectively, locally rank-symmetric). Moreover, F_{P ×Q} = F_{P} F_{Q}. □

Let ν = (ν_{1}, ν_{2}, …, ν_{ℓ}) ∈ ℙ^{ℓ}, where ℙ = {1, 2, …}. Let L_{ν} denote the product of chains of lengths ν_{1}, ν_{2}, …, ν_{ℓ}, so #L_{ν} = (ν_{1} + 1)(ν_{2} + 1) ⋯ (ν_{ℓ} + 1), and L_{ν} has rank |ν| = ν_{1} +⋯+ν_{ℓ}. Let h_{ν} denote the complete homogeneous symmetric function h_{ν_{1}}h_{ν_{2}} ⋯ h_{ν_{ℓ}}.

3.3 Proposition. We have F_{L_{ν}} = h_{ν}.

Proof. By Lemma 3.2, it suffices to assume that ℓ = 1 (i.e., L_{ν} is a chain). The proof is now evident from the definition (1) of F_{P}. □

Next we consider the case of modular lattices. All lattices L considered here are assumed to be finite. A (finite) lattice L is semiprimary [14] if L is modular, and whenever t ∈ L is join-irreducible (respectively, meet-irreducible) then the interval [ˆ0, t] (respectively, [t, ˆ1]) is a chain. A semiprimary lattice is primary if every interval is either a chain or contains at least three atoms. We also say that a lattice L is a q-lattice [22, §6] if every complemented interval is isomorphic to a projective geometry of order q (or to a boolean algebra when q = 1). A modular lattice L is a q-lattice if and only if every interval of rank two is either a chain or has q+1 elements of rank one. (A modular 1-lattice is just a distributive lattice). We say that L is q-semiprimary if L is both semiprimary and a q-lattice, and similarly we define q-primary. (Note that a q-semiprimary lattice for q ≥ 2 is in fact q-primary.) Primary lattices have been almost completely classified by Baer, Inaba, and Jónsson-Monk. See [14] for further information. Some interesting recent work on semiprimary lattices appears in [29]. Every primary lattice L of rank n has a well-defined type λ ⊢ n; see [14][29, Def. 4.8] for the definition. The main example of a q-primary lattice is the lattice L_{M} of submodules of a module M of finite length over a discrete valuation ring R with a finite residue class field 𝔽_{q}. Let us call such lattices Hall lattices, since Philip Hall developed their basic enumerative properties, an exposition of which appears in [15, Chs. 2 and 3]. Tesler [29, Thm. 4.81ff] has shown that the enumerative properties of Hall lattices described in [15] carry over to arbitrary q-primary lattices. Two prototypical examples of q-Hall lattices are (a) the lattice of subgroups of a finite

[figure]

Figure 1: A flag-symmetric modular lattice which is not locally rank-symmetric

abelian p-group of type λ = (λ_{1}, …, λ_{ℓ}) (for which R = ℤ_{p}, the p-adic integers, q = p, and M = (ℤ_{p}/p^{λ_{1}}ℤ_{p}) ⊕ ⋯ ⊕ (ℤ_{p}/p^{λ_{ℓ}}ℤ_{p})); and (b) the lattice of submodules of the 𝔽_{q}[[x]]-module M = 𝔽_{q}[[x]]/(x^{λ_{1}}) ⊕ ⋯ ⊕ 𝔽_{q}[[x]]/(x^{λ_{ℓ}}). In both these two examples the Hall lattice L is of type λ. (The two lattices are not isomorphic, e.g., for λ = (2, 2, 2); see [7, Theorem 4 and Lemma 5] for further details.) More generally, the type of a Hall lattice is λ = (λ_{1}, λ_{2}, …), where L = L_{M} and M is a product of cyclic R-modules of lengths λ_{1}, λ_{2}, . . ..

3.4 Theorem. (F. Regonati [20]) Let L be a finite modular lattice . The following three conditions are equivalent.

(a) L is locally rank-symmetric.

(b) Every interval of L of rank three is rank-symmetric.

(c) L is a product P_{1}×P_{2}×⋯×P_{m} of q_{i}-primary lattices P_{i} (including the possibility q_{i} = 0, in which case P_{i} is a chain).

Unlike the case for distributive lattices (Theorem 3.1), a flag-symmetric modular lattice need not be locally rank-symmetric. See Figure 1 for an example. We will now determine the symmetric function F_{L} for a q-primary lattice L (and thus by Lemma 3.2 and Theorem 3.4 for any locally rank-symmetric modular lattice).We assume knowledge of the Hall-Littlewood symmetric functions P_{λ}(x; q) and Q_{λ}(x; q) and of the Kostka polynomials K_{λμ}(q), as defined in [15, Ch. III] (using t instead of q). Following [15, p. 132], we write

K̃_{λμ}(q) = q^{n(μ)}K_{λμ}(q^{−1}),

where n(μ) = ∑(i − 1)μ_{i} = ∑ \binom{μ′_{i}}{2}.

3.5 Theorem. Let L = L_{M} be a q-primary lattice of type μ ⊢ n. Then

F_{L} = ∑_{λ⊢n} K̃_{λμ}(q)s_{λ}.  (9)

Proof. All matrices considered here will have rows and columns indexed by partitions of n in some fixed order. Given a basis b = {b_{λ} : λ ⊢ n} for the abelian group Λ^{n} of symmetric functions of degree n with integer coefficients, we identify b with the vector whose components are the b_{λ}’s (in the fixed order considered above). Write e.g. K(q) for the matrix [K_{λμ}(q)], and let ′ denote transpose. Thus

s = K(q)P,  (10)

by definition of K_{λμ}(q). It’s easy to see (e.g. [6, §4]) that if we define

α_{μν}(q) = α_{L_{μ}}(S_{ν}),

where ℓ(ν) = ℓ and S_{ν} = {ν_{1}, ν_{1}+ν_{2}, …, ν_{1}+ν_{2}+⋯ ν_{ℓ−1}}, then α_{μν}(q) is a polynomial in q of degree at most n(μ). Set α̃_{μν} = q^{n(μ)}α_{μν}(1/q). It is an immediate consequence of [15, (3.4) on p. 112], (see [6, equation (4)]) that

h = α̃′P.  (11)

(The references [6] and [15] deal only with Hall lattices, but the work of Tesler mentioned after Proposition 3.3 shows that these results carry over to arbitrary q-primary lattices.) Comparing (10) and (11) and using h = K′s yields α̃′ = K′K(q), or equivalently α̃ = K(q)′K. Since Km = s, we have α̃m = K(q)′s, i.e.,

∑_{ν} q^{n(μ)}α_{μν}(1/q)m_{ν} = ∑_{λ} K_{λμ}(q)s_{λ}.

Substituting 1/q for q and multiplying by q^{n(μ)} yields (9) (i.e., αm = K̃(q)′s). □

Since q-primary lattices are modular they are Cohen-Macaulay [4, Ex. 2.5 and Thm. 3.2], so we can ask whether Conjecture 2.3 holds for them. By a well-known result of Lascoux and Schützenberger (see [15, (6.5) on p. 129]) the coefficients of K_{λμ}(q) (or K̃_{λμ}(q)) are nonnegative, so Theorem 3.5 implies that Conjecture 2.3 is valid for q-primary lattices (and so for locally rank-symmetric modular lattices).

Since F_{L} has a simple combinatorial definition, we could use (9) as the definition of the Kostka polynomial K_{λμ}(q). This gives a definition using symmetric functions considerably simpler (though not any easier to work with) than the usual definition s = K(q)P in terms of the Hall-Littlewood symmetric functions.

We know of numerous other examples of locally rank-symmetric posets, though they don’t seem as interesting as q-primary lattices. First suppose that P and Q are locally rank-symmetric of the same rank n. Let P ˆ+Q denote the direct sum (= disjoint union) of P and Q, with the ˆ0’s identified and ˆ1’s identified. The following proposition is self-evident.

3.6 Proposition. With P and Q as above, we have that P ˆ+Q is locally ranksymmetric of rank n, and F_{P ˆ+Q} = F_{P} + F_{Q} − m_{n}.

A simple class of Cohen-Macaulay locally rank-symmetric posets are the ladders H_{nj} of rank n and width j. They have j elements of each rank 1, 2, …, n − 1, and x < y whenever ρ(x) < ρ(y). It’s easy to see that

F_{H_{nj}} = ∑_{λ⊢n} j^{ℓ(λ)−1}m_{λ} = ∑_{i=0}^{n−1}(j − 1)^{i}s_{n−i,1^{i}}.

Hence Conjecture 2.3 is valid for ladders.

A class of posets even more restrictive than locally rank-symmetric posets are (finite) binomial posets [8][26, Ch. 3.15]. For these posets P, all intervals of length k have the same number B(k) of maximal chains. If follows that any interval of P of rank k has B(k)/B(i)B(k − i) elements of rank i, so P is indeed locally ranksymmetric. It was also observed by Ehrenborg [9, p. 10] that F_{P} is a symmetric function for binomial posets P. Numerous examples of binomial posets are given in [8] and [26], but the only examples which are Cohen-Macaulay are included among the posets we have already considered or have rank equal to three. It might be an interesting problem to try to classify all Cohen-Macaulay binomial posets.

Another interesting class of posets are the Eulerian posets [26, Ch. 3.14][28], defined by the condition μ(s, t) = (−1)^{ρ(s,t)} for all s ≤ t in P, where μ denotes the Möbius function of P. In particular, face lattices of convex polytopes are Eulerian. Any simplex, polygon, or three-dimensional polytope with the same number of vertices as two-dimensional faces has a locally rank-symmetric face lattice. Moreover, products of such lattices remain locally rank-symmetric and remain face lattices of polytopes. Recently Bisztriczky [2] has constructed a class of polytopes of arbitrary dimension d whose face lattices are irreducible (i.e., not a direct product of smaller lattices) and locally self-dual. Curiously, these lattices have the same flag f-vectors as products of face lattices of two-dimensional polytopes. If we don’t insist that our locally rank-symmetric Cohen-Macaulay Eulerian poset is a lattice, then the only new irreducible ones we know are the ladders H_{n2} together with additional examples of rank four. The following question may be worth pursuing: What is the dimension of the linear span of all flag f-vectors of (a) locally rank-symmetric face lattices of (n − 1)-dimensional convex polytopes, (b) locally self-dual face lattices of (n − 1)- dimensional convex polytopes, (c) locally rank-symmetric Eulerian posets of rank n, and (d) locally self-dual Eulerian posets of rank n? (Conceivably all four answers could be the same.)

Two additional classes of locally rank-symmetric posets were pointed out by V. Welker and F. Regonati, respectively. The two classes, especially the second, remain to be investigated. The members of the two classes are given by (a) the poset of nondegenerate subspaces of a finite-dimensional vector space over 𝔽_{q} with respect to a symmetric or skew-symmetric form, and (b) the poset of complemented elements of a Hall lattice.

4 A locally-rank symmetric P -cocomplex and relative lexicographic shellability.

In this section we give a fundamental example of a locally rank-symmetric Cohen-Macaulay P -cocomplex. Recall [26, p. 168] that Young’s lattice Y consists of all partitions of all nonnegative integers n, with the ordering μ ≤ λ if μ_{i} ≤ λ_{i} for all i. Let P_{λ/μ} denote the interval [μ, λ] of Y. Let X = X_{λ/μ} consist of all intervals [ρ, σ] of P_{λ/μ} such that ρ < σ and σ/ρ is a horizontal strip, i.e., the Young diagram of σ/ρ does not contain two cells in the same column [15, p. 4]. Write Γ_{λ/μ} = Γ_{X}, and let P/Γ = P_{λ/μ}/Γ_{λ/μ} be the corresponding simple P -cocomplex. Thus P/Γ consists of all chains μ = ν^{0} < ν^{1} < ⋯ < ν^{r} = λ such that each skew shape ν^{i}/ν^{i−1} is a horizontal strip.

4.1 Theorem. Let μ ⊂ λ. Then the P -cocomplex P/Γ = P_{λ/μ}/Γ_{λ/μ} is locally rank-symmetric (and hence flag-symmetric by Theorem 1.5) and Cohen-Macaulay. Moreover, F_{P/Γ} = s_{λ/μ}, the skew Schur function of shape λ/μ.

Proof. The proof that P/Γ is locally rank-symmetric is essentially the same argument used by Bender and Knuth [1, p. 47] to show that Schur functions are symmetric functions. We refer the reader to [1] for the details. The definition of F_{P/Γ} coincides with the usual combinatorial definition [15, (5.12)] of s_{λ/μ}.

We sketch two proofs that P/Γ is Cohen-Macaulay. Both proofs work in the following more general context. Let Q be an n-element poset, and let J(Q) denote its lattice of order ideals [26, Ch. 3.4]. A labeling of Q is a injection ω : Q → ℙ. Let Δ(J(Q), ω) be the set of all chains Ø = I_{0} ⊂ I_{1} ⊂ ⋯ ⊂ I_{k} = Q of J(Q) such that every subposet I_{i} − I_{i−1} is naturally labelled by ω, i.e., if s, t ∈ I_{i} − I_{i−1} and s < t, then ω(s) < ω(t). Thus Δ(J(Q), ω) is the J(Q)-cocomplex J(Q)/Γ_{ω}, where Γ_{ω} consists of all chains I_{1} ⊂ ⋯ ⊂ I_{j} of J̃(Q) = J(Q) − {ˆ0, ˆ1} such that for some 1 ≤ i ≤ j +1, the restriction of ω to I_{i} −I_{i−1} is not natural (where I_{0} = Ø, I_{j+1} = Q).

If we take Q to be a skew diagram of shape λ/μ (regarded as a subposet of ℙ×ℙ with the standard cartesian product order), and if we choose the labeling ω to increase along rows from left to right and to decrease down columns, then Γ_{ω} = Γ_{λ/μ} and Δ(J(Q), ω) = P_{λ/μ}/Γ_{λ/μ}.

4.2 Proposition. For any labelled poset (Q, ω), the cocomplex P/Γ = Δ(J(Q), ω) is Cohen-Macaulay.

First proof. It follows from the proof of [23, Prop. 8.3] and from [23, second paragraph on p. 225] that P/Γ has a geometric realization |P/Γ| which is a convex polytope P with a subset Q of its boundary removed, where Q consists of all points of ∂P visible from some (properly chosen) point outside P. There are two exceptions: if ω is order-preserving then Q = Ø, and if ω is order-reversing then Q = ∂P. Thus either Q is topologically a ball on ∂P with dim Q = dim P −1, or Q = Ø, or Q = ∂P. It follows from [27, Cor. 5.4(ii)] that in all cases P/Γ is Cohen-Macaulay. □

Second proof. A powerful tool for showing that posets are Cohen-Macaulay is the theory of lexicographic shellability [3][4, §2][5]. Here we outline a “relative” version of this theory. The proofs are straightforward generalizations of those in [3]. For simplicity we deal only with edge labelings and not the more general chain labelings of [5]. The theory can easily be extended to chain labelings, but we don’t need them to prove Propostion 4.2.

Let P be a finite graded poset of rank n with ˆ0 and ˆ1. Let E(P) = {(s, t) : t covers s in P }, the set of (directed) edges of the Hasse diagram of P. A function λ : E → ℤ is called an E-labeling. If σ : s = s_{0} < s_{1} < ⋯ < s_{k} = t is a saturated chain (i.e., a maximal chain of the interval [s, t]), then we write λ(σ) = (λ(s_{0}, s_{1}), λ(s_{1}, s_{2}), …, λ(s_{k−1}, s_{k})). The chain σ is increasing if λ(s_{0}, s_{1}) ≤ λ(s_{1}, s_{2}) ≤ ⋯ ≤ λ(s_{k−1}, s_{k}). The descent set of λ(σ) = (a_{1}, …, a_{k}) is defined by D(λ(σ)) = {i : a_{i} > a_{i+1}}. We let ≤_{L} denote lexicographic order on finite integer sequences, so for example 111 <_{L} 112 <_{L} 113 <_{L} 121 <_{L} 122 <_{L} 131 <_{L} 211.

4.3 Definition. (a) Let P be a finite graded poset of rank n with ˆ0 and ˆ1. A labeling λ : E → ℤ is called a relative ER-labeling if the following two conditions are satisfied:

(i) Every interval [s, t] has at most one increasing maximal chain.

(ii) If the interval [s, t] has an increasing maximal chain and s ≤ s′ ≤ t′ ≤ t, then [s′, t′] has an increasing maximal chain.

(b) If in addition for every interval [s, t] with an increasing maximal chain σ, the sequence λ(σ) is strictly less (in lexicographic order) than λ(τ) for any other maximal chain τ of [s, t], then we call λ a relative EL-labeling.

Suppose now that λ : E → ℤ is a relative ER-labeling. Let X = X(P, λ) be the set of all non-singleton intervals of P which possess an increasing maximal chain. Clearly by (ii) above X is an order ideal of non-singleton intervals of P. Hence we can define a simple P -cocomplex Δ(P, λ) = P/Γ_{X}. We then have the following main theorem on relative labelings.

4.4 Theorem. (a) Let λ : E(P) → ℤ be a relative ER-labeling. For S ⊆ [n−1], let γ_{P,λ}(S) be the number of maximal chains σ of P with descent set S. Then β_{Δ(P,λ)}(S) = γ_{P,λ}(S).

(b) Let λ : E(P) → ℤ be a relative EL-labeling. Let σ_{1}, σ_{2}, …, σ_{m} be any ordering of the maximal chains of P such that λ(σ_{1}) ≤_{L} λ(σ_{2}) ≤_{L} ⋯ ≤_{L} λ(σ_{m}). Then σ_{1}, σ_{2}, …, σ_{m} is a shelling of Δ(P, λ) (as defined in [27, §6]). The standard arguments for showing that shellable simplicial complexes are Cohen-Macaulay (e.g., [24]) extend without difficulty to the relative case, so we conclude that Δ(P, λ) is Cohen-Macaulay. □

A trivial example of a relative EL-labeling is as follows. Let P be any finite graded poset of rank n with ˆ0 and ˆ1, and choose λ so that every maximal chain is strictly decreasing (e.g., λ(s, t) = ρ(t), the rank of t). Then only intervals of length zero and one have increasing maximal chains, so the conditions of Definition 4.3 are vacuously satisfied. Topologically, Δ(P, λ) is a disjoint union of m open balls of dimension n−2, where m is the number of maximal chains of P.

A more substantial example, and the one which is relevant to Proposition 4.2, is the following. Let Q be any n-element poset, and let ω : Q → [n] be a labeling. Define an E-labeling λ = λ_{ω} : E(J(Q)) → [n] by letting λ_{ω}(I, I′) be the label ω(t) of the unique element t ∈ I′ − I. One easily checks that λ_{ω} is an EL-labeling, and that the cocomplex Δ(J(Q), λ_{ω}) coincides with Δ(J(Q), ω) = J(Q)/Γ_{ω}. Hence by Theorem 4.4, Δ(J(Q), ω) is Cohen-Macaulay, completing the second proof of Proposition 4.2 and thus also of Theorem 4.1. □

We conclude this section by stating a partial “labelled analogue” of Theorem 3.1 which is equivalent to a result of C. Malvenuto [16][17, Thm. 6.4]. (A full analogue is given by Conjecture 4.6.) Actually Malvenuto states a slightly weaker result than Theorem 4.5 below, but her proof carries over to Theorem 4.5 (as she herself observes in [17, p. 108]). If λ/μ is a skew shape, then we mentioned above that the labeling ω of P_{λ/μ} which corresponds to the cocomplex P/Γ = P_{λ/μ}/Γ_{λ/μ} is characterized by the conditions that it increases along rows and decreases down columns. We call such a

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

1

Figure 2: A Schur labelled skew shape

[figure: 1; 2; 3; 3; 2; 1; 1; 2; 3; 2; 3; 1; 2; 1; 3; 3; 2; 1; 1; 3; 2; 3; 1; 2; 2; 1; 3; 1; 3; 2; 1; 2; 3]

Figure 3: The eleven three-element labelled posets (C, ω) for which (J(C), λ_{ω}) is rank-symmetric

labeling a Schur labeling and say that (P, ω) is a Schur labelled skew shape. Figure 2 illustrates a Schur labeling of the skew shape 76441/31. Define two labelled posets (Q, ω) and (Q′, ω′) to be isomorphic if there is a poset isomorphism f : Q → Q′ such that if s < t in Q then

ω(s) < ω(t) if and only if ω′(f(s)) < ω′(f(t)).  (12)

(Note that if s and t are incomparable in Q then we don’t require that (12) holds.) The J(Q)-cocomplex J(Q)/Γ_{ω} depends only on the isomorphism type of (Q, ω).

4.5 Theorem (C. Malvenuto). Let ω : Q → [n] be a labeling of an n-element poset Q. Assume that the cocomplex Δ(J(Q), ω) is locally rank-symmetric. Then (Q, ω) is isomorphic to a Schur labelled skew shape.

Malvenuto actually shows that rather than using the full hypothesis that (J(C), λ_{ω_{C}}) is rank-symmetric for every convex subset C of Q (with ω_{C} denoting the restriction of ω to C), one only needs this hypothesis for three-element convex subsets. In other words, if every three-element convex subset of Q has the type of one of the labelled posets of Figure 3, then (Q, ω) is isomorphic to a Schur labelled skew shape.

Theorem 4.5 is a special case of the conjecture on page 81 of [21], which we repeat below (in a different wording).

4.6 Conjecture. The conclusion to Theorem 4.5 remains true if we assume only that Δ(J(Q), ω) is flag-symmetric (rather than locally rank-symmetric).

5 Connections with representation theory.

If a homogeneous symmetric function f (over ℤ) of degree n is Schur positive, then it is the (Frobenius) characteristic ch ψ of a character ψ of the symmetric group S_{n} (see [15, I.7]). The degree ψ(1) of this character is the coefficient of m_{1^{n}} when f is expanded in terms of monomial symmetric functions m_{λ}. Hence if P/Γ is flagsymmetric of rank n and F_{P/Γ} is Schur positive, then by (3) F_{P/Γ} = ch ψ_{P/Γ} for some character ψ_{P/Γ} of S_{n} of degree α([n − 1]), the number of facets of P/Γ (which will be the number of maximal chains in P if Γ doesn’t contain a maximal chain of P). Hence we may ask whether there is a “natural” linear action φ of S_{n} on the complex vector space ℂF(P/Γ) with basis F(P/Γ), the set of facets of P/Γ, such that φ has character ψ_{P/Γ}. We will discuss some interesting examples of such actions of S_{n} (or in one case the Hecke algebra of S_{n}). However, it appears that such examples are quite special, and that in general there is no nice connection between flag-symmetric posets P (or P -cocomplexes P/Γ) and representation theory, even when F_{P} or F_{P/Γ} are Schur positive.

First we discuss what we mean by a “natural” action of S_{n} on ℂF(P/Γ). Let s_{i} = (i, i+1), the adjacent transposition which transposes i and i+1, for 1 ≤ i ≤ n−1. Let P be any graded poset of rank n with ˆ0 and ˆ1, and let Γ be any subcomplex of Δ̃(P). We say that a linear action of S_{n} on ℂF(P/Γ) is local if for each maximal chain F : ˆ0 = t_{0} < t_{1} < ⋯ < t_{n} = ˆ1 of P/Γ, s_{i} · F is a linear combination of maximal chains of P/Γ of the form F′ : ˆ0 = t_{0} < t_{1} < ⋯ < t_{i−1} < t′_{i} < t_{i+1} < ⋯ < t_{n} = ˆ1, i.e., F′ agrees with F except possibly at the ith rank. This definition is motivated by the definition of “local stationary algebra” in [30]. Now assume that P/Γ is flagsymmetric. We say that an S_{n}-action φ on ℂF(P/Γ) is good if it is local and if its character χ_{φ} has characteristic ch χ_{φ} = F_{P/Γ}.

The simplest situation for a local S_{n}-action is the following. Suppose that P is any finite graded poset of rank n with ˆ0 and ˆ1, such that every interval of rank two contains three or four elements (i.e., is a 3-element chain or the boolean algebra B_{2}).

For 1 ≤ i ≤ n − 1 and a maximal chain F : ˆ0 = t_{0} < t_{1} < ⋯ < t_{n} < ˆ1, define

s_{i} · F = \{ \begin{matrix}F, & if [t_{i−1}, t_{i+1}] has three elements \\ (F − \{t_{i}\}) ∪ \{t′_{i}S′\}, & if [t_{i−1}, t_{i+1}] has the four elements t_{i−1}, t_{i}, t′_{i}, t_{i+1}. \end{matrix}

(13)

When does this definition define an S_{n}-action? In other words, when are the Coxeter relations s_{i}^{2} = 1, s_{i}s_{j} = s_{j}s_{i} if |j − i| ≥ 2, s_{i}s_{i+1}s_{i} = s_{i+1}s_{i}s_{i+1} satisfied? The first two are automatic, and one can check that the last is satisfied if and only if every interval of rank three is isomorphic to a sum (in the sense of Proposition 3.6) of intervals C_{4}, C_{3} × C_{2}, or C_{2} × C_{2} × C_{2}, where C_{i} denotes an i-element chain. If P is Cohen-Macaulay then intervals of rank three are irreducible with respect to ˆ+, so only C_{4}, C_{3} × C_{2}, and C_{2} × C_{2} × C_{2} can occur above. It is clear that any product of chains L_{λ} = C_{λ_{1}+1} × ⋯ × C_{λ_{ℓ}+1} has only C_{4}, C_{3} × C_{2}, or C_{2} × C_{2} × C_{2} as rank three intervals, and hence has a local S_{n}-action (where n = ∑ λ_{i}) defined by (13). This action is isomorphic to the natural action of S_{n} on left cosets of the Young subgroup S_{λ} = S_{λ_{1}} × S_{λ_{2}} × ⋯ × S_{λ_{ℓ}}, and its character ψ^{λ} has characteristic h_{λ}. Since L_{λ} is flag-symmetric (even locally self-dual) and F_{L_{λ}} = h_{λ}, we have a satisfactory instance of a good S_{n}-action. The following result, originally conjectured by this author, is due to David Grabiner [11].

5.1 Proposition (D. Grabiner). Let P be a finite graded poset of rank n with ˆ0 and ˆ1, such that every interval of rank three is a product of chains, i.e., is isomorphic to one of C_{4}, C_{3} × C_{2}, or C_{2} × C_{2} × C_{2}. Suppose also that for every interval [s, t] of rank at least four, the open interval (s, t) is connected (which is the case, for example, when P is Cohen-Macaulay). Then P is a product of chains.

5.2 Corollary. If P is a Cohen-Macaulay poset with a good S_{n}-action of the form (13), then P is a product of chains.

We can now ask for examples of good actions of S_{n} on ℂF(P/Γ) which are not of the form (13). It follows from the description of Young’s natural representation of skew shape λ/μ given in [12] or [30] that there is a good action φ^{λ/μ} of S_{n} on ℂF(P_{λ/μ}/Γ_{λ/μ}), so by Theorem 4.1 the character χ^{λ/μ} of φ^{λ/μ} has characteristic ch χ^{λ/μ} = s_{λ/μ} (where n = |λ/μ|). When λ/μ is a horizontal strip (as defined at the beginning of Section 4) we recover the good action of S_{n} on a product of chains defined by (13). We don’t know of any further examples of a good S_{n}-action on a connected flag-symmetric P -cocomplex P/Γ which does not have a facet stabilized by S_{n}.

When λ/μ consists of n disjoint squares, then P_{λ/μ}/Γ_{λ/μ} = P_{λ/μ} ≅ B_{n}, the boolean algebra of rank n. The good action of S_{n} on B_{n} defined above is just the regular representation of S_{n}. There is an interesting q-analogue of this action which we now discuss. For a prime power q, let B_{n}(q) be the lattice of subspaces of an ndimensional vector space V_{n} over 𝔽_{q}. B_{n}(q) is well known to be “nice” q-analogue of B_{n}. For 1 ≤ i ≤ n − 1, define linear transformations A_{i} on ℂF(B_{n}(q)) (the space of formal linear combinations of maximal chains of B_{n}(q)) by

A_{i}(F) = ∑_{F′} F′,  (14)

where if F is given by ˆ0 = V_{0} ⊂ V_{1} ⊂ ⋯ ⊂ V_{n} = ˆ1, then F′ ranges over all flags (maximal chains) ˆ0 = V_{0} ⊂ V_{1} ⊂ ⋯ ⊂ V_{i−1} ⊂ V′_{i} ⊂ V_{i+1} ⊂ ⋯ ⊂ V_{n} = ˆ1, where V′_{i} ≠ V_{i}. (There are exactly q such flags F′.) One checks that

A_{i}^{2} = (q − 1)A_{i} + qI
A_{i}A_{j} = A_{j}A_{i}, if |j − i| ≥ 2
A_{i}A_{i+1}A_{i} = A_{i+1}A_{i}A_{i+1}.

Let H_{n}(q) denote the Hecke algebra of S_{n} with standard generators T_{1}, T_{2}, …, T_{n−1} corresponding to the simple reflections (adjacent transpositions) s_{1}, s_{2}, …, s_{n−1} in S_{n} [13, §7.4][18] (though in [18] g_{i} is used for our T_{i}). The defining relations for H_{n}(q) imply that we have a representation

φ : H_{n}(q) → End(ℂF(B_{n}(q)))

defined by φ(T_{i}) = A_{i}. In other words, we have a local action of H_{n}(q) on ℂF(B_{n}(q)). The irreducible representations φ^{λ} of H_{n}(q) are indexed in a natural way by partitions λ of n (e.g., [18]). The representation φ is well-known in the theory of Hecke algebras (though perhaps not described in exactly the way we have done it), and the multiplicity f^{λ}(q) of φ^{λ} in φ is called a generic degree of H_{n}(q). Since φ is a q-analogue of the regular representation of S_{n}, we may regard f^{λ}(q) as a q-analogue of the number f^{λ} of standard Young tableaux of shape λ (i.e., the dimension of the irreducible representation of S_{n} indexed by λ). In fact, it is known (see [19, Thm. 5.9] for a proof accessible to combinatorialists) that

f^{λ}(q) = \frac{q^{b(λ)}(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})}{(1 − q^{h_{1}})(1 − q^{h_{2}}) ⋯ (1 − q^{h_{n}})}
= ∑_{T} q^{maj(T)},

where b(λ) = ∑ \binom{λ_{i}′}{2} = ∑(i − 1)λ_{i}; h_{1}, h_{2}, …, h_{n} are the hook-lengths of λ; T ranges over all standard tableaux of shape λ; and maj(T) denotes the major index of T, defined by maj(T) = ∑ i, summed over all i for which i + 1 appears in a lower row of T than i.

In analogy to S_{n}-actions, we say that an action σ of H_{n}(q) on ℂF(P/Γ), where P/Γ is flag-symmetric of rank n, is good if it is local (i.e., if F is a maximal chain then T_{i} · F is a linear combination of maximal chains which agree with F at all ranks except possibly rank i) and if F_{P/Γ} = ∑ c_{λ}s_{λ}, where c_{λ} is the multiplicity of φ^{λ} in σ.

5.3 Proposition. The action φ of H_{n}(q) on ℂF(B_{n}(q)) defined above is good.

Proof. By definition φ is local. Now B_{n}(q) is a Hall lattice of type (1^{n}), so by Theorem 3.5 we have

F_{B_{n}(q)} = ∑_{λ⊢n} K̃_{λ,1^{n}}(q)s_{λ}.

It is known [15, Ex. 2 on p. 130] that K̃_{λ,1^{n}}(q) = f^{λ}(q), and the proof follows. □

It is natural to ask for other posets P (where P − {ˆ0, ˆ1} is connected) with a local H_{n}(q)-action, but except for the uninteresting case where H_{n}(q) acts trivially we don’t know of any examples. A Hall lattice L of type λ is a “nice” q-analogue of a product of chains of lengths λ_{1}, λ_{2}, . . .. Let F : ˆ0 = t_{0} < t_{1} < ⋯ < t_{n} = ˆ1 be a maximal chain in L. Define linear transformations A_{i} on ℂF(L) for 1 ≤ i ≤ n − 1 by A_{i}(F) = F if the interval [t_{i−1}, t_{i+1}] is a chain, and otherwise A_{i}(F) is given by (14). This seems to be the “natural” analogue of the S_{n}-action on C_{λ_{1}+1} × C_{λ_{2}+1} × ⋯, but unfortunately it does not define an H_{n}(q)-action unless λ = (n) or λ = (1^{n}).

A final question: For every λ ⊢ n, is there a P -cocomplex P/Γ and a good action of H_{n}(q) on ℂF(P/Γ) which is isomorphic to the irreducible representation φ^{λ} of H_{n}(q)?

References

[1] E. A. Bender and D. E. Knuth, Enumeration of plane partitions, J. Combinatorial Theory 13 (1972), 40–54.

[2] T. Bisztriczky, On a class of generalized simplices, preprint.

[3] A. Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), 159–183.

[4] A. Björner, A. Garsia, and R. Stanley, An introduction to the theory of Cohen-Macaulay posets, in Ordered Sets (I. Rival, ed.), Reidel, Dordrecht/Boston/- London, 1982, pp. 583–615.

[5] A. Björner and M. Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), 323–341.

[6] L. M. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc. 101 (1987), 771–775.

[7] L. M. Butler and A. W. Hales, Generalized flags in p-groups, Discrete Math., to appear.

[8] P. Doubilet, G.-C. Rota, and R. Stanley, On the foundations of combinatorial theory (VI): The idea of generating function, in Sixth Berkeley Symposium on Mathematical Statistics and Probability, vol. II: Probability Theory, University of California, 1972, pp. 267–318.

[9] R. Ehrenborg, On posets and Hopf algebras, preprint.

[10] I. Gessel, Multipartite P -partitions and inner products of skew Schur functions, in Combinatorics and Algebra (C. Greene, ed.), Contemporary Math., vol. 34, American Mathematical Society, Providence, RI, 1984, pp. 289–301.

[11] D. Grabiner, in preparation.

[12] C. Greene, A rational function identity related to the Murnagham-Nakayama formula for the characters of S_{n}, J. Algebraic Combinatorics 1 (1992), 235–255.

[13] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge University Press, Cambridge, 1990.

[14] B. Jónsson and G. S. Monk, Representations of primary arguesian lattices, Pacific J. Math. 30 (1969), 95–139.

[15] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1979.

[16] C. Malvenuto, P -partitions and the plactic congruence, Graphs and Combinatorics 9 (1993), 63–73.

[17] C. Malvenuto, Produits et coproduits des fonctions quasi-symétriques et de l’algèbre des descentes, Ph.D. thesis, Université du Québec à Montréal, November, 1993.

[18] A. Ram, A Frobenius formula for the characters of the Hecke algebra, Invent. Math. 106 (1991), 461–468.

[19] A. Ram and J. B. Remmel, Applications of the Frobenius formulas for the characters of the symmetric group and Hecke algebras of type A, J. Algebraic Combinatorics, to appear.

[20] F. Regonati, Whitney numbers (of the II kind) of finite modular lattices, preprint.

[21] R. Stanley, Ordered Structures and Partitions, Mem. Amer. Math. Soc., vol. 119, 1972.

[22] R. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197–219.

[23] R. Stanley, Combinatorial reciprocity theorems, Advances in Math. 14 (1974), 194–253.

[24] R. Stanley, Cohen-Macaulay rings and constructible polytopes, Bull. Amer. Math. Soc. 81 (1975), 133–135.

[25] R. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), 139–157.

[26] R. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986.

[27] R. Stanley, Generalized h-vectors, intersection cohomology of toric varieties, and related results, in Commutative Algebra and Combinatorics (M. Nagata and H. Matsumura, eds.), Advanced Studies in Pure Mathematics 11, Kinokuniya, Tokyo, and North-Holland, Amsterdam/New York, 1987, pp. 187–213.

[28] R. Stanley, A survey of Eulerian posets, in Proc. NATO Advanced Study Institute on Polytopes: Abstract, Convex, and Computational (Toronto, 1993), to appear.

[29] G. P. Tesler, Semi-primary lattices and tableau algorithms, Ph.D. thesis, M.I.T., 1995.

[30] A. M. Vershik, Local stationary algebras, Amer. Math. Soc. Transl. (2) 148 (1991), 1–13; translated from Proc. First Siberian Winter School “Algebra and Analysis” (Kemerovo, 1988).