SIGN-GRADED POSETS, UNIMODALITY OF W -POLYNOMIALS AND THE CHARNEY-DAVIS CONJECTURE

PETTER BRÄNDÉN

Abstract. We generalize the notion of graded posets to what we call signgraded (labeled) posets. We prove that the W -polynomial of a sign-graded poset is symmetric and unimodal. This extends a recent result of Reiner and Welker who proved it for graded posets by associating a simplicial polytopal sphere to each graded poset P. By proving that the W -polynomials of signgraded posets has the right sign at −1, we are able to prove the Charney-Davis Conjecture for these spheres (whenever they are flag).

1. Introduction and preliminaries

Recently Reiner and Welker [8] proved that the W -polynomial of a graded naturally labeled poset P has unimodal coefficients. They proved this by associating to P a simplicial polytopal sphere, Δ_{eq}(P), whose h-polynomial is the W -polynomial of P, and invoking McMullen’s g-theorem [11]. Whenever this sphere is flag, i.e., its minimal non-faces all have cardinality two, they noted that the Neggers-Stanley Conjecture implies the Charney-Davis Conjecture for Δ_{eq}(P). In this paper we give a completely different proof of the unimodality of W -polynomials of graded posets, and we also prove the Charney-Davis Conjecture for Δ_{eq}(P) (whenever they are flag). Our proof is by studying a family of labeled posets, which we call sign-graded posets, of which the class of graded naturally labeled posets is a sub-class.

In this paper all posets will be finite. For undefined terminology on posets we refer the reader to [13]. We denote the cardinality of a poset P with a small letter p. Let P be a poset and let ω : P → {1, 2, …, p} be a bijection. The pair (P, ω) is called a labeled poset. If ω is order-preserving then (P, ω) is said to be naturally labeled. A (P, ω)-partition is a map σ : P → {1, 2, 3, …} such that

• σ is order reversing, that is, if x ≤ y then σ(x) ≥ σ(y),

• if x < y and ω(x) > ω(y) then σ(x) > σ(y). The theory of (P, ω)-partitions was developed by Stanley in [10]. The number of (P, ω)-partitions σ : P → {1, 2, …, n} is a polynomial of degree p in n called the order polynomial of (P, ω) and is denoted Ω(P, ω; n). The W -polynomial of (P, ω) is defined by

∑_{n≥0} Ω(P, ω; n)t^{n} = \frac{tW (P, ω; t)}{(1 − t)^{p+1}}.

The Jordan-Hölder set, L(P, ω), of (P, ω) is the set of permutations ω(x_{1}), ω(x_{2}), …, ω(x_{p}) where x_{1}, x_{2}, …, x_{p} is a linear extension of P. A descent in a permutation π = π_{1}π_{2} ⋯ π_{p} is an index 1 ≤ i ≤ p − 1 such that π_{i} > π_{i+1}. The number of descents of π is denoted des(π). A result of Stanley’s [10] implies that the W -polynomial can be written as

Part of this work was financed by the EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272, while the author was at Universitá di Roma “Tor Vergata”, Rome, Italy.

W (P, ω; t) = ∑_{π∈L(P,ω)} t^{des(π)},

The Neggers-Stanley Conjecture is the following:

Conjecture 1.1 (Neggers-Stanley). For any labeled poset (P, ω) the polynomial W (P, ω; t) has only real zeros.

It was first conjectured by Neggers [6] in 1978 for natural labelings and by Stanley in 1986 for arbitrary labelings. The conjecture has been proved for special cases, see [1, 2, 8, 14] for the state of the art. If a polynomial has only real non-positive zeros then its coefficients form a unimodal sequence. For the W -polynomials of graded posets unimodality was first proved by Gasharov [5] whenever the rank is at most 2, and as mentioned by Reiner and Welker for all graded posets.

For the relevant definitions concerning the topology behind the Charney-Davis Conjecture we refer the reader to [3, 8, 12].

Conjecture 1.2 (Charney-Davis, [3]). Let Δ be a flag simplicial homology (d−1)- sphere, where d is even. Then the h-vector, h(Δ, t), of Δ satisfies

(−1)^{d/2}h(Δ, −1) ≥ 0.

Recall that the nth Eulerian polynomial, A_{n}(x), is the W -polynomial of an anti-chain of n elements. The Eulerian polynomials can be written as

A_{n}(x) = ∑_{i=0}^{⌊(n−1)/2⌋} a_{n,i}x^{i}(1 + x)^{n−1−2i},

where a_{n,i} is a non-negative integer for all i. This was proved by Foata and Schützenberger in [4] and combinatorially by Shapiro, Getu and Woan in [9]. From this expansion we see immediately that A_{n}(x) is symmetric and that the coefficients in the standard basis are unimodal. It also follows that (−1)^{(n−1)/2}A_{n}(−1) ≥ 0.

We will in Section 2 define a class of labeled poset whose members we call signgraded posets. This class includes the class of naturally labeled graded posets. In Section 4 we show that the W -polynomial of a sign-graded poset (P, ω) of rank r can be expanded, just as the Eulerian polynomial, as

W (P, ω; t) = ∑_{i=0}^{⌊(p−r−1)/2⌋} a_{i}(P, ω)t^{i}(1 + t)^{p−r−1−2i},  (1.1)

where a_{i}(P, ω) are non-negative integers. Hence, symmetry and unimodality follow, and W (P, ω; t) has the right sign at −1. Consequently, whenever the associated sphere Δ_{eq}(P) of a graded poset P is flag the Charney-Davis Conjecture holds for Δ_{eq}(P). We also note that all symmetric polynomials with non-positive zeros only, admits an expansion such as (1.1). Hence, that W (P, ω; t) has such an expansion can be seen as further evidence for the Neggers-Stanley Conjecture.

In [7] the Charney-Davis quantity of a graded naturally labeled poset (P, ω) of rank r was defined to be (−1)^{(p−1−r)/2}W (P, ω; −1). In Section 5 we give a combinatorial interpretation of the Charney-Davis quantity as counting certain reverse alternating permutations. Finally in Section 6 we give a characterization of sign-graded posets in terms of properties of order polynomials.

Figure 1. A sign-graded poset, its two labelings and the corresponding rank function.

[figure: 10; 7; 6; 2; 9; 5; 4; 1; 8; 3; •; •; 1; •; 1; •; 1; •; −1; •; −1; 1; •; 1; •; 1; 1; •; •; −1; 1; 1; 0; 0; −1; 1; 0; 0; −1; 1; 0]

2. Sign-graded posets

Let (P, ω) be a labeled poset and let E = E(P) = {(x, y) ∈ P × P : x ≺ y} be the covering relations of P. An element y covers x, written x ≺ y, if x < y and x < z < y for no z ∈ P. We associate a labeling ϵ : E → {−1, 1} of the Hasse-diagram of P by

ϵ(x, y) = \begin{cases}1 if ω(x) < ω(y), \\ −1 if ω(x) > ω(y). \end{cases}

Note that the definition of a (P, ω)-partition only depends on the function ϵ. In what follows we will often refer to ϵ as the labeling and write Ω(P, ϵ; t).

Definition 2.1. Let ϵ : E → {−1, 1} be a labeling of E. We say that P is sign-graded with respect to ϵ (or ϵ-graded for short) if for every maximal chain x_{0} ≺ x_{1} ≺ ⋯ ≺ x_{n} the sum

∑_{i=1}^{n} ϵ(x_{i−1}, x_{i})

is the same. The common value, r(ϵ), of the above sum is called the rank of ϵ. The rank function, ρ : P → ℤ is defined by

ρ(x) = ∑_{i=1}^{m} ϵ(x_{i−1}, x_{i}),

where x_{0} ≺ x_{1} ≺ ⋯ ≺ x_{m} = x is any saturated chain from a minimal element to x.

See Fig. 1 for an example of a sign-graded poset. Note that if ϵ is identically equal to 1, then a sign-graded poset with respect to ϵ is just a graded poset. Note also that if P is ϵ-graded then P is also −ϵ-graded, where −ϵ is defined by (−ϵ)(x, y) = −ϵ(x, y). It may come as a surprise to the reader that when it comes to order-polynomials of sign-graded posets, the specific labeling does not matter:

Theorem 2.2. Let P be ϵ-graded and μ-graded. Then

Ω(P, ϵ; t − \frac{r(ϵ)}{2}) = Ω(P, μ; t − \frac{r(μ)}{2}).

Proof. Let ρ_{ϵ} and ρ_{μ} denote the rank functions of (P, ϵ) and (P, μ) respectively, and let A(ϵ) denote the set of (P, ϵ)-partitions. Define a function ξ : A(ϵ) → ℚ^{P} by ξσ(x) = σ(x) + Δ(x), where

Δ(x) = \frac{r(ϵ) − ρ_{ϵ}(x)}{2} − \frac{r(μ) − ρ_{μ}(x)}{2}.

The four possible combinations of labelings of a covering-relation (x, y) ∈ E are

Table 1

ϵ(x, y) μ(x, y) σ  Δ  ξσ
1  1  σ(x) ≥ σ(y) Δ(x) = Δ(y)  ξσ(x) ≥ ξσ(y)
1  −1  σ(x) ≥ σ(y) Δ(x) = Δ(y) + 1 ξσ(x) > ξσ(y)
−1  1  σ(x) > σ(y) Δ(x) = Δ(y) − 1 ξσ(x) ≥ ξσ(y)
−1  −1  σ(x) > σ(y) Δ(x) = Δ(y)  ξσ(x) > ξσ(y)

given in Table 1.

According to the table ξσ is a (P, μ)-partition provided that ξσ(x) > 0 for all x ∈ P. But ξσ is order-reversing so it attains its minima on maximal elements. If z is a maximal element we have ξσ(z) = σ(z) so ξ : A(ϵ) → A(μ). By symmetry we also have a map η : A(μ) → A(ϵ) defined by

ησ(x) = σ(x) + \frac{r(μ) − ρ_{μ}(x)}{2} − \frac{r(ϵ) − ρ_{ϵ}(x)}{2}.

Hence, η = ξ^{−1} and ξ is a bijection.

Since σ and ξσ are order-reversing they attain their maxima on minimal elements. But if z is a minimal element then ξσ(z) = σ(z) + \frac{r(ϵ)−r(μ)}{2}, which gives

Ω(P, μ; n) = Ω(P, ϵ; n + \frac{r(μ) − r(ϵ)}{2}),

and proves the theorem. □

Theorem 2.3. Let P be ϵ-graded. Then

Ω(P, ϵ; t) = (−1)^{p}Ω(P, ϵ; −t − r(ϵ)).

Proof. We have the following reciprocity for order polynomials, see [10]:

Ω(P, −ϵ; t) = (−1)^{p}Ω(P, ϵ; −t).  (2.1)

Note that r(−ϵ) = −r(ϵ), so by Theorem 2.2 we have:

Ω(P, −ϵ; t) = Ω(P, ϵ, t − r(ϵ)),

which, combined with (2.1), gives the desired result. □

Corollary 2.4. Let P be an ϵ-graded poset. Then W (P, ϵ, t) is symmetric with center of symmetry (p − r(ϵ) − 1)/2. If P is also μ-graded then

W (P, μ; t) = t^{(r(ϵ)−r(μ))/2}W (P, ϵ; t).

Proof. It is known, see [10], that if W (P, ϵ; t) = ∑_{i≥0} w_{i}(P, ϵ)t^{i} then Ω(P, ϵ; t) = ∑_{i≥0} w_{i}(P, ϵ)\binom{t+p−1−i}{p}. Let r = r(ϵ). Theorem 2.3 gives:

Ω(P, ϵ; t) = ∑_{i≥0} w_{i}(P, ϵ)(−1)^{p}\binom{−t − r + p − 1 − i}{p}

= ∑_{i≥0} w_{i}(P, ϵ)\binom{t + r + i}{p}

= ∑_{i≥0} w_{p−r−1−i}(P, ϵ)\binom{t + p − 1 − i}{p},

so w_{i}(P, ϵ) = w_{p−r−1−i}(P, ϵ) for all i, and the symmetry follows. The relationship between the W -polynomials of ϵ and μ follows from Theorem 2.2 and the expansion of order-polynomials in the basis \binom{t+p−1−i}{p}. □

The following theorem tells us that the class of sign-graded posets is considerably greater than the class of graded posets.

Theorem 2.5. Let P be a finite poset. Then there exists a labeling ϵ : E → {−1, 1} such that (P, ϵ) is sign-graded if and only if all maximal chains in P have the same parity (cardinality modulo 2).

Moreover, the labeling ϵ can be chosen so that the corresponding rank function has values in {0, 1}.

Proof. It is clear that if P is ϵ-graded then all maximal chains have the same parity. Let P be a poset whose maximal chains have the same parity. Then, for any x ∈ P, all saturated chains starting at a minimal element and ending at x has the same length modulo 2. Hence, we may define a labeling ϵ : P → {−1, 1} by ϵ(x, y) = (−1)^{ℓ(x)}, where ℓ(x) is the length of any saturated chain starting at a minimal element and ending at x. It follows that P is ϵ-graded and that its rank function has values in {0, 1}. □

We say that ω : P → {1, 2, …, p} is canonical if (P, ω) has a rank-function ρ with values in {0, 1}, and ρ(x) < ρ(y) implies ω(x) < ω(y). By Theorem 2.5 we know that P admits a canonical labeling if P is sign-graded with respect to some ϵ.

3. The Jordan-Hölder set of a sign-graded poset

Let (P, ω) be sign-graded. We may assume that ω(x) < ω(y) whenever ρ(x) < ρ(y). Assume that x, y ∈ P are incomparable and that ρ(y) = ρ(x) + 1. Then the Jordan-Hölder set of (P, ω) can be partitioned into two sets: One where in all permutations ω(x) comes before ω(y) and one where ω(y) comes before ω(x). This means that

L(P, ω) = L(P′, ω) ⊔ L(P′′, ω),  (3.1)

where P′ is the transitive closure of E ∪ {x ≺ y}, and P′′ is the transitive closure of E ∪ {y ≺ x}.

Lemma 3.1. With definitions as above (P′, ω) and (P′′, ω) are sign-graded with the same rank-function as that for (P, ω).

Proof. Let C : z_{0} ≺ z_{1} ≺ ⋯ ≺ z_{k} = z be a saturated chain in P′′, where z_{0} is a minimal element in P′′. Of course z_{0} is also a minimal element in P. We have to prove that

ρ(z) = ∑_{i=0}^{k−1} ϵ′′(z_{i}, z_{i+1}),

where ϵ′′ is the “edge”-labeling of P′′ and ρ is the rank-function of (P, ω).

All covering relations in P′′, except y ≺ x, are also covering relations in P. Note that ϵ′′(y, x) = −1. If y and x do not appear in C, then C is a saturated chain in P and we have nothing to prove. Otherwise

C : y_{0} ≺ ⋯ ≺ y_{i} = y ≺ x = x_{i+1} ≺ x_{i+2} ≺ ⋯ ≺ x_{k} = z.

Note that if s_{0} ≺ s_{1} ≺ ⋯ ≺ s_{ℓ} is any saturated chain in P then ∑_{i=0}^{ℓ−1} ϵ(s_{i}, s_{i+1}) = ρ(s_{ℓ}) − ρ(s_{0}). Since y_{0} ≺ ⋯ ≺ y_{i} = y and x = x_{i+1} ≺ x_{i+2} ≺ ⋯ ≺ x_{k} = z are saturated chains in P we have

∑_{i=0}^{k−1} ϵ′′(z_{i}, z_{i+1}) = ρ(y) + ϵ′′(y, x) + ρ(z) − ρ(x)
= ρ(y) − 1 − ρ(x) + ρ(z)
= ρ(z),

as was to be proved. The statement for (P′, ω) follows similarly. □

We say that a sign-graded poset (P, ω) is saturated if for all x, y ∈ P we have that x and y are comparable whenever |ρ(y) − ρ(x)| = 1. Let P and Q be posets on the same set. Then Q extends P if x <_{Q} y whenever x <_{P} y.

Corollary 3.2. Let (P, ω) be a sign-graded poset. Then the Jordan-Hölder set of (P, ω) is uniquely decomposed as the disjoint union

L(P, ω) = ⨆_{Q} L(Q, ω),

where the union is over all saturated sign-graded posets (Q, ω), which extend (P, ω) and has the same rank-function as (P, ω).

Proof. That the union exhausts L(P, ω) follows from (3.1) and Lemma 3.1. Let (Q_{1}, ω) and (Q_{2}, ω) be two different saturated sign-graded posets that extends (P, ω) and have the same rank-function as (P, ω). Then we may assume that there is a covering relation x ≺ y in Q_{1} which is not a covering relation in Q_{2}. Since |ρ(x) − ρ(y)| = 1 we must have y ≺ x in Q_{2}. Thus ω(x) precedes ω(y) in any permutation in L(Q_{1}, ω), and ω(y) precedes ω(x) in any permutation in L(Q_{2}, ω). Hence, the union is disjoint. □

We need two operations on labeled posets: Let (P, ϵ) and (Q, μ) be two labeled posets. The ordinal sum, P ⊕ Q, of two non-empty posets P and Q is the poset with the disjoint union of P and Q as underlying set and with partial order defined by x ≤ y if, either x ≤_{P} y or x ≤_{Q} y, or x ∈ P, y ∈ Q. Define two labelings of E(P ⊕ Q) by

(ϵ ⊕_{1} μ)(x, y) = ϵ(x, y) if (x, y) ∈ E(P),
(ϵ ⊕_{1} μ)(x, y) = μ(x, y) if (x, y) ∈ E(Q) and
(ϵ ⊕_{1} μ)(x, y) = 1 otherwise.
(ϵ ⊕_{−1} μ)(x, y) = ϵ(x, y) if (x, y) ∈ E(P),
(ϵ ⊕_{−1} μ)(x, y) = μ(x, y) if (x, y) ∈ E(Q) and
(ϵ ⊕_{−1} μ)(x, y) = −1 otherwise.

With a slight abuse of notation we write P ⊕_{±1} Q when the labelings of P and Q are understood from the context. Note that ordinal sums are associative, i.e., (P ⊕_{±1} Q) ⊕_{±1} R = P ⊕_{±1} (Q ⊕_{±1} R), and preserve the property of being signgraded. The following result is obtained easily by combinatorial reasoning, see [2, 14]:

Proposition 3.3. Let (P, ω) and (Q, ν) be two labeled posets. Then

W (P ⊕ Q, ω ⊕_{1} ν; t) = W (P, ω; t)W (Q, ν; t)

and

W (P ⊕ Q, ω ⊕_{−1} ν; t) = tW (P, ω; t)W (Q, ν; t).

Proposition 3.4. Suppose that (P, ω) is a saturated canonically labeled sign-graded poset. Then (P, ω) is the direct sum

(P, ω) = A_{0} ⊕_{1} A_{1} ⊕_{−1} A_{2} ⊕_{1} A_{3} ⊕_{−1} ⋯ ⊕_{±1} A_{k},

where the A_{i}s are anti-chains.

Proof. Let π ∈ L(P, ω). Then we may write π as π = w_{0}w_{1} ⋯ w_{k} where the w_{i}s are maximal words with respect to the property: If a and b are letters of w_{i} then ρ(ω^{−1}(a)) = ρ(ω^{−1}(b)). Then π ∈ J(Q, ω) where

(Q, ω) = A_{0} ⊕_{1} A_{1} ⊕_{−1} A_{2} ⊕_{1} A_{3} ⊕_{−1} ⋯ ⊕_{±1} A_{k},

and A_{i} is the anti-chain consisting of the elements ω^{−1}(a), where a is a letter of w_{i} (A_{i} is an anti-chain, since if x < y where x, y ∈ A_{i} there would be a letter in π between ω(x) and ω(y) whose rank was different than that of x, y). Now, (Q, ω) is saturated so P = Q. □

Note that the argument in the above proof also can be used to give a simple proof of Corollary 3.2 when ω is canonical. However, we wanted to prove Corollary 3.2 in its generality even though we only need it for canonical labelings.

4. The W -polynomial of a sign-graded poset

The space, S^{d}, of symmetric polynomials in ℝ[t] with center of symmetry d/2 has a basis

B_{d} = {t^{i}(1 + t)^{d−2i}}_{i=0}^{⌊d/2⌋}.

If h ∈ S^{d} has non-negative coefficients in this basis it follows immediately that the coefficients of h in the standard basis are unimodal. Let S_{+}^{d} be the non-negative span of B_{d}. Thus S_{+}^{d} is a cone. Another property of S_{+}^{d} is that if h ∈ S_{+}^{d} then it has the correct sign at −1 i.e.,

(−1)^{d/2}h(−1) ≥ 0.

Lemma 4.1. Let c, d ∈ ℕ. Then

S^{c}S^{d} ⊂ S^{c+d}
S_{+}^{c}S_{+}^{d} ⊂ S_{+}^{c+d}.

Suppose further that h ∈ S^{d} has positive leading coefficient and that all zeros of h are real and non-positive. Then h ∈ S_{+}^{d}.

Proof. The inclusions are obvious. Since t ∈ S_{+}^{2} and (1 + t) ∈ S_{+}^{1} we may assume that none of them divides h. But then we may collect the zeros of h in pairs θ and θ^{−1}. Let A_{θ} = −θ − θ^{−1}. Then

h = C ∏_{θ<−1}(t^{2} + A_{θ}t + 1),

where C > 0. Since A_{θ} > 2 we have

t^{2} + A_{θ}t + 1 = (t + 1)^{2} + (A_{θ} − 2)t ∈ S_{+}^{2},

and the lemma follows. □

We can now prove our main theorem.

Theorem 4.2. Suppose that (P, ω) is a sign-graded poset of rank r. Then W (P, ω; t) ∈ S_{+}^{p−r−1}.

Proof. By Corollary 2.4 and Lemma 2.5 we may assume that (P, ω) is canonically labeled. By Corollary 3.2 we know that

W (P, ω; t) = ∑_{Q} W (Q, ω; t),

where (Q, ω) are saturated and sign-graded with the same rank function as that of (P, ω). The W -polynomials of anti-chains are the Eulerian polynomials, which only have real non-negative zeros. By Proposition 3.4 and Proposition 3.3 the polynomial W (Q, ω; t) has only real non-positive zeros so by Lemma 4.1 and Corollary 2.4 we have W (Q, ω; t) ∈ S_{+}^{p−r−1}. The Theorem now follows since S_{+}^{p−r−1} is a cone. □

Corollary 4.3. Let (P, ω) be sign-graded of rank r then W (P, ω; t) is symmetric and its coefficients are unimodal. Moreover, W (P, ω; t) has the correct sign at −1, i.e.,

(−1)^{(p−1−r)/2}W (P, ω; −1) ≥ 0.

Corollary 4.4. Let P be a (naturally labeled) graded poset. Suppose that Δ_{eq}(P) is flag. Then the Charney-Davis Conjecture holds for Δ_{eq}(P).

If h(t) is any polynomial with integer coefficients and h(t) ∈ S^{d}, it follows that h(t) has integer coefficients in the basis t^{i}(1 + t)^{d−2i}. Thus we know that if (P, ω) is sign-graded of rank r, then

W (P, ω; t) = ∑_{i=0}^{⌊(p−r−1)/2⌋} a_{i}(P, ω)t^{i}(1 + t)^{p−r−1−2i},

where a_{i}(P, ω) are non-negative integers. It would be interesting to have a combinatorial interpretation of these coefficients, and thus a combinatorial proof of Theorem 4.2.

Let (P, ϵ) be a labeled poset. We say that (P, ϵ) admits a rank function if for every x ∈ P and saturated chain x_{0} ≺ x_{1} ≺ ⋯ ≺ x_{k} = x, where x_{0} is a minimal element, the quantity

ρ(x) = ∑_{i=1}^{k} ϵ(x_{i−1}, x_{i})

is the same. Hence, a labeled poset (P, ϵ) with a rank function is sign-graded if and only if ρ is constant on maximal elements.

Theorem 4.5. Suppose that (P, ϵ) admits a rank-function with values in {0, 1}. Then W (P, ϵ; t) has unimodal coefficients.

Proof. One may check that the proofs of Lemma 3.1, Corollary 3.2 and Proposition 3.4 holds for this case too. But then

W (P, ϵ; t) = ∑_{Q} W (Q, ϵ; t),

where W (Q, ϵ; t) is unimodal and symmetric with center of symmetry (p − 1)/2 or (p − 2)/2. The sum of such polynomials is again unimodal. □

5. The Charney-Davis quantity

In [7] Reiner, Stanton and Welker defined the Charney-Davis quantity of a graded naturally labeled poset (P, ω) of rank r to be

CD(P, ω) = (−1)^{(p−1−r)/2}W (P, ω; −1).

We may define it in the exact same way for sign-graded posets. Since the particular labeling does not matter we write CD(P). Let π = π_{1}π_{2} ⋯ π_{n} be any permutation. We say that π is alternating if π_{1} > π_{2} < π_{3} > ⋯ and reverse alternating if π_{1} < π_{2} > π_{3} < · · ·. Let (P, ω) be a canonically labeled sign-graded poset. If π ∈ L(P, ω) then we may write π as π = w_{0}w_{1} ⋯ w_{k} where w_{i} are maximal words with respect to the property: If a and b are letters of w_{i} then ρ(ω^{−1}(a)) = ρ(ω^{−1}(b)). The words w_{i} are called the components of π. The following theorem is well known, see for example [9], and gives the Charney-Davis quantity of an anti-chain.

Proposition 5.1. Let n ≥ 0 be an integer. Then (−1)^{(n−1)/2}A_{n}(−1) is equal to 0 if n is even and equal to the number of (reverse) alternating permutations of the set {1, 2, …, n} if n is odd.

Theorem 5.2. Let (P, ω) be a canonically labeled sign-graded poset. Then the Charney-Davis quantity, CD(P), is equal to the number of reverse alternating permutations in L(P, ω) such that all components have an odd numbers of letters.

Proof. It suffices to prove the theorem when (P, ω) is saturated. By Proposition 3.4 we know that

(P, ω) = A_{0} ⊕_{1} A_{1} ⊕_{−1} A_{2} ⊕_{1} A_{3} ⊕_{−1} ⋯ ⊕_{±1} A_{k},

where the A_{i}s are anti-chains. This means that CD(P) = CD(A_{0})CD(A_{1}) ⋯ CD(A_{k}). Let π = w_{0}w_{1} ⋯ w_{k} ∈ L(P, ω) where w_{i} is a permutation of ω(A_{i}). Then π is a reverse alternating such that all components have an odd numbers of letters if and only if, for all i, w_{i} is reverse alternating if i is even and alternating if i is odd. Hence, by Proposition 5.1, the number of such permutations is indeed CD(A_{0})CD(A_{1}) ⋯ CD(A_{k}). □

6. A characterization of sign-graded posets

Here we give a characterization of sign-graded posets along the lines of the characterization of graded posets given by Stanley in [10]. Let (P, ϵ) be any labeled poset. Define a function δ = δ_{ϵ} : P → ℤ by

δ(x) = max{∑_{i=1}^{ℓ} ϵ(x_{i−1}, x_{i})},

where x = x_{0} ≺ x_{1} ≺ ⋯ ≺ x_{ℓ} is any saturated chain starting at x and ending at a maximal element x_{ℓ}. Define a map Φ = Φ_{ϵ} : A(ϵ) → ℤ^{P} by

Φσ = σ + δ.

We have

δ(x) ≥ δ(y) + ϵ(x, y).  (6.1)

This means that Φσ(x) > Φσ(y) if ϵ(x, y) = 1 and Φσ(x) ≥ Φσ(y) if ϵ(x, y) = −1. Thus Φσ is a (P, −ϵ)-partition provided that Φσ(x) > 0 for all x ∈ P. But Φσ is order reversing so it attains its minimum at maximal elements and for maximal elements, z, we have Φσ(z) = σ(z). This shows that Φ : A(ϵ) → A(−ϵ) is an injection.

We say that a labeling ϵ of a poset P satisfies the δ-chain condition if for every x ∈ P and saturated chain x = x_{0} ≺ x_{1} ≺ ⋯ ≺ x_{ℓ}, where x_{ℓ} is a maximal element, the quantity

∑_{i=1}^{ℓ} ϵ(x_{i−1}, x_{i})

is the same.

Proposition 6.1. Let (P, ϵ) be labeled poset. Then Φ_{ϵ} : A(ϵ) → A(−ϵ) is a bijection if and only if ϵ satisfies the δ-chain condition.

Proof. If ϵ satisfies the δ-chain condition, then so does −ϵ and δ_{−ϵ}(x) = −δ_{ϵ}(x) for all x ∈ P. Thus the if part follows since the inverse of Φ_{ϵ} is Φ_{−ϵ}.

For the only if direction note that ϵ satisfies the δ-chain condition if and only if for all (x, y) ∈ E we have

δ(x) = δ(y) + ϵ(x, y)

If ϵ fails to satisfy the δ-chain property we have, by (6.1), that there is a covering relation (x, y) ∈ E such that either ϵ(x, y) = 1 and δ(x) ≥ δ(y) + 2 or ϵ(x, y) = −1 and δ(x) ≥ δ(y).

Suppose that ϵ(x, y) = 1. It is clear that there is a σ ∈ A(−ϵ) such that σ(x) = σ(y) + 1. But then

σ(x) − δ(x) ≤ σ(y) − δ(y) − 1,

so σ − δ ∉ A(ϵ).

Similarly, if ϵ(x, y) = −1 then we can find a partition σ ∈ A(−ϵ) with σ(x) = σ(y), and then

σ(x) − δ(x) ≤ σ(y) − δ(y),

so σ − δ ∉ A(ϵ). □

Define r(ϵ) by

r(ϵ) = max{∑_{i=1}^{ℓ} ϵ(x_{i−1}, x_{i}) : x_{0} ≺ x_{1} ≺ ⋯ ≺ x_{ℓ} is maximal}.

We then have:

max{Φσ(x) : x ∈ P } = max{σ(x) + δ_{ϵ}(x) : x is minimal}
≤ max{σ(x) : x ∈ P } + r(ϵ).

So if we let A_{n}(ϵ) be the (P, ϵ)-partitions with largest part at most n we have that Φ_{ϵ} : A_{n}(ϵ) → A_{n+r(ϵ)}(−ϵ) is an injection. A labeling ϵ of P is said to satisfy the λ-chain condition if for every x ∈ P there is a maximal chain c : x_{0} ≺ x_{1} ≺ ⋯ ≺ x_{ℓ} containing x such that ∑_{i=1}^{ℓ} ϵ(x_{i−1}, x_{i}) = r(ϵ).

Lemma 6.2. Suppose that n is a non-negative integer such that Ω(P, ϵ; n) ≠ 0. If

Ω(P, −ϵ; n + r(ϵ)) = Ω(P, ϵ; n)

then ϵ satisfies the λ-chain condition.

Proof. Define δ^{∗} : P → ℤ by

δ^{∗}(x) = max{∑_{i=1}^{ℓ} ϵ(x_{i−1}, x_{i})},

where the maximum is taken over all maximal chains starting at a minimal element and ending at x. Then

δ(x) + δ^{∗}(x) ≤ r(ϵ)  (6.2)

for all x, and ϵ satisfies the λ-chain condition if and only if we have equality in (6.2) for all x ∈ P. It is easy to see that the map Φ^{∗} : A_{n}(ϵ) → A_{n+r(ϵ)}(−ϵ) defined by

Φ^{∗}σ(x) = σ(x) + r(ϵ) − δ^{∗}(x),

is well-defined and is an injection. By (6.2) we have Φσ(x) ≤ Φ^{∗}σ(x) for all σ and all x ∈ P, with equality if and only if x is in a maximal chain of maximal weight. This means that in order for Φ : A_{n}(ϵ) → A_{n+r(ϵ)}(−ϵ) to be a bijection it is necessary for ϵ to satisfy the λ-chain condition. □

Theorem 6.3. Let ϵ be a labeling of P. Then

Ω(P, ϵ; t) = (−1)^{p}Ω(P, ϵ; −t − r(ϵ))

if and only if P is ϵ-graded of rank r(ϵ).

Proof. The ”if” part is Theorem 2.3, so suppose that the equality of the theorem holds. By reciprocity we have

(−1)^{p}Ω(P, ϵ; −t − r(ϵ)) = Ω(P, −ϵ; t + r(ϵ)),

and since Φ_{ϵ} : A_{n}(ϵ) → A_{n+r(ϵ)}(−ϵ) is an injection it is also a bijection. By Proposition 6.1, ϵ satisfies the δ-chain condition, and, by Lemma 6.2, we have that all minimal elements are members of maximal chains of maximal weight. In other words P is ϵ-graded. □

It should be noted that it is not necessary for P to be ϵ-graded in order for W (P, ϵ; t) to be symmetric. For example, if (P, ϵ) is any labeled poset then the W - polynomial of the disjoint union of (P, ϵ) and (P, −ϵ) is easily seen to be symmetric. However, we have the following:

Corollary 6.4. Suppose that

Ω(P, ϵ; t) = Ω(P, −ϵ; t + s),

for some s ∈ ℤ. Then −r(−ϵ) ≤ s ≤ r(ϵ), with equality if and only if P is ϵ-graded.

Proof. We have an injection Φ_{ϵ} : A_{n}(ϵ) → A_{n+r(ϵ)}(−ϵ). This means that s ≤ r(ϵ). The lower bound follows from the injection Φ_{−ϵ}, and the statement of equality follows from Theorem 6.3. □

References

[1] P. Brändén. On operators on polynomials preserving real-rootedness and the Neggers-Stanley conjecture. J.Algebraic Comb., to appear.

[2] F. Brenti. Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc., 81(413):viii+106, 1989.

[3] R. Charney and M. Davis. The Euler characteristic of a nonpositively curved, piecewise Euclidean manifold. Pacific J. Math., 171(1):117–137, 1995.

[4] D. Foata and M. Schützenberger. Théorie géométrique des polynômes eulériens. Lecture Notes in Mathematics, Vol. 138. Springer-Verlag, Berlin, 1970.

[5] V. Gasharov. On the Neggers-Stanley conjecture and the Eulerian polynomials. J. Combin. Theory Ser. A, 82(2):134–146, 1998.

[6] J. Neggers. Representations of finite partially ordered sets. J. Combin. Inform. System Sci., 3(3):113–133, 1978.

[7] V. Reiner, D. Stanton, and V. Welker. The Charney-Davis quantity for certain graded posets. Sém. Lothar. Combin., 50:Art. B50c, 13 pp. (electronic), 2003.

[8] V. Reiner and V. Welker. On the Charney-Davis and the Neggers-Stanley conjectures. http://www.math.umn.edu/˜ reiner/Papers/papers.html, 2002.

[9] L. W. Shapiro, W. J. Woan, and S. Getu. Runs, slides and moments. SIAM J. Algebraic Discrete Methods, 4(4):459–466, 1983.

[10] R. P. Stanley. Ordered structures and partitions. American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119.

[11] R. P. Stanley. The number of faces of simplicial polytopes and spheres. In Discrete geometry and convexity (New York, 1982), volume 440 of Ann. New York Acad. Sci., pages 212–223. New York Acad. Sci., New York, 1985.

[12] R. P. Stanley. Combinatorics and commutative algebra, volume 41 of Progress in Mathematics. Birkhäuser Boston Inc., Boston, MA, second edition, 1996.

[13] R. P. Stanley. Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1997.

[14] D. G. Wagner. Enumeration of functions from posets to chains. European J. Combin., 13(4):313–324, 1992.

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

E-mail address: branden@math.chalmers.se