ON THE CHARNEY-DAVIS AND NEGGERS-STANLEY CONJECTURES

VICTOR REINER AND VOLKMAR WELKER

Abstract. For a graded naturally labelled poset P, it is shown that the P -Eulerian polynomial

W (P, t) := ∑_{w∈L(P)} t^{des(w)}

counting linear extensions of P by their number of descents has symmetric and unimodal coefficient sequence, verifying the motivating consequence of the Neggers-Stanley conjecture on real zeroes for W (P, t) in these cases. The result is deduced from McMullen’s g-Theorem, by exhibiting a simplicial polytopal sphere whose hpolynomial is W (P, t).

Whenever this simplicial sphere turns out to be flag, that is, its minimal non-faces all have cardinality two, it is shown that the Neggers-Stanley Conjecture would imply the Charney-Davis Conjecture for this sphere. In particular, it is shown that the sphere is flag whenever the poset P has width at most 2. In this case, the sphere is shown to have a stronger geometric property (locally convexity), which then implies the Charney-Davis Conjecture in this case via a result from [27].

It is speculated that the proper context in which to view both of these conjectures may be the theory of Koszul algebras, and some evidence is presented.

1. Introduction

This paper has several goals. The first is to show that, in the context of the Neggers-Stanley Conjecture 1.2, for every graded poset P there is lurking in the background a polytopal simplicial sphere, which we will denote Δ_{eq}(P). This sphere is relevant for two purposes:

1991 Mathematics Subject Classification. 06A07, 13F55, 16S37, Key words and phrases. Charney-Davis conjecture, Neggers-Stanley conjecture,

Koszul algebra, partially ordered set, linear extension, order polytope, real roots, Polya frequency sequence.

First author supported by NSF grant DMS-9877047. Second author supported by DFG.

▷ The P -Eulerian polynomial (defined below) coincides with the h-polynomial of Δ_{eq}(P). As a consequence, its coefficients satisfy McMullen’s conditions for the h-vector of a simplicial polytope, and are in particular symmetric and unimodal. Thereby we verify the motivating consequence of the Neggers-Stanley Conjecture for naturally labeled graded posets (see discussion after the statement of Conjecture 1.2).

▷ Whenever the simplicial sphere Δ_{eq}(P) is flag, the Neggers-Stanley Conjecture 1.2 for P implies the Charney-Davis Conjecture for the sphere Δ_{eq}(P). Furthermore, when P has width at most 2, it is shown in Theorem 3.23 that Δ_{eq}(P) satisfies a stronger geometric condition than flag-ness known as local convexity, which implies the Charney-Davis Conjecture in this case by a result from [27].

The latter portion of the paper (Section 4 onward) is aimed toward the thesis that both the Charney-Davis and Neggers-Stanley Conjectures, along with some other combinatorial conjectures and results, should be considered in the context of the following question. Question 1.1. For which Koszul algebras is the Hilbert function a Polya frequency sequence?

To give a more precise discussion, we start by recalling the Neggers-Stanley Conjecture. For any partial order P on [n] := {1, 2, …, n}, let L(P) denote its set of linear extensions, that is the set of w = (w_{1}, …, w_{n}) ∈ 𝔖_{n} for which i <_{P} j implies w^{−1}(i) < w^{−1}(j). The P -Eulerian polynomial

W (P, t) := ∑_{w∈L(P)} t^{des(w)}

is the generating function for the linear extensions L(P) counted according to cardinality of their descent sets:

Des(w) := {i ∈ [n − 1] : w_{i} > w_{i+1}}
des(w) := # Des(w)

Conjecture 1.2 (Neggers-Stanley). For any labelled poset P on [n] the polynomial W (P, t) has only real (non-positive) zeroes.

We are mainly interested in the case where P is naturally labelled, that is i <_{P} j implies i < j.

Some history and context for the conjecture follows. For naturally labelled posets Conjecture 1.2 was made originally by Neggers [29], and generalized to the above statement by Stanley in 1986. When P is an antichain of n elements, W (P, t) is the Eulerian polynomial whose real-rootedness was shown by Harper [22] and served as an initial motivation for the conjecture. For the case when P is a naturally labelled disjoint union of chains the result is due to Simion [34]. This result was extended to arbitrary labellings by Brenti [5], who also verified the conjecture for Ferrers posets and Gaussian posets [5]. An important combinatorial implication of the real-rootedness of a polynomial with non-negative coefficients is the unimodality of the coefficients (i.e. for the sequence of coefficients a_{0}, …, a_{r} there is an index j such that a_{0} ≤ ⋯ ≤ a_{j} ≥ ⋯ ≥ a_{r}). Gasharov [17] verified the unimodality consequence of the conjecture for naturally labelled graded posets with at most 3 ranks. Corollary 3.15 verifies this (and something stronger) more generally for all naturally labelled graded posets.

Next, we recall the Charney-Davis Conjecture. Given an abstract simplicial complex Δ triangulating a (d − 1)-dimensional (homology) sphere, one can collate the face numbers f_{i}, which count the number of i-dimensional faces, into its f-vector and f-polynomial

\begin{aligned}f(Δ) & := (f_{−1}, f_{0}, f_{1}, …, f_{d−1}) \\ f(Δ, t) & := ∑_{i=0}^{d} f_{i−1}t^{i}. \end{aligned}

The h-polynomial and h-vector are easily seen to encode the same information:

(1.1)

h(Δ) := (h_{0}, h_{1}, …, h_{d}) where
h(Δ, t) = ∑_{i=0}^{d} h_{i}t^{i} satisfies
t^{d}h(Δ, t^{−1}) = [t^{d}f(Δ, t^{−1})]_{t↦t−1} .

The h-polynomial turns out to be a more convenient and natural encoding in several ways, closely related to commutative algebra, toric geometry, and shellability. For example, the fact that homology spheres are Cohen-Macaulay implies non-negativity of the h_{i}, and the Dehn-Sommerville equations for simplicial spheres assert that h_{i} = h_{d−i} for 0 ≤ i ≤ d (see [43, §II.6]). Note that the latter implies that the hpolynomial is symmetric, h(Δ, t) = t^{d}h(Δ, t^{−1}), and that h(Δ, −1) = 0 whenever d is odd.

The Charney-Davis Conjecture [9, Conjecture D] concerns the quantity h(Δ, −1) in the case where d is even and Δ is a simplicial homology (d − 1)-sphere which happens to be a flag complex, that is the minimal subsets of vertices which do not span a simplex all have cardinality two. For polytopal simplicial spheres Δ, this quantity is known [27] to coincide with the signature or index of the associated toric variety X_{Δ}. Conjecture 1.3 (Charney-Davis, Conjecture D [9]). When Δ is a flag simplicial homology (d − 1)-sphere and d is even, then

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

The first hint of a relation between these two conjectures comes from the following simple observation (cf. [9, Lemma 7.5]). Proposition 1.4. Let h(t) = h_{d}t^{d}+⋯+h_{1}t+h_{0} ∈ R[t] be a polynomial in t of even degree d with non-negative coefficients. If h(t) is symmetric and has only real zeroes, then

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

Proof. Since h(t) has degree d we have h_{d} ≠ 0 and by symmetry h_{0} ≠ 0. Thus h(t) has d zeroes which must then all be strictly negative since h_{i} ≥ 0 for 0 ≤ i ≤ d. Factor h(t) = h_{d} ∏_{i=1}^{d}(t − r_{i}) according to its (real) zeroes r_{i}. Symmetry of h(t) implies that r is a zero if and only if \frac{1}{r} is a zero. If r ≠ −1, exactly one of r, \frac{1}{r} is less than −1. Thus for a zero r, either r = −1 is a zero, in which case h(−1) = 0 and we are done, or else exactly half of the factors in the product h(−1) = h_{d} ∏_{i=1}^{d}(−1−r_{i}) are negative, implying that the product has sign (−1)^{\frac{d}{2}} . □

The paper is structured as follows.

Section 2 reviews some theory of P -partitions, order polytopes, and their canonical triangulations.

In Section 3.1 we show that when P is a graded poset, that is every maximal chain in P has the same number of elements r, there exists a simplicial sphere Δ_{eq}(P) of dimension #P − r − 1 such that

h(Δ_{eq}(P), t) = W (P, t).

Thus the Neggers-Stanley Conjecture for P implies the Charney-Davis Conjecture for Δ_{eq}(P) (whenever it is flag) via Proposition 1.4. Combinatorial interpretations for the (non-negative) Charney-Davis quantity (−1)^{\frac{#P −r}{2}} W (P, −1), for some cases of posets where the Neggers-Stanley Conjecture is known, are explored in [33].

In Section 3.2 it is shown that the sphere Δ_{eq}(P) is the boundary complex of a simplicial convex polytope. Therefore by McMullen’s g-Theorem characterizing the number of faces of such polytopes [37], the coefficients (h_{0}, h_{1}, …, h_{#P −r}) are symmetric and unimodal.

Convexity has further relevance. In [27] it was shown via the Hirzebruch signature formula that the Charney-Davis Conjecture holds for a simplicial polytope under a certain geometric hypothesis (local convexity) stronger than being flag. We show in Section 3.2 that this hypothesis holds for Δ_{eq}(P) whenever P has width (i.e. size of the largest antichain) at most 2, thereby providing more evidence for the Neggers-Stanley Conjecture.

In Sections 4 and 5 we gather evidence for the thesis that both of these conjectures can be fruitfully viewed within the context of Koszul algebras. In particular, we point out ways in which Hilbert series of Koszul algebras interact well with the theory of Polya frequency series and polynomials with real zeroes.

2. Review: P -Partitions and Order Polytopes

In this section we review some of the theory of P -partitions, distributive lattices and order polytopes; see [23, 25, 24, 36, 38] for proofs and more details. Also see [16, §1.2] for definitions and basic facts about polyhedral cones and fans.

Given a naturally labelled poset P on [n] ordered by ≤_{P}, the vector space of functions f = (f(1), …, f(n)) : P → R will be identified with R^{n}. One says that f is a P -partition if f(i) ≥ 0 for all i and f(i) ≥ f(j) for all i <_{P} j. Denote by A(P) the cone of all P -partitions in R^{n}. The convex polytope

O(P) = A(P) ∩ [0, 1]^{n}

is called the order polytope of P. An order ideal I in P is a subset of P such that i ∈ I and j <_{P} i implies j ∈ I. It is known that O(P) is the convex hull of the characteristic vectors χ_{I} ∈ {0, 1}^{n} as I runs through all order ideals I in P.

A useful alternative way to view O(P) is provided by the fact that it is isometric to the hyperplane slice at x_{0} = 1 of the cone A(P^{0}) ⊂ R^{n+1}, where P^{0} is the naturally labelled poset on [0, n] := {0, 1, …, n} obtained from P by adjoining a new minimum element 0. We call the cone A(P^{0}) the homogenization of the cone A(P).

We recall a few basic definitions some of which were already mentioned in the introduction. The set of permutations w = (w_{1}, …, w_{n}) ∈ 𝔖_{n} which extend P to a linear order is called its Jordan-Hölder set

L(P) := {w = (w_{1}, …, w_{n}) ∈ 𝔖_{n} : i <_{P} j implies w^{−1}(i) < w^{−1}(j)}.

The descent set and descent number of w are defined by

Des(w) := {i ∈ [n − 1] : w_{i} > w_{i+1}}
des(w) := # Des(w).

Define a cone for each w ∈ 𝔖_{n}

A(w) := {f ∈ R^{n} :
f(w_{i}) ≥ f(w_{i+1}) for i ∈ [n − 1],
f(w_{i}) > f(w_{i+1}) if i ∈ Des(w)}

It is not hard to see that the closure of A(w) (defined by removing the strict inequalities above), is a unimodular (simplicial) cone, that is its extreme rays are spanned by a set of vectors forming a lattice basis for Z^{n}. Similarly, the closure of A(w) ∩ [0, 1]^{n} is a unimodular simplex. Now we are in position to formulate the basic fact from the theory of P -partitions which will be crucial for subsequent arguments.

Proposition 2.1.

(i) The cone of P -partitions decomposes into a disjoint union as follows:

A(P) = ⊔_{w∈L(P)}A(w)

The closures of the cones A(w) for w ∈ L(P) give a unimodular triangulation of A(P).

(ii) The unimodular triangulation of A(P) described in (i) restricts to a unimodular triangulation of the order polytope

O(P) = ⊔_{w∈L(P)}A(w) ∩ [0, 1]^{n}.

We call the triangulations of A(P) (into simplicial cones) and O(P) (into simplices) from Proposition 2.1 their canonical triangulations. Note that via homogenization the canonical triangulation of O(P) is easily seen to be the restriction of the canonical triangulation of the homogenized cone A(P^{0}) to the hyperplane x_{0} = 1. This makes sense since there is an obvious bijection between the linear extensions L(P^{0}) and L(P).

The combinatorics of these triangulations is closely related to the distributive lattice J(P) of all order ideals I in P ordered by inclusion. The order complex ΔJ(P) is the abstract simplicial complex having a vertex for each ideal I in P and a simplex for each chain I_{1} ⊂ … ⊂ I_{t} of nested ideals. Given a set of vectors V ⊂ R^{n}, define their positive span to be the (relatively open) cone

pos(V) := {∑_{v∈V} c_{v} · v : c_{v} ∈ R, c_{v} > 0} .

Proposition 2.2.

(i) Every non-zero P -partition f ∈ A_{P} can be uniquely expressed in the form

f = ∑_{i=1}^{t} c_{i}χ_{I_{i}}

where the c_{i} are positive reals, and I_{1} ⊂ ⋯ ⊂ I_{t} is a chain of ideals in P. In other words,

A(P) = ⨆_{ideals I_{1}⊂···⊂I_{t}⊂P} pos ({χ_{I_{t}}}_{i=1}^{t}).

(ii) The canonical triangulation of the order polytope O(P) is isomorphic (as an abstract simplicial complex) to ΔJ(P), via an isomorphism sending an ideal I to its characteristic vector χ_{I}.

(iii) The lexicographic order of permutations in L(P) gives rise to a

shelling order on ΔJ(P). (iv) In this shelling, for each w in L(P), the minimal face of its cor-

responding simplex in ΔJ(P) which is not contained in a lexicographically earlier simplex is spanned by the ideals {w_{1}, w_{2}, …, w_{i}} where i ∈ Des(w).

Using basic facts about shellings (see [3]), part (iv) of the preceding proposition implies that one can re-interpret the polynomial W (P, t):

(2.1)  W (P, t) := ∑_{w∈L(P)} t^{des(w)} = h(ΔJ(P), t)

This connection with J(P) also allows one to re-interpret these results in terms of Ehrhart polynomials. Recall that for a convex polytope Q in R^{n} having vertices in Z^{n}, the number of lattice points contained in an integer dilation dQ grows as a polynomial in the dilation factor d ∈ N. This polynomial in d is called the Ehrhart polynomial:

Ehrhart(O(Q), d) := #(dO(P) ∩ N^{n}).

Whenever Q has a unimodular triangulation abstractly isomorphic to a simplicial complex Δ, there is the following relationship:

(2.2)  ∑_{d≥0} Ehrhart(O(Q), d) t^{d} = \frac{h(Δ, t)}{(1 − t)^{n}} .

3. The Equatorial Sphere for a Graded Poset

3.1. Definition and main properties. In this section we exhibit for every graded naturally labelled poset P on [n] having r ranks an alternative triangulation of the order polytope O(P), which we call the equatorial triangulation. This triangulation has several pleasant properties, proven in this and the next subsection, which may be summarized as follows:

▷ It is a unimodular triangulation.

(See Proposition 3.6) ▷ It is isomorphic, as an abstract simplicial complex, to the join of an r-simplex with a simplicial (#P − r − 1)-sphere, which we will denote Δ_{eq}(P), and call the equatorial sphere. (See Corollary 3.8)

▷ h(Δ_{eq}(P), t) = h(ΔJ(P), t) = W (P, t).

(See Corollary 3.8) ▷ The equatorial sphere Δ_{eq}(P) is polytopal, and hence shellable

and a PL-sphere. (See Theorem 3.14)

▷ When P has width at most 2, the equatorial sphere Δ_{eq}(P) is realized by a locally convex simplicial fan. Hence is a flag subcomplex of ΔJ(P), and a flag sphere for which the Charney-Davis Conjecture holds. (See Theorem 3.23)

Example 3.1. Let P be the graded naturally labelled poset on [4] with r = 2 ranks shown in Figure 1(a). Let J(P) be its associated (distributive) lattice of order ideals (see Figure 1(b)).

The 4-dimensional order polytope O(P), and its canonical triangulation by ΔJ(P), may be “visualized” as follows. Start with the convex pentagon π which is the convex hull of

{χ_{1}, χ_{2}, χ_{12}, χ_{13}, χ_{123}, χ_{124}},

and triangulate π as shown in Figure 1(c). The canonical triangulation is obtained by taking the simplicial join of this triangulation of π with the edge {χ_{∅}, χ_{1234}}.

The equatorial triangulation (see Proposition 3.6) is obtained starting from the alternate triangulation of π depicted in Figure 1(d) and taking the simplicial join with the edge {χ_{∅}, χ_{1234}}. Equivalently, it is obtained from the equatorial 1-sphere Δ_{eq}(P) depicted in Figure 1(e) and taking the simplicial join with the triangle {χ_{∅}, χ_{12}, χ_{1234}}.

Fix a naturally labelled poset P on [n], and assume that it is graded, with r rank sets P_{1}, …, P_{r}. The following are the key definitions.

Definition 3.2. A P -partition f will be called rank-constant if it is constant along ranks, i.e. f(p) = f(q) whenever p, q ∈ P_{j} for some j.

A P -partition f will be called equatorial if min_{p∈P} f(p) = 0 and for every j ∈ [2, r] there exists a covering relation between ranks j − 1, j Figure 1. (a) A graded poset P. (b) The distributive lattice of order ideals J(P). (c) Part of the canonical triangulation ΔJ(P) of its order polytope O(P). (d) The analogous part of the equatorial triangulation. (e) The equatorial 1-sphere Δ_{eq}(P).

in P along which f is constant, i.e. there exist p_{j−1} <_{P} p_{j} with

p_{j−1} ∈ P_{j−1}, p_{j} ∈ P_{j} and f(p_{j−1}) = f(p_{j}).

An order ideal I in P will be called rank-constant (resp. equatorial) if its characteristic vector χ_{I} is rank-constant (resp. equatorial). More generally, a collection of ideals {I_{1}, …, I_{t}} forming a chain I_{1} ⊂ … ⊂ I_{t} will be called rank-constant (resp. equatorial) if the sum χ_{I_{1}} + … + χ_{I_{t}} (or equivalently, any vector in the cone pos({χ_{I_{j}}}_{j=1}^{t}) is rank-constant (resp. equatorial).

Note that the only rank-constant ideals are the ones in the chain

∅ = I_{0}^{rc} ⊂ I_{1}^{rc} ⊂ ⋯ ⊂ I_{r}^{rc} = P

where I_{j}^{rc} := ⊔_{i≤j}P_{i}. Also note that the only P -partition which is both rank-constant and equatorial is the zero P -partition f(p) = 0. Thus the only rank-constant and equatorial order ideal is I_{0}^{rc} = ∅. Proposition 3.3. Every non-zero P -partition f can be uniquely expressed as

f = f^{rc} + f^{eq},

where f^{rc}, f^{eq} are rank-constant and equatorial P -partitions, respectively.

Proof. To show existence, for j ∈ [r − 1] define non-negative constants

\begin{aligned}c_{j} & := min \{f(p_{j−1}) − f(p_{j}) : p_{j−1} ∈ P_{j−1}, p_{j} ∈ P_{j}, p_{j−1} <_{P} p_{j}\} \\ c_{r} & := min\{f(p_{r}) : p_{r} ∈ P_{r}\}, \end{aligned}

and set

\begin{aligned}f^{rc} & := ∑_{j=1}^{r} c_{j}χ_{I_{j}^{rc}} \\ f^{eq} & := f − f^{rc}. \end{aligned}

Obviously f^{rc} is a rank-constant P -partition. It is a straightforward verification, left to the reader, that f^{eq} is a P -partition, and that it is equatorial by construction.

For uniqueness, assume f = g^{rc} + g^{eq} is an additive decomposition of f into a rank-constant and an equatorial P -partition. It is again straightforward to show that the equatoriality of g^{eq} and rankconstancy of g^{rc} forces g^{rc} = ∑_{j=1}^{r} c_{j}χ_{I_{j}^{rc}}, where c_{j} is defined as above in terms of f. □

We wish to deduce our equatorial triangulation of A(P) from Proposition 3.3, and for this we need to understand both rank-constant and equatorial chains of ideals better. Equatoriality and rank-constancy of a chain of ideals I_{1} ⊂ … ⊂ I_{t} are intimately related with properties of its jumps

J_{i} := I_{i} − I_{i−1} for i = 1, …, t + 1

(where by convention I_{0} := ∅, I_{t+1} = P).

It is easy to see that the rank-constant P -partitions form an rdimensional simplicial subcone within the n-dimensional cone A(P), and that this subcone is the non-negative span of the vectors {χ_{I_{j}^{rc}}}_{j=1}^{r}. Proposition 3.4. The rank-constant subcone of A(P) is interior, that is, it does not lie in the boundary subcomplex of the cone A(P).

Proof. In a triangulation of a polyhedral cone, a subcone lies on the boundary if and only if it is contained in a codimension one subcone that lies on the boundary. For codimension one subcones, lying in the boundary is equivalent to being contained in a unique top dimensional subcone. Specializing to the case of the canonical triangulation of the cone A(P) from Proposition 2.1, one sees that this means a chain of ideals I_{1} ⊂ ⋯ ⊂ I_{t} corresponds to a subcone on the boundary if and only if one of at least one of its jumps J_{i} contains a pair of elements which are comparable in P. But for I_{1}^{rc} ⊂ ⋯ ⊂ I_{r}^{rc}, since the jumps J_{i} = I_{i}^{rc} − I_{i−1}^{rc} = P_{i} are antichains, this property fails to hold. □

Proposition 3.5. A chain of non-empty ideals I_{1} ⊂ … ⊂ I_{t}, is equatorial if and only if its jumps J_{i} have the following property: For every j ∈ [2, r], there exist p_{j−1} <_{P} p_{j} with p_{j−1} ∈ P_{j−1}, p_{j} ∈ P_{j} and a value i ∈ [t + 1], such that p_{j−1}, p_{j} ∈ J_{i}.

The chain I_{1} ⊂ … ⊂ I_{t} is maximal with respect to the equatorial property if and only if its jumps J_{i} for i ∈ [t + 1] satisfy the following two conditions:

(i) The J_{i} are all maximal (saturated) chains in P, possibly singletons.

(ii) The non-singleton J_{i} can be re-ordered J_{i_{1}}, J_{i_{2}}, …, J_{i_{s}} so that min_{J_{i_{1}}} has rank 1, max_{J_{is}} has rank r, and max J_{i_{k}}, min J_{i_{k+1}} have the same rank in P for k ∈ [s − 1].

Consequently, t = n−r for any maximal equatorial chain of non-empty ideals.

Proof. Since the jumps J_{i} are the domains on which the associated P - partition χ_{I_{1}} + … + χ_{I_{t}} is constant, the first assertion is direct from Definition 3.2.

It is then easy to see that a chain of non-empty ideals having properties (i), (ii) will be equatorial, and maximal with respect to refinement. Conversely, suppose one is given a maximal equatorial chain of nonempty ideals. If there exists an incomparable pair p, p′ in one of its jumps J_{i}, it is straightforward to check that one can refine the chain further while preserving the equatorial property, e.g. by adding in the ideal I_{i−1} ∪ {q ∈ J_{i} : q ≤ p}. Thus each jump J_{i} must be a maximal chain, proving (i). Furthermore, the pairs of adjacent ranks {j − 1, j} spanned by two different jumps J_{i}, J_{i′} must be disjoint, else one could refine the chain equatorially by “breaking” J_{i} between two such ranks {j − 1, j} which they share. The jumps J_{i} must then disjointly cover all possible adjacent rank pairs {j − 1, j}_{j=2}^{r}, so they can be re-ordered as in (ii). □

Proposition 3.6. The collection of all cones

pos ({χ_{I} : I ∈ R ∪ E}),

where R (resp. E) is a chain of non-empty rank-constant (resp. equatorial) ideals in P, gives a unimodular triangulation of the cone of P -partitions A(P).

Proof. First we check that these polytopal cones indeed decompose A(P). Given f ∈ A, write f = f^{rc} + f^{eq} as in Proposition 3.3. Then use these easy facts:

▷ f^{rc} lies in the cone of rank-constant P -partitions, which is the simplicial cone positively spanned by the (non-empty) rankconstant ideals {I_{j}^{rc}}_{j=1}^{r},

▷ When f^{eq} is expressed in the unique way as a positive combination of characteristic vectors of a chain of ideals, as in Proposition 2.2 part (i), this chain of ideals must be equatorial since f^{eq} is.

It remains to check that all such cones are unimodular. Thus it suffices to show that whenever R ∪ E is maximal under inclusion, then #R ∪ E = n and the Z-span of the set {χ_{I} : I ∈ R ∪ E} additively generates inside R^{n} is the full integer lattice Z^{n}. To see #R ∪ E = n, first note that when R ∪ E is maximal, one has R = {I_{j}^{rc}}_{j=1}^{r}, and then #E = n − r follows from Proposition 3.5. To show they additively generate Z^{n}, we show by induction on the rank r of P that the subgroup they generate contains each standard basis vector e_{p} for p ∈ P. The base case r = 1 has P an antichain, hence all ideals I ⊊ P are equatorial, so the cones in question coincide with the cones in the canonical triangulation, which are unimodular by Proposition 2.1. In the inductive step, note that this subgroup generated by {χ_{I} : I ∈ R ∪ E} has the alternate description as the subgroup generated by the characteristic vectors χ_{P_{j}} of all of the ranks of P along with the characteristic vectors χ_{J_{i}} of all of the jumps between the equatorial ideals in E. Proposition 3.5 shows that there will be exactly one element q of the top rank r in P which does not occur in a singleton jump J_{i}. Namely, q = max J_{i_{s}} after the re-labelling as in Proposition 3.6. Hence for every p ∈ P_{r} − {q}, one has e_{p} in the subgroup, but then one also has e_{q} in the subgroup, since the subgroup contains χ_{P_{r}}. Now apply induction to the graded poset P − P_{r} of rank r − 1, replacing the ideals in R ∪ E by their intersections with P − P_{r} and removing multiple copies of the same ideal created by the intersection process. □

The triangulation of A(P) given in Proposition 3.6 induces a unimodular triangulation of O(P), which we will call the equatorial triangulation of O(P).

Definition 3.7. The equatorial complex Δ_{eq}(P) is defined to be the subcomplex of the order complex ΔJ(P) whose faces are indexed by the equatorial chains of non-empty ideals.

For the formulation of the next corollary we need the concept of simplicial join. For two simplicial complexes Δ_{1}, Δ_{2} which are defined over disjoint vertex sets, the simplicial join Δ_{1} ∗ Δ_{2} is the simplicial complex {σ_{1} ∪ σ_{2} : σ_{i} ∈ Δ_{i}, i = 1, 2}. Note that we always assume that the empty face ∅ is a face of a simplicial complex. Corollary 3.8. The equatorial triangulation of the order polytope O(P) is abstractly isomorphic to the simplicial join σ^{r} ∗ Δ_{eq}(P), where σ^{r} is the interior r-simplex spanned by the chain of rank-constant ideals {I_{j}^{rc}}_{j=0}^{r}. As a consequence of its unimodularity, one has

h(Δ_{eq}(P), t) = h(ΔJ(P), t) = W (P, t).

Proof. The first assertion follows directly from Proposition 3.6, noting that σ_{r} is interior due to Proposition 3.4. For the second, note that both σ^{r} ∗ Δ_{eq}(P) and ΔJ(P) index unimodular triangulations of the order polytope, so (2.2) implies

h(σ^{r} ∗ Δ_{eq}(P), t) = h(ΔJ(P), t).

On the other hand, the defining equation (1.1) of the h-polynomial shows that

f(Δ_{1} ∗ Δ_{2}, t) = f(Δ_{1}, t) ∗ f(Δ_{2}, t)
h(Δ_{1} ∗ Δ_{2}, t) = h(Δ_{1}, t) ∗ h(Δ_{2}, t)
h(σ^{r}, t) = 1,

and hence h(σ^{r} ∗ Δ, t) = h(Δ, t). □

Remark 3.9. Corollary 3.8 has the following consequence: for a graded poset P, the set of linear extensions L(P) is equinumerous with the set L_{eq}(P) of all maximal equatorial chains of ideals in P, as both coincide with [W (P, t)]_{t=1}.

This begs for a bijection ϕ : L(P) → L_{eq}(P). The authors thank Dennis White [50] for supplying one which is elegant, using the idea of jeu-de-taquin on linear extensions of P, thought of as P -shaped tableaux that use each entry 1, 2, …, n exactly once. Given such a linear extension w, replace the highest label n (at top rank r) by a jeu-de-taquin hole, and slide it past other entries down to rank 1, duplicating the last entry that it slid past in the hole’s resting position at rank 1. Then repeat this with the entry n − 1, sliding it down to rank 2, and similarly with the entries n − 2, n − 3, ..., n − r + 1. The result is a P -shaped tableaux that can be interpreted as an equatorial P -partition, compatible with a unique maximal equatorial chain of ideals ϕ(w). It is not hard to check that this map w ↦ ϕ(w) is a bijection.

3.2. Geometric and Convexity Properties of Δ_{eq}(P). In this section, we use convexity and the concrete geometric realization of Δ_{eq}(P) to learn more about it. Definition 3.10. The rank-constant subspace V^{rc} ⊂ R^{n} is the R-linear span of the set {χ_{I_{j}^{rc}}}_{j=1}^{r}.

Let Q be a convex polytope, and V a linear subspace, both inside R^{n}. Then there is a well defined quotient polytope

Q/V := {q + V : q ∈ Q} ⊂ R^{n}/V.

If π : R^{n} → R^{n−dim V} is any linear surjection with kernel V (such as an orthogonal projection onto V^{⊥}), then the polytope Q/V can be identified with the image π(Q). Also note that if V is a rational subspace of R^{n} with respect to the integer lattice Z^{n} ⊂ R^{n}, the quotient lattice Z^{n}/(V ∩ Z^{n}) is well-defined, and a full rank sublattice in R^{n}/V. Proposition 3.11. The collection of quotient cones

{C_{E} = pos ({χ_{I} : I ∈ E}) + V^{rc}} ,

as E runs through all equatorial chains of non-empty ideals in P, forms a complete simplicial fan in R^{n}/V^{rc}.

(i) This simplicial fan is unimodular with respect to the quotient lattice Z^{n}/(V^{rc} ∩ Z^{n}).

(ii) The simplices (C_{E} ∩ O(P)) + V^{rc} form a unimodular triangula-

tion of the quotient polytope O_{eq}(P) := O(P)/V^{rc}. (iii) This triangulation of O(P)/V^{rc} is isomorphic, as an abstract

simplicial complex, to the cone 0∗Δ_{eq}(P) with base Δ_{eq}(P) and apex at the interior point 0 = V^{rc}.

Consequently, Δ_{eq}(P) triangulates the (n−r−1)-dimensional boundary sphere ∂O_{eq}(P).

Proof. Apply the following general statement, Proposition 3.12, about polytopes (and the analogous statement about fans) with

Q = O(P),
Δ = the equatorial triangulation,
Δ′ = Δ_{eq}(P),
V = V^{rc}.

□

Proposition 3.12. Let Q be an n-dimensional convex polytope in R^{n}. Assume Q has a triangulation abstractly isomorphic to a simplicial complex Δ of the form Δ ≅ σ^{r} ∗ Δ′, where σ^{r} is an r-simplex not lying on the boundary of Q. Let V be the r-dimensional linear subspace parallel to the affine span of the vertices of σ_{r}.

Then the quotient (n − r)-dimensional polytope Q/V ⊂ R^{n}/V inherits a triangulation abstractly isomorphic to σ^{0} ∗ Δ′, where σ^{0} is an interior point of Q/V ⊂ R^{n}/V.

Furthermore, when V is rational with respect to Z^{n} ⊂ R^{n} and if the triangulation of Q is unimodular with respect to Z^{n}, then the triangulation of Q/V^{rc} is unimodular with respect to Z^{n}/(V^{rc} ∩ Z^{n}).

The proof of Proposition 3.12 is straightforward. We leave it as an exercise.

Proposition 3.11, shows that Δ_{eq}(P) corresponds to a complete unimodular fan. This fact suffices to infer both that it is spherical, and that it corresponds to a smooth, complete toric variety X_{Δ_{eq}(P)} (see [16, §2.1]). Our next goal will be to show that Δ_{eq}(P) corresponds to a polytopal fan, as this has multiple consequences; see Corollary 3.15 below.

We prove polytopality of Δ_{eq}(P) by choosing for each equatorial ideal I of P a point on its ray pos(χ_{I} + V^{rc}) so that the convex hull of all such points is a simplicial polytope having Δ_{eq}(P) as its boundary complex. Here we employ the following strategy. We start with the (usually) non-simplicial polytope O_{eq}(P) and pull each of its vertices in a certain order to produce a simplicial polytope with boundary complex Δ_{eq}(P).

Recall [28, §2.5] that if Q is a convex polytope, one pulls the vertex v in Q to produce a new polytope pull_{v}(Q) by taking the convex hull after moving v slightly outward past the supporting hyperplanes of all facets that contain v, but past no other facet-supporting hyperplanes of Q. Assuming that Q contains the origin in its interior, this can clearly be achieved by replacing v with (1 + ϵ)v where ϵ > 0 is sufficiently small.

We will require the following proposition describing the 1-skeleton resulting from pulling all the vertices of a polytope:

Proposition 3.13. Let Q̂ be the polytope resulting from pulling all of the vertices of a polytope Q in some order v_{1}, v_{2}, …, and let v̂_{i} denote the corresponding vertices in Q̂.

Then two vertices v̂_{j}, v̂_{k} will not form a boundary edge of Q̂ if and only if the unique smallest face F of Q containing v_{j}, v_{k} is either Q itself, or contains a vertex v_{i} with i < j, k.

Proof. The basic fact about pulling [28, Theorem 2.5.23] is that the faces of pull_{v}(Q) correspond either to faces of Q that do not contain v, or faces which are cones of the form v̂ ∗ F where F is a face not containing v inside a facet of Q that does contain v.

This implies the following two facts.

(a) If v_{j}, v_{k} do not lie on some common boundary face, the edge {v_{j}, v_{k}} will never be introduced by pulling.

(b) When one pulls Q at a sequence of vertices that do not lie on a face F of Q, then the face F will remain unsubdivided.

Thus if F is the unique smallest face of Q containing v_{j} and v_{k}, it will remain unsubdivided until one pulls the first vertex v_{i} in the sequence that lies on F. By replacing Q with pull_{v_{i−1}}(⋯ pull_{v_{1}}(Q) ⋯), one may assume without loss of generality that i = 1. We may also assume that F is a boundary face of Q.

If 1 ∉ {j, k}, then we claim that v_{j}, v_{k} no longer lie in any common boundary facet of pull_{v_{1}}(Q) (and hence will never form an edge after any subsequent pullings). To see this, assume there was such a facet G. If G does not contain v_{1}, then by fact (b) above, G is a face of Q̂. But since it contains both v_{j}, v_{k}, it would also contain v_{1} because v_{1} ∈ F ⊂ G, a contradiction. If G contains v_{1}, then G = v_{1} ∗ G′ for some face G′ of Q not containing v_{1}. But then G′ must contain both v_{j} and v_{k}, since G does, Hence the same reasoning as for G applies to G′ and then G′ must contain v_{1}, again a contradiction.

If 1 ∈ {j, k}, say v_{j} = v_{1}, then when one pulls v_{j} one creates the edge {v_{j}, v_{k}}, as v_{k} lies on any facet of Q containing F. Then this edge will persist during all subsequent pullings. Thus in this case {v̂_{j}, v̂_{k}} will be an edge of Q̂. □

Theorem 3.14. The equatorial complex Δ_{eq}(P) can be realized as the boundary complex of a polytope.

Proof. We construct a polytope Q such that Δ_{eq}(P) is its boundary complex by pulling the vertices

{v_{I} := χ_{I} + V^{rc}, I an equatorial ideal in P },

of O_{eq}(P) in any linear order which is compatible with the cardinality of the equatorial ideals I, that is, in any order where smaller ideals come earlier.

We will show that whenever {v_{I_{1}}, … v_{I_{k}}} spans a face of of Q, then {I_{1}, … I_{k}} is an equatorial chain of ideals. This would suffice since it would imply that the simplicial sphere Δ which is the boundary of the pulled polytope Q is a subcomplex of Δ_{eq}(P). However, both triangulate an (n − r − 1)-sphere, and hence one cannot be properly contained in the other. Thus they must coincide.

We prove the contrapositive: given equatorial ideals I_{1}, … I_{k} such that the set {I_{1}, … I_{k}} is not equatorial, we will show that {v_{I_{1}}, … v_{I_{k}}} does not span a face of Q. Denote by F the unique smallest face F of O_{eq}(P) containing {v_{I_{1}}, … v_{I_{k}}}. Pick a linear functional f : R^{n} → R which supports the face F of O_{eq}(P). This means

▷ f is a linear functional on R^{n} that descends to a linear functional on the quotient R^{n}/V^{rc}. In other words, f restricts to 0 or equivalently, f(χ_{P_{j}}) = 0 for any rank P_{j} of P.

▷ f assumes its maximum value M among all equatorial ideals at the vertices in F, i.e.

M := f(v_{I_{1}}) = ⋯ = f(v_{I_{k}}) ≥ f(v_{I}) for all ideals I

Note that M > 0 whenever F is a proper face of O_{eq}(P), since we know from Proposition 3.11(iii) that the origin 0 = V^{rc} in R^{n}/V^{rc} is actually an interior point of O_{eq}(P).

There are then two cases for the non-equatorial set {I_{1}, … I_{k}}.

Case 1. {I_{1}, … I_{k}} is not totally ordered by inclusion. In this case, there is some pair of ideals J, K among them which are not nested, and one has

(3.1)  f(v_{J}) + f(v_{K}) = f(v_{J∩K}) + f(v_{J∪K}).

Note that J ∩ K and J ∪ K are both ideals in P, and whether they are equatorial or not, they satisfy f(v_{J∩K}), f(v_{J∪K}) ≤ M. Since f(v_{J}) = f(v_{K}) = M, the equation (3.1) forces f(v_{J∩K}) = f(v_{J∪K}) = M. This means that both J ∩ K, J ∪ K lie on the face F. Thus we can choose I := J ∩ K in this case, and #I < #J, #K. Hence v_{I} would have been pulled before v_{J}, v_{K}. By Proposition 3.13 this shows v_{J}, v_{K} do not span a face of Q, and hence neither does its superset {v_{I_{1}}, … v_{I_{k}}}.

Case 2. I_{1} ⊂ ⋯ ⊂ I_{k} are nested, but still do not form an equatorial chain. In this case we will show that F is the entire polytope O_{eq}(P).

Because {I_{1}, … I_{k}} is not equatorial there exists a value j ∈ [1, r −1] such that no covering pair between ranks j, j + 1 lies entirely in any of its jumps J_{i} := I_{i} − I_{i−1}. For each ℓ = 1, 2, …, k − 1 define new sets

I′_{ℓ} := (I_{ℓ+1} − I_{j}^{rc}) ∪ I_{ℓ}.

We first claim that each I′_{ℓ} is an order ideal of P. If not, then without loss of generality there exists some covering relation p′ ⋖ p in with p ∈ I′_{ℓ} but p′ ∉ I′_{ℓ}. Because I_{ℓ} is an ideal, we may assume p ∉ I_{ℓ}. Then p ∈ I_{ℓ+1} − I_{j}^{rc}, which forces p′ ∈ I_{ℓ+1} because the latter is an ideal. Hence p′ ∈ I_{j}^{rc}, which means that p′ ⋖ p is a covering relation between ranks j, j + 1, and thus {p′, p} ⊄ J_{ℓ+1} = I_{ℓ+1} − I_{ℓ}. From this one has that p′ ∈ I_{ℓ} ⊂ I′_{ℓ}, a contradiction.

We next prove that

(3.2)  f(v_{I_{1}}) + ⋯ + f(v_{I_{k}}) = f(v_{I_{j}^{rc}}) + f(v_{I′_{1}}) + ⋯ + f(v_{I′_{k−1}}).

by checking that the coefficient of the standard basis vector e_{p} for any p ∈ P is the same on both sides. We check this in two cases, depending upon whether r(p) ≤ j. In either case, define

i_{0} := min{i : p ∈ I_{i}}.

In the case r(p) ≥ j + 1, note that p ∉ I_{1} else the jump J_{1} would contain some covering relation between ranks j, j + 1 by following a chain downward from p. Thus i_{0} ≥ 2, and hence e_{p} appears once each in v_{I_{i_{0}}}, v_{I_{i_{0}+1}}, …, v_{I_{k}} on the left side, and once each in v_{I′_{i_{0}−1}}, v_{I_{i_{0}}}, …, v_{I_{k−1}} on the right.

In the case r(p) ≤ j, note that p ∈ I_{k} else the jump J_{k+1} := P − I_{k} would contain some covering relation between ranks j, j+1 by following a chain upward from p. Thus i_{0} ≤ k, and hence e_{p} appears once each in v_{I_{i_{0}}}, v_{I_{i_{0}+1}}, …, v_{I_{k}} on the left side, and once each in v_{I′_{i_{0}}}, v_{I′_{i_{0}+1}}, …, v_{I′_{k−1}} plus once in v_{I_{j}^{rc}} on the right.

We now use (3.2). Since I_{j}^{rc} is rank-constant, f(v_{I_{j}^{rc}}) = 0. Since each I′_{j} is an ideal, one has f(I′_{j}) ≤ M. Thus equation (3.2) leads to the inequality k · M ≤ 0 + (k − 1) · M, which forces M ≤ 0. In other words, F is not a proper face; rather F = O_{eq}(P), and so {v_{I_{1}}, … v_{I_{k}}} will not span a face of Q. □

Corollary 3.15. Let P be a naturally labelled graded poset with r ranks. (i) The equatorial sphere Δ_{eq}(P) is shellable. (ii) The associated smooth toric variety X_{Δ_{eq}(P)} is projective. (iii) The P -Eulerian polynomial W (P, t) has symmetric unimodal

coefficient sequence (h_{0}, h_{1}, …, h_{#P −r}), and their differences

(h_{0}, h_{1} − h_{0}, h_{2} − h_{1}, …, h_{⌊ \frac{#P −r}{2} ⌋} − h_{⌊ \frac{#P −r}{2} ⌋−1})

form an M-vector, that is they satisfy the inequalities characterizing the Hilbert function of a standard graded commutative algebra.

Proof. For (i), see [3]. For (ii), see [16]. For (iii), see [37]. □

Remark 3.16. We should point out a recent related partial unimodality result of Björner and Farley [2]: the f-vector of the order complex of a distributive lattice is unimodal in its first half and last quarter. This is relevant since equations (1.1) and (2.1) show that for a naturally labelled poset P and its distributive lattice J(P) of order ideals, the real-rootedness of W (P, t) is equivalent to the real-rootedness of the f-polynomial of the order complex of J(P). Remark 3.17. In [24] Hibi shows that for any poset P, the face fan of the order polytope O(P) (after translating so that the origin is anywhere in its interior), is a polytopal fan. The part of the proof of Theorem 3.14 up through Case 1 gives an alternate proof of this result. In fact, it shows that the polytope involved may be obtained by pulling the vertices of O(P) in any order that refines the order by cardinality of the ideals indexing the vertices. Remark 3.18. Theorem 3.14 shows that Δ_{eq}(P) is a shellable sphere, but does not quite give an explicit shelling order on its facets, raising the following question. Question 3.19. Is there a natural order on the set L_{eq}(P) of maximal equatorial chains which induces a shelling order on Δ_{eq}(P)? If so, what is the statistic on L_{eq}(P), analogous to the descent statistic des(w) on L(P), whose generating function gives the h-polynomial W (P, t)?

One might hope that the bijection L(P) → L_{eq}(P) from Remark 3.9 could be used to transfer known orderings on L(P) (such as lexicographic order) that induce shellings of ΔJ(P) to orderings on L_{eq}(P) that shell Δ_{eq}(P). However, this seems to fail, even in small examples.

As mentioned earlier, Theorem 3.14 is important for the geometry of the toric variety X_{Δ_{eq}(P)}, but this geometry also has relevance for the Charney-Davis Conjecture. In [27, Theorem 1.1] it was shown that when Δ is a simplicial sphere arising from a simplicial, rational, polytopal fan, the quantity h(Δ, −1) coincides with the signature σ(X_{Δ}) of the associated toric variety. This opens the possibility for ideas from geometry to be applied. In particular, in [27] a property of the fan Δ was identified, called local convexity, which implies that Δ is flag, and furthermore via the Hirzebruch signature formula implies the Charney-Davis Conjecture for Δ. Definition 3.20. For a 1-dimensional ray pos(v) in a complete simplicial fan Δ, we denote by star_{v}(Δ) its star, that is the set of cones which together with this ray span a cone in the fan. Say that a complete simplicial fan Δ is locally convex if for every 1-dimensional ray pos(v) one has that star_{v}(Δ) forms a convex cone.

Figure 2. Zig-Zag Poset

Theorem 3.21. [27, Theorem 1.2(i), Proposition 5.3] The simplicial sphere Δ associated to any locally convex complete simplicial fan is flag. If furthermore the fan is rational and polytopal, then the Charney-Davis Conjecture holds for Δ.

It is therefore interesting to know whether the fan in R^{n}/V^{rc} associated with Δ_{eq}(P) is locally convex. Unfortunately, it does not even possess the weaker property of being flag in in general^{1}, as shown by the following example. Example 3.22. Let P be the “zig-zag” graded poset on [6] with r = 2 ranks P_{1} = {1, 2, 3}, P_{2} = {4, 5, 6} and covering relations given in Figure 2.

To show that Δ_{eq}(P) is not flag in this case, consider the chain of ideals

\begin{aligned}I_{1} & ⊂ & I_{2} & ⊂ & I_{3} \\ \{1\} & ⊂ & \{1, 2, 4\} & ⊂ & \{1, 2, 3, 4, 5\}. \end{aligned}

Note that each I_{j} is equatorial, as is each pair {I_{j}, I_{k}}, but the whole triple {I_{1}, I_{2}, I_{3}} is not.

To illustrate more explicitly how the relevant fan fails to be locally convex, consider the maximal equatorial chain of ideals

\begin{aligned}I_{1} & ⊂ & I_{2} & ⊂ & I_{3} & ⊂ & I_{4} \\ \{1\} & ⊂ & \{1, 4\} & ⊂ & \{1, 2, 4, 5\} & ⊂ & \{1, 2, 3, 4, 5\}. \end{aligned}

and the equatorial pair I_{1} = {1} ⊂ {1, 2, 4} =: I. We wish to show that in the simplicial fan corresponding to Δ_{eq}(P) in R^{6}/V^{rc}, which we identify for the moment with Δ_{eq}(P), the star of the ray pos(v_{I_{1}}) is not convex. Specifically, the 2-dimensional cone pos({v_{I_{1}}, v_{I}}) ⊆ star_{v_{I_{1}}}(Δ_{eq}(P)) has points in its interior that lie on the supporting hyperplane for the cone that is spanned (in the quotient space R^{6}/V^{rc}) by {v_{I_{2}}, v_{I_{3}}, v_{I_{4}}}:

1Contrary to a mistaken assertion with incorrect proof in an earlier version of this manuscript. The authors thank Xun Dong for catching this error.

χ_{I_{1}} + χ_{I} = χ_{{1}} + χ_{{1,2,4}}
= χ_{{1,2}} + χ_{{1,4}}
= χ_{{1,2,3}} − (χ_{{1,2,3,4,5}} − χ_{{1,2,4,5}}) + χ_{{1,4}}
= χ_{I_{1}^{rc}} − (χ_{I_{4}} − χ_{I_{3}}) + χ_{I_{2}}.

Here I_{1}^{rc} denotes the rank-constant ideal P_{1} = {1, 2, 3} as usual.

However, we do have the following result. For a poset P, the width is the size of the largest antichain (=totally unordered subset) in P. Theorem 3.23. The fan in R^{n}/V^{rc} associated with Δ_{eq}(P) is locally convex if width(P) ≤ 2. Consequently, Δ_{eq}(P) is flag in this case, and the Charney-Davis Conjecture holds for Δ_{eq}(P), that is

\begin{matrix}(−1)^{\frac{n−r}{2}} h(Δ_{eq}(P), −1) ≥ 0 \\ (= (−1)^{\frac{n−r}{2}} W (P, −1)) \end{matrix}

Although flag-ness follows from local convexity, when width(P) ≤ 2 it is easy enough to show flag-ness directly; we omit this direct proof.

Proof. Without loss of generality, we may assume not only that P has width 2, but also that every rank P_{j} has cardinality 2; when a rank of P has only one element, this element is comparable to all of P and its removal is easily seen not to affect Δ_{eq}(P) or its associated fan in R^{n}/V^{rc} up to linear isomorphism.

Local convexity here amounts to checking the following. Consider a maximal equatorial chain of ideals I_{1} ⊂ ⋯ ⊂ I_{n−r}. Let I be another ideal that forms an equatorial pair {I, I_{k}} with one of the ideals I_{k} in the chain. We must show that the unique linear functional f defined on R^{n} by the conditions

(3.3)  \begin{aligned}f(V^{rc}) & = 0 \\ f(χ_{I_{j}}) & = 0 for i ∈ [n − r] − \{k\} \\ f(χ_{I_{k}}) & = 1 \end{aligned}

has f(χ_{I}) ≥ 0. This suffices because the zero set of the functional f defines a typical supporting hyperplane for the star of the ray pos(v_{I_{k}}), and one needs to check that every other ray v_{I} in this star lies on the same side of this hyperplane as v_{I_{k}}.

From the defining equation of f (3.3) and its additivity we infer the following list of values of f on the characteristic vectors of the jumps J_{i} := I_{i} − I_{i−1}, which we will use without further reference:

\begin{aligned}f(χ_{J_{k+1}}) & = −1 \\ f(χ_{J_{k}}) & = +1 \\ f(χ_{J_{i}}) & = 0 for i ≠ k, k + 1 \end{aligned}

Another fact that will be used frequently without mention is that by (3.3) for every rank P_{j} = {p, p′} one has f(e_{p}) + f(e_{p′}) = f(χ_{P_{j}}) = 0.

By Proposition 3.5 the two sets of ranks occupied by the chains J_{k+1} and J_{k} can overlap in at most one rank. When they do overlap, say in the rank P_{j} = {p, p′} with p ∈ J_{k} and p′ ∈ J_{k+1}, one can check that f satisfies

\begin{aligned}f(e_{p}) & = +1 \\ f(e_{p′}) & = −1 \\ f(e_{q}) & = 0 for q ≠ p, p′. \end{aligned}.

As p′ ∉ I_{k}, this means that f(e_{q}) ≥ 0 for q ∈ I_{k}. Thus any ideal I that forms an equatorial chain of the form I ⊂ I_{k} will have f(χ_{I}) ≥ 0 as desired. If the equatorial chain looks like I_{k} ⊂ I, then p ∈ I_{k} ⊂ I will force f(χ_{I}) ≥ 0 again.

When the sets of ranks occupied by J_{k+1} and J_{k} do not overlap, we consider two cases.

Case 1. J_{k} occupies strictly higher ranks than J_{k+1}.

Then by Proposition 3.5 it is possible to index a subset of the jumps J_{i} as

J_{k+1} := J_{i_{1}}, J_{i_{2}}, …, J_{i_{s−1}}, J_{i_{s}} := J_{k}

in such a way that J_{i_{2}}, J_{i_{3}}, …, J_{i_{s−1}} are non-singleton jumps J_{i_{ℓ}}, with max(J_{i_{ℓ}}), min(J_{i_{ℓ+1}}) occupying the same rank for each ℓ ∈ [s − 1].

In fact, one can check that the definition of the jumps along with the fact that P is graded (so that every element in P is comparable to at least one out of the two elements in each rank P_{j}) forces s to be even. Moreover, one can verify the following total orderings of the chains J_{i_{ℓ}}:

\begin{matrix}J_{i_{2}} <_{P} J_{i_{4}} <_{P} ⋯ <_{P} J_{i_{s}} & ⊂ I_{k} \\ J_{i_{1}} <_{P} J_{i_{3}} <_{P} ⋯ <_{P} J_{i_{s−1}} & ⊄ I_{k}. \end{matrix}

(here J <_{P} J′ means that the two chains satisfy max J <_{P} min J′). This then implies that f(e_{p}) = 0 for most p ∈ P, with the exception of values +1, −1 alternating along the following two linearly ordered subsets:

(3.4)

max J_{i_{1}} < min J_{i_{3}} < max J_{i_{3}} < ⋯ < min J_{i_{s−1}} < max J_{i_{s−1}}
−1  +1  −1  +1  −1
min J_{i_{2}} < max J_{i_{2}} < ⋯ < min J_{i_{s−2}} < max J_{i_{s−2}} < min J_{i_{s}}
+1  −1  +1  −1  +1.

Let I be an ideal in P such that {I, I_{k}} is equatorial. I ⊂ I_{k}: We have f(χ_{I}) ≥ 0 because the only q ∈ I_{k} with e_{q} ≠ 0 that

can lie in I will form an initial segment of the second chain in (3.4).

I_{k} ⊂ I: It follows that f(χ_{I}) ≥ 0, because the q ∈ I − I_{k} such that f(e_{q}) ≠ 0 form an initial segment of the first chain in (3.4), so their sum is at least −1, while f(χ_{I_{k}}) = +1.

Case 2. J_{k} occupies strictly lower ranks than does J_{k+1}.

In this case, the definition of the jumps, along with the graded-ness of P forces the following situation. There exists a pair of adjacent ranks P_{j}, P_{j+1} and two elements p_{j}, p_{j+1} such that

(3.5)

P_{j+1} = {min J_{k+1}, p_{j+1}}
P_{j} = {max J_{k}, p_{j}}
p_{j} < p_{j+1} ( in fact, J_{k−1} = {p_{j}, p_{j+1}})
max J_{k+1} ≮ p_{j+1}.

One can check that this implies the following values for f:

(3.6)

f(max J_{k}) = f(p_{j+1}) = +1
f(min J_{k+1}) = f(p_{j}) = −1
f(p) = 0 for all other p ∈ P.

Again, let I be an ideal in P such that {I, I_{k}} is equatorial. I_{k} ⊂ I: From (3.5) and (3.6), there is only one possible q in I − I_{k} such

that f(e_{q}) < 0, namely q = min J_{k+1} has f(q) = −1. But then f(χ_{I_{k}}) = +1, so

f(χ_{I}) = f(χ_{I_{k}} + χ_{I−I_{k}}) ≥ −1 + 1 = 0.

I ⊂ I_{k}: From (3.5) and (3.6), the only way one could have f(χ_{I}) < 0 would be if p_{j} ∈ I but both max J_{k} and p_{j+1} are not in I. However this would contradict the equatoriality of the pair {I, I_{k}}: since max J_{k+1} ≮ p_{j+1}, there would be no covering pair from ranks j, j+1 contained in any of the jumps I, I_{k}−I, P −I_{k}.

□

The Neggers-Stanley Conjecture is trivial when width(P) = 1, but unknown even when width(P) = 2, although claims for its proof in this case have been made, and then retracted, more than once [49]. In light of Proposition 1.4, we regard Theorem 3.23 as non-trivial further evidence for both the Charney-Davis and the Neggers-Stanley Conjectures.

4. Which Koszul Algebras have PF Hilbert Functions?

In this and the next section, we give some results aimed toward the thesis that the right context in which to view both the Charney-Davis and Neggers-Stanley Conjectures (along with some other combinatorial conjectures and questions) may be the interaction between Koszul algebras and PF-sequences.

4.1. Koszul Algebras and PF-Sequences. We begin with a quick review both of Koszul algebras and of PF-sequences. The reader is referred to [15] for more information on Koszul algebras, and to [5, 26] for more on PF-sequences.

Let R = ⨁_{i≥0} R_{i} be a finitely generated, standard graded, connected, associative (but not necessarily commutative) algebra over a field k, that is a quotient R = k⟨x_{1}, …, x_{n}⟩/J for some two-sided ideal J which is homogeneous with respect to the grading deg(x_{i}) = 1. By eliminating redundant generators x_{i}, we may assume without loss of generality that J only contains elements of degree 2 and higher.

Definition 4.1. (see [15]) R is called Koszul if the field k, endowed with the trivial R-module structure as the quotient k = R/⟨x_{1}, …, x_{n}⟩, has a graded linear R-free resolution, that is an exact sequence of the form

⋯ → ∑_{j} R(−i)^{β_{i}} → ⋯ → ∑_{j} R(−1)^{β_{1}} → R → k → 0.

Equivalently, R is Koszul if the graded k-vector space Tor_{i}^{R}(k, k) is concentrated in degree i for each i, or equivalently, if the Poincaré series P (R, t) and Hilbert series H(R, t) defined by

P (R, t) : = ∑_{i≥0} dim_{k} Tor_{i}^{R}(k, k)t^{i}
H(R, t) : = ∑_{i≥0} dim_{k} R_{i}t^{i},

where R_{i} is the k-vector subspace of R generated by the monomials of degree i, are related by the equation

(4.1)  P (R, t)H(R, −t) = 1.

It is not hard to see that Koszul-ness of R implies that the ideal of relations J defining R is generated quadratically, but the reverse implication holds only in special cases; see e.g. Theorem 4.5 below.

Note that H(R, t), P (R, t) are only power series in t, and not rational functions of t in general. However, we will be particularly interested in the case where R is a commutative ring, so that one can (uniquely) express

H(R, t) := ∑_{i≥0} dim_{k} R_{i} t^{i} = \frac{h(R, t)}{(1 − t)^{d}}

where h(R, t) = h_{0}+h_{1}t+⋯+h_{α(R)}t^{α(R)} ∈ Z[t] with h_{α(R)} ≠ 0 (see [12, Exercise 12.12, p. 284]). Here d is the Krull dimension of R, the vector (h_{0}, h_{1}, …, h_{α(R)}) is called the h-vector of R, and we will call h(R, t) the h-polynomial of R. Although the quantity α(R) does not seem to have a particular name in the literature that we could find, the degree of H(R, t) as a rational function is usually called the a-invariant a(R). So we can express α(R) as the sum α(R) = a(R) + d of the a-invariant and Krull dimension.

The theory of Hilbert series relates h-polynomials of simplicial complexes and W -polynomials through the polynomial h(R, t). When R is commutative and Cohen-Macaulay we say that R is CM. The following facts are well known (see for example [7]):

▷ If R is CM then h(R, t) ∈ N[t].

▷ If R is commutative and Gorenstein then R is CM and h(R, t) = h_{0} + h_{1}t + ⋯ + h_{α(R)}t^{α(R)} satisfies h_{α(R)−i} = h_{i} for i ∈ [0, α(R)].

We are interested in the case when h(R, t) has only real non-positive zeroes. This question can be approached via the theory of total positivity (see [5] for a pleasant introduction, and [26] for an extensive treatment). We review some of the basic facts and definitions here.

Say that a sequence of real numbers (a_{0}, a_{1}, …) is a Polya frequency sequence of order r (or P F_{r} for short) if all minor subdeterminants of size at most r in the infinite Toeplitz matrix (a_{j−i})_{i,j=0,1,2,...} are nonnegative. For example, PF_{1} means the a_{i} are non-negative, while PF_{2} is equivalent to log-concavity, i.e. a_{i}^{2} ≥ a_{i−1}a_{i+1} for each i. A Polya frequency sequence (or PF sequence) is one which is PF_{r} for all r. We say that a formal power series A(t) := ∑_{i≥0} a_{i}t^{i} generates a PFsequence if the sequence (a_{0}, a_{1}, …) is PF.

We also recall a basic relationship between zeroes/poles of rational functions and PF-sequences, in a form stated by Brenti that is convenient for our applications. It can be deduced from a fundamental and deep result [5, Theorem 4.5.2],[26, Chapter 8, Theorem 5.1] characterizing PF-sequences. Theorem 4.2 (Theorem 4.5.3 [5]). Let ∑_{i≥0} a_{i}t^{i} be a rational power series in R[[t]] with non-negative coefficients a_{i}. Then (a_{0}, a_{1}, …) is a PF-sequence if and only if when we express

∑_{i≥0} a_{i}t^{i} = \frac{W (t)}{V (t)}

with W, V relatively prime polynomials in R[t], the numerator W (t) has only real non-positive zeroes and the denominator V (t) has only real positive zeroes. Corollary 4.3. When R is Koszul, the following are equivalent:

(i) The sequence (Hilb(R, 0), Hilb(R, 1), …) generated by H(R, t) is PF.

(ii) The sequence (β_{0}, β_{1}, …) generated by P (R, t) is PF. When R is furthermore commutative and CM, then (i) and (ii) are equivalent to:

(iii) h(R, t) has only negative real zeroes.

(iv) The sequence (h_{0}, h_{1}, …, h_{α(R)}) generated by h(R, t) is PF.

Proof. The equivalence of the PF-property for power series H(t), P (t) satisfying P (t)H(−t) = 1 is well-known [26, Theorem 8.1.2], so the equivalence of (i), (ii) follows from (4.1).

CM-ness of R implies that the h_{i} are non-negative, so Theorem 4.2 shows the equivalence of (iii) and (iv).

Since h_{0} = 1 > 0 and the h_{i} are non-negative, the polynomial h(R, t) does not vanish at t = 1, and consequently the numerator and denominator in H(R, t) = \frac{h(R,t)}{(1−t)^{d}} are relatively prime. Hence Theorem 4.2 also shows the equivalence of (i) and (iii). □

4.2. Questions and Examples. The questions motivating this section are as follows. Say that a Koszul algebra R is PF if H(R, t)

(or equivalently P (R, t)) generates a PF-sequence. Say that a Koszul Gorenstein commutative algebra R is CD (for \underline{C}harney-\underline{D}avis) if either

• α(R) is odd, or

• if α(R) is even and (−1)^{\frac{α(R)}{2}} h(R, −1) ≥ 0.

Question 4.4.

▷ Which Koszul algebras are PF?

▷ In particular, which Koszul CM-algebras are PF, that is, which ones have only real zeroes for their h-polynomial h(R, t)?

▷ Which Koszul Gorenstein algebras are CD? Note that Proposition 1.4 shows that for a Gorenstein algebra, PFimplies CD.

Part of the relevance of Koszul-ness for various combinatorial conjectures derives from a result of Fröberg [14]. Recall that for a simplicial complex Δ on vertex set V the Stanley-Reisner ring k[Δ] is the quotient of k[x_{v} : v ∈ V] by the ideal I_{Δ} generated by the squarefree monomials whose support is a minimal non-face of Δ. Theorem 4.5. [14] For monomial ideals I in S = k[x_{1}, …, x_{n}], the algebra R = S/I is Koszul if and only if I is quadratically generated.

Consequently, for a simplicial complex Δ, the Stanley-Reisner ring k[Δ] is Koszul if and only if Δ is flag.

Instances of Question 4.4 have occurred several times in the literature. Here are some notable examples, beginning with the two that originally motivated us. Example 4.6. The Charney-Davis Conjecture for a flag simplicial homology sphere Δ asserts CD-ness for the Koszul Gorenstein Stanley-Reisner ring k[Δ]. Example 4.7. The Neggers-Stanley Conjecture for a naturally labelled poset P asserts PF-ness for the Koszul CM Stanley-Reisner ring k[ΔJ(P)]. Here we recall from Section 2 that ΔJ(P) is the order complex of the distributive lattice of order ideals in P. Example 4.8. A conjecture generally attributed to Gasharov and Stanley asserts that the f-polynomial of the complex Δ_{G} of independent (or stable) sets in a claw-free (see Example 4.12) graph G has only real zeroes. The independent set complex Δ_{G} is always flag: it is defined as having a simplex for every subset of vertices that contains no edges. Thus the Stanley-Reisner ring k[Δ_{G}] is Koszul by Theorem 4.5, and the Gasharov-Stanley Conjecture asserts that it is PF. In general k[Δ_{G}] is far from being CM. However its further quotient k[Δ_{G}]/(x_{v}^{2} : v ∈ V) is of Krull dimension 0, hence Cohen-Macaulay, and also Koszul by Theorem 4.5, having h-polynomial the same as the f-polynomial of Δ_{G}.

Thus one can also view the Gasharov-Stanley Conjecture as asserting that this Koszul CM-ring is PF.

There is an interesting special case where this conjecture is known. For a poset P let G_{P} be the graph whose edges correspond to incomparable pairs of elements in P. Then Δ_{G_{P}} is the order complex Δ(P) and G_{P} is claw-free if and only if P is (3⊔1)-free (i.e. P does not contain 4 elements whose induced subposet is a disjoint union of a chain of 3 elements and a single element). In this case it is known by work of Stanley [41, Cor. 2.9], based on earlier work of Gasharov, that f(Δ_{G_{P}} , t) has only real zeroes; see [35, Cor. 4.1] for an alternative proof. Example 4.9. Given a graph G on vertex set [n], define its matching complex M_{G} to be the simplicial complex having vertex set corresponding to the edges of G, and a simplex for each subset of edges that form a partial matching. This is clearly a flag complex, so that k[M_{G}] is Koszul. A classical theorem in enumerative graph theory by Heilmann and Lieb [19] can be rephrased as asserting that the f-polynomial of M_{G} has only real zeroes. Analogous to Example 4.8 one constructs from the Stanley-Reisner ring k[M_{G}] a Koszul CM-ring whose h-polynomial is the f-polynomial of M_{G}. Example 4.10. In [5, Chapter 7], Brenti initiated the study of the following question, generalizing the Neggers-Stanley problem. Given a directed graph D (or digraph), let a_{i} denoted the number of directed walks of length k in D. For which digraphs is (a_{0}, a_{1}, …) a PF-sequence?

The sequence (a_{0}, a_{1}, …) turns out to be the Hilbert function for a (non-commutative) Koszul algebra studied by Bruns, Herzog and Vetter, and also by Kobayashi (see [8]), who give algebraic interpretations for some of the combinatorial results. Example 4.11. Phung Ho Hai has shown that certain quantum deformations of polynomial and exterior algebras are Koszul [20] and PF [21], by representation-theoretic means.

This list of examples might make it tempting to conjecture that any Koszul CM-algebra is PF. But this is indeed far from being true. Example 4.12. The claw graph G is a tree with one vertex of degree 3 connected to 3 leaves. Its independent set complex Δ_{G} is the disjoint union of a 2-simplex and a 0-simplex, having f-vector

(f_{1}, f_{0}, f_{1}, f_{2}) = (1, 4, 3, 1).

This implies that R = k[Δ_{G}]/(x_{1}^{2}, x_{2}^{2}, x_{3}^{2}, x_{4}^{2}) is a Koszul CM-algebra with h(R, t) = 1 + 4t + 3t^{2} + t^{3}. But h(R, t) can be easily seen to have two non-real zeroes, so R is not PF.

4.3. Motivating Results. In this subsection we will give results that show, in spite of Example 4.12, there is evidence for the assertion that Koszul rings and their Hilbert functions are a good framework in which to think about PF-questions.

One indication that the Koszul and PF-properties interact well is the following proposition, apparently well-known to those who study Tor_{·}^{R}(k, k). The authors thank Vesselin Gasharov and Irena Peeva for bringing it to their attention.

Proposition 4.13. Let R be a Koszul algebra with rational Hilbert series H(R, t) (e.g. if R is commutative, or finite-dimensional over k).

Then if H(R, t) has any zeroes at all, it will have at least one real zero, namely −ρ where ρ is the radius of convergence P (R, t).

Proof. Recall that \frac{1}{H(R,−t)} = P (R, t) = ∑_{i≥0} β_{i}t^{i} has non-negative coefficients β_{i}(= dim_{k} Tor_{i}^{R}(k, k)). Then Pringsheim’s Theorem [46, §7.2] implies that whenever H(R, t) has any zeroes, P (R, t) will have a pole (and H(R, −t) a zero) at t = ρ, where ρ is the radius of convergence (= the minimum complex modulus of the poles) of P (R, t). □

This has consequences for CM-algebras R whose h-polynomial is of low degree α(R).

Corollary 4.14.

(i) Every Koszul CM-algebra R with α(R) ≤ 2 is PF.

(ii) Every Koszul Gorenstein algebra R with α(R) ≤ 3 is PF.

(iii) A Koszul Gorenstein algebra R with α(R) ≤ 4 is PF if and only if it is CD.

In particular, (iii) combines with Davis and Okun’s recent proof [11] of the Charney-Davis Conjecture for flag simplicial homology spheres of dimension at most 3, to show that such simplicial spheres are always PF.

Proof. Assertion (i) is immediate from Proposition 4.13: α(R) ≤ 2 implies h(R, t) is a quadratic polynomial, and it has real coefficients, so since it has at least one real zero, both its zeroes are real.

For assertions (ii),(iii) certain possibilities for h(R, t) when R is Koszul and Gorenstein must be ruled out in an ad hoc way, which we do all at once here:

(4.2)  \begin{aligned}h(R, t) & = 1 + t + t^{2} + t^{3} \\ h(R, t) & = 1 + 2t + 2t^{2} + t^{3} \\ h(R, t) & = 1 + 2t + 2t^{2} + 2t^{3} + t^{4} \\ h(R, t) & = 1 + 3t + 4t^{2} + 3t^{3} + t^{4} \\ h(R, t) & = 1 + h_{1}t + 0t^{2} + h_{1}t^{3} + t^{4} \\ h(R, t) & = 1 + h_{1}t + 1t^{2} + h_{1}t^{3} + t^{4} \end{aligned}

Firstly, by means of Theorem 4.15 (iv) below, one can mod out by a regular sequence of degree one and assume that R has Krull dimension 0, and hence is generated by h_{1} elements in degree 1. Then Koszulness implies that the ideal J is generated by J_{2}. The 5th possibility above is absurd for a standard graded algebra. The 1st would require J_{2} = 0 and hence J = 0, which is absurd since R_{5} = 0. In the 6th possibility above, one of Macaulay’s conditions for being an Mvector [43, Corollary II.2.4] asserts that h_{3} ≤ h_{2}^{⟨2⟩}, which would force h_{1}(= h_{3}) = 1. This leads to a contradiction as in the 1st possibility. For the 2nd, 3rd, and 4th possibilities, one contradicts the fact that

dim_{k} J_{3} ≤ dim_{k} J_{2} · dim_{k} R_{1}
and hence \binom{h_{1} + 2}{3} − h_{3} ≤ (\binom{h_{1} + 1}{2} − h_{2}) · h_{1}.

Now to prove assertion (ii), we must consider the case α(R) = 3, so

h(R, t) = 1 + h_{1}t + h_{1}t^{2} + t^{3} = (1 + t)(1 + (h_{1} − 1)t + t^{2}).

For real zeroes we need only show that h_{1} − 1 ≥ 2. Since h_{1} is a non-negative integer, this means ruling out the first two possibilities in (4.2), so we are done.

To prove assertion (iii), we must consider the case α(R) = 4, so

h(R, t) = 1 + h_{1}t + h_{2}t^{2} + h_{1}t^{3} + t^{4}.

We consider two cases, depending on whether the radius of convergence of H(R, t) is ρ = 1 or not. Case 1. ρ = 1. In this case, we will show R is always PF. Here h(R, t) has t = −1 as a zero, so 1 + t as a factor, and since it is a symmetric quartic polynomial, it must have it as a double factor:

\begin{aligned}h(R, t) & = 1 + h_{1}t + h_{2}t^{2} + h_{1}t^{3} + t^{4} \\ & = (1 + t)^{2}(1 + (h_{1} − 2)t + t^{2}). \end{aligned}

For real zeroes we need only to show h_{1} − 2 ≥ 2, that is to rule out the 2nd, 3rd and 4th possibilities in (4.2). This was already done.

Case 2. ρ ≠ 1. In this case, since h(R, t) is symmetric, both −ρ and \frac{−1}{ρ} are zeroes. If we set a := ρ + \frac{1}{ρ}, and define b by a + b = h_{1}, then this means

h(R, t) = 1 + h_{1}t + h_{2}t^{2} + h_{1}t^{3} + t^{4}

= (1 + ρt) (1 + \frac{1}{ρ}t) q(t)

= (1 + at + t^{2})(1 + bt + t^{2})

where we further note that ab = h_{2} − 1. Now ρ ∈ (0, 1) since exactly one of the two positive values ρ, \frac{1}{ρ} lies in this range, and ρ is the smaller of the two. This implies a := ρ + \frac{1}{ρ} > 2, and hence one concludes that the Charney-Davis quantity

h(R, −1) = (1 − a + 1)(1 − b + 1) = (a − 2)(b − 2)

has the same sign as b − 2. Thus R is CD if and only if b ≥ 2. Clearly, h(R, t) has only real roots if and only if |b| ≥ 2. Thus if we can show that b ≥ 0, then R is CD if and only if h(R, t) has only real zeroes, as desired.

To see b ≥ 0, using the equation ab = h_{2} − 2 and the fact that a > 0, we need only show that h_{2} ≥ 2. In other words, we need to rule out the last two possibilities in (4.2), which was already done. □

Next we discuss how Question 4.4 respects various natural constructions. Given two commutative standard graded k-algebras R, R′ one can form their tensor product R ⊗_{k} R′ having

(R ⊗_{k} R′)_{l} := ∑_{i+j=l} R_{i} ⊗_{k} R′_{j},

their Segre product R ∗ R′ having

(R ∗ R′)_{l} := R_{l} ⊗_{k} R′_{l},

and the d-th Veronese subalgebra R^{(d)} having

R_{l}^{(d)} := R_{dl}

for any positive integer d.

These ring operations have corresponding effects on the Hilbert function. Tensor product corresponds to the convolution c_{l} := ∑_{i+j=l} a_{i}b_{j} of two sequences (a_{i}), (b_{j}). The Segre product corresponds to the Hadamard product c_{i} = a_{i}b_{i}. The d-th Veronese subalgebra corresponds to the d-th arithmetic subsequence c_{l} = a_{dl}. Theorem 4.15. Let R, R′ be commutative standard k-algebras, and (a_{i})_{i=0}^{∞}, (b_{i})_{i=0}^{∞} two sequences of complex numbers.

(i) (Tensor products)

(a) If (a_{i}), (b_{i}) are PF, then so is their convolution.

(b) If R, R′ are Koszul, then so is R ⊗_{k} R′.

(c) If R, R′ are CM, then so is R ⊗_{k} R′. (ii) (Segre products)

(a) If (a_{i}), (b_{i}) are PF, and if furthermore either both are finite sequences, or both are polynomial functions a(i), b(i) of the index i, then so is their Hadamard product.

(b) If R, R′ are Koszul, then so is R ∗ R′.

(c) If R, R′ are CM, and if furthermore either both have Krull dimension zero, or both have Hilbert functions equal to their Hilbert polynomials, then R ∗ R′ is CM also.

(iii) (Veronese subrings) (a) If (a_{i}) is PF, then so is (a_{di}) for any positive integer d.

(b) If R is Koszul, then so is R^{(d)} for any positive integer d.

(c) If R is CM, then so is R^{(d)}. (iv) (Quotients by a linear non-zero-divisor)

(a) If

∑_{i=0}^{∞} a_{i}t^{i} = \frac{h(t)}{(1 − t)^{d}}

for some polynomial h(t) having h(1) ≠ 0 and d > 0, then (a_{i}) is PF if and only if the sequence generated by \frac{h(t)}{(1−t)^{d−1}} is PF.

(b) When f ∈ R is a linear non-zero divisor, R is Koszul if and only if R/(f) is Koszul.

(c) When f ∈ R is a linear non-zero divisor, R is CM if and only if R/(f) is CM.

Proof. The assertions about preservation of the Koszul property follow from a result of Backelin and Fröberg [15, Theorem 5.2] (i)(a) Is easy (see e.g. [26, Theorem 1.2]). (ii)(a) This is a result of Maló (see [5, Section 4.7]) when the sequences

are finite, and a result of Wagner [48] when the sequences are polynomial.

(iii)(a) Is easy (see e.g. [5, Proposition 2.2.3]). (iv)(a) Follows from Theorem 4.2. (i)(c) Follows from standard facts about systems of parameters and

regular sequences in CM-rings [7]. (ii)(c) This is trivial when both R, R′ have Krull dimension 0, since

such rings are always CM. When R, R′ have Hilbert functions which are polynomial, it follows from a result of Stückrad and Vogel [45, Theorem, part (i), p. 378].

(iii)(c) The arguments for this fact are given, for example, in [18, Be-

ginning of §3]. (iv)(c) Same as (i)(c).

□

5. Families of Examples

In this section, we examine some interesting families of flag simplicial spheres and other CM flag complexes Δ. Adopting the conventions of the previous sections we say that a flag simplicial sphere Δ is CD if Δ satisfies the Charney-Davis conjecture, say that a simplicial complex Δ is PF is h(Δ, t) has only real zeroes. All of these examples have been either been checked or conjectured to be CD or PF.

5.1. Simplicial Hyperplane Arrangements. Simplicial hyperplane arrangements turn out to give rise to complete simplicial fans which are locally convex [27, Proposition 4.8], and hence to flag simplicial spheres [27, Proposition 5.3]. Because of their local convexity, it was noted in [27] that whenever the arrangements are rational, they are at least CD. We do not know whether they are PF, nor whether they are CD without the assumption of rationality.

Coxeter arrangements are the simplicial hyperplane arrangements given by the reflecting hyperplanes of a finite Coxeter system (W, S), and are closely related to the Neggers-Stanley Conjecture. The associated simplicial complex Δ(W, S), called the Coxeter complex (see [43, §III.4]) has h-polynomial

h(Δ(W, S), t) = ∑_{w∈W} t^{des(w)}

where des(w) := #{s ∈ S : ℓ(ws) < ℓ(w)}. Because this h-polynomial is multiplicative for reducible Coxeter systems (W_{1} × W_{2}, S_{1} ⊔ S_{2}), it suffices to check the CD or PF-property for irreducible finite Coxeter systems, which have a well-known classification.

For types A_{n−1} and B_{n}, the h-polynomial coincides with the special cases of k = 1 and k = 2 of a family of polynomials E_{n}^{k}(t) studied by Steingrimsson [44] which generalize the classical Eulerian polynomials. These satisfy

(5.1)  \begin{aligned}\frac{E_{n}^{k}(t)}{(1 − t)^{d+1}} & = ∑_{m≥0}(km + 1)^{n}t^{m} \\ ∑_{n≥0} E_{n}^{k}(t)\frac{u^{n}}{n!} & = \frac{(1 − t)e^{u(1−t)}}{1 − te^{ku(1−t)}} \end{aligned}

From the first equation in (5.1) and results of Brenti [5], it follows that E_{n}^{k}(t) has only real zeroes, taking care of the PF-property for type A and B Coxeter complexes. It is known that the Charney-Davis quantity

h(Δ_{A_{n−1}}, −1) = ∑_{w∈𝔖_{n}}(−1)^{des(w)} = \begin{cases}0 & for n even \\ (−1)^{\frac{n−1}{2}} E_{n} & for n odd \end{cases}

where E_{n} is the number of alternating permutations

w = w_{1} < w_{2} > w_{3} < ⋯

in 𝔖_{n} (this can be deduced, e.g., from (5.1) by setting k = 1, t = −1 and comparing with [40, pp. 148-9]). The formulas (5.1) show similarly that

h(Δ_{B_{n}}, −1) = \begin{cases}0 & for n odd \\ (−1)^{\frac{n}{2}} 2^{n}E_{n} & for n even. \end{cases}

For type D, the h-polynomial of the Coxeter complex was first investigated by Stembridge, who showed (see [32, p. 136]) that it satisfies

(5.2)  h(Δ(D_{n}), t) = h(Δ(B_{n}), t) − 2^{n−1}n t · h(Δ(A_{n−2}), t).

Brenti further explored these polynomials, and conjectured [6, Conjecture 5.1] that they are PF. Although this is not known, it can at least be shown using (5.2) that they are CD, as follows. From the above generating functions, and the answers for types A_{n−1}, B_{n}, one checks that for n even,

(−1)^{\frac{n}{2}} h(Δ(D_{n}), −1) = 2^{n−1}(2E_{n} − nE_{n−1}).

To show the right-hand side is non-negative, we exhibit for n even an injection

{(i, w) : i ∈ [n], w an alternating permutation in 𝔖_{n−1}}

↪^{ϕ} {ŵ ∈ 𝔖_{n} : ŵ is alternating or reverse alternating}

defined as follows: given (i, w) as above, define

\begin{matrix}ϕ(w) = \\ \{ & \begin{matrix}w_{i−1} > w_{i−2} < … > w_{1} < n > w_{i} < w_{i+1} > ⋯ > w_{n−1}, & i odd, \\ w_{1} < w_{2} > … > w_{i−1} < n > w_{n−1} < w_{n−2} > ⋯ < w_{i}, & i even. \end{matrix} \end{matrix}

For the remaining (non-dihedral) exceptional finite irreducible Coxeter groups (E_{6}, E_{7}, E_{8}, F_{4}, H_{3}, H_{4}), one can compute the h-polynomials of the Coxeter complex explicitly via computer, and check ad hoc that they have only real zeroes (in fact, most of them were already checked in [6]).

5.2. Generalized Associahedra. The generalized associahedra defined recently by Fomin and Zelevinsky [13] are a family of flag simplicial spheres associated to any finite Weyl group W; we will denote their associated simplicial complex Δ_{F Z}(W). These complexes generalize the associahedra and cyclohedra and possess beautiful numerology. Their number of facets is a known Coxeter group generalization of the Catalan numbers

Catalan(W) = ∏_{i} \frac{e_{i} + h + 1}{e_{i} + 1},

where h is the Coxeter number of W and e_{i} are the exponents. From recursions for their face numbers given in [13, §3.3], one can compute their h-polynomials explicitly:

h(Δ_{F Z}(A_{n−1}), t) = ∑_{k=0}^{n−1} \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}t^{k}

h(Δ_{F Z}(B_{n}), t) = ∑_{k=0}^{n} \binom{n}{k}^{2}t^{k}
h(Δ_{F Z}(D_{n}), t) = 1 + t^{n}

+ (∑_{k=1}^{n−1} (\binom{n}{k}^{2} − \frac{n}{n − 1}\binom{n − 1}{k − 1}\binom{n − 1}{k}) t^{k})

h(Δ_{F Z}(E_{8}), t) = 1 + 120t + 1540t^{2} + 6120t^{3} + 9518t^{4}
+ 6120t^{5} + 1540t^{6} + 120t^{7} + t^{8},
h(Δ_{F Z}(E_{7}), t) = 1 + 63t + 546t^{2} + 1470t^{3} + 1470t^{4}
+ 546t^{5} + 63t^{6} + t^{7},
h(Δ_{F Z}(E_{6}), t) = 1 + 36t + 204t^{2} + 351t^{3} + 204t^{4} + 36t^{5} + t^{6},
h(Δ_{F Z}(F_{4}), t) = 1 + 24t + 55t^{2} + 24t^{3} + t^{4}.

For type A_{n−1}, the h-polynomial is the generating function for the Narayana numbers [42, Exercise 6.34], and one can check (see [31, Proposition 17]) that it coincides with W (2 × n, t), where 2 × n is a naturally labelled Cartesian product of chains of sizes 2 and n. This is PF by Brenti’s result that the Neggers-Stanley Conjecture holds for all naturally labelled Gaussian posets [5, Theorem 5.6.8].

For type B_{n}, the h-polynomial coincides with W (n⊔n, t) where n⊔n is a naturally labelled disjoint union of two chains of size n. This is PF by Simion’s result that the Neggers-Stanley Conjecture holds for naturally labelled disjoint unions of chains [34].

For type D_{n}, we do not know whether the h-polynomial given above is PF. However, one can check that it is CD. By calculating explicitly one shows that

h(Δ_{F Z}(D_{n}), −1) = \begin{cases}0 & for n odd \\ (−1)^{\frac{n}{2}} \binom{n−2}{\frac{n−2}{2}} (2 − \frac{4}{n}) & for n even \end{cases}

which for n ≥ 2 has the appropriate sign.

One can check ad hoc for each of the exceptional cases above the h-polynomial h(Δ_{F Z}(W), t) has only real zeroes, and hence is PF.

5.3. Barycentric Subdivisions. Barycentric subdivisions of the boundaries of convex polytopes give flag simplicial spheres which are known to be CD. The Charney-Davis quantity in this case was observed by Babson (see [43, p. 103], [9, §7.3]) to be a certain coefficient in a finer enumerative invariant of the polytope known as its cd-index. Then a result of Stanley [39] shows that these cd-index coefficients are all nonnegative for a more general class of flag simplicial spheres (barycentric subdivisions of S-shellable regular cellular spheres). We do not know whether these barycentric subdivisions are PF.

5.4. Broken Circuit Complexes. Given a matroid M with a linear order ω on its ground set, there is an important shellable (hence CM) simplicial complex known as the broken-circuit complex BC(M, ω). It was shown by Björner and Ziegler [4, Theorem 2.8] that BC(M, ω) is a flag complex if and only if M is supersolvable, and in this case the h-polynomial factors

h(BC(M, ω), t) = ∏_{i}(1 + (e_{i} − 1)t)

where e_{i} are the exponents of the supersolvable matroid M. Thus whenever BC(M, ω) is flag, it is also trivially PF.

5.5. Regular Complex Polytopes. Regular complex polytopes were first defined by Shephard (see [10]), as arrangements of complex affine subspaces in C^{n} satisfying axioms modelled after the affine subspaces spanned by faces in a regular convex (real) polytope. To each regular complex polytope P is associated a flag simplicial complex Δ(P) called its Milnor fiber complex (or the order complex of its lattice of faces). These complexes are known to be CM [30], but not known to be shellable.

The classification of regular complex polytopes which are not regular real convex polytopes is fairly short, with three infinite families (simplices, generalized cross-polytopes, generalized cubes) all of whose h(Δ(P), t) are subsumed by the polynomials E_{n}^{k}(t) from (5.1), and hence are PF. There remains a finite list of exceptions, many of which live in C^{2}, so that Δ(P) is 1-dimensional, and hence are PF by Proposition 4.14(i). There are only four others on this list. In the following we list their h-polynomials (where we are using Coxeter’s notation for the polytopes themselves):

h(Δ(2{4}3{3}3), t) = h(Δ(3{3}3{4}2), t)
= 1 + 339t + 831t^{2} + 125t^{3},
h(Δ(3{3}3{3}3), t) = 1 + 123t + 399t^{2} + 125t^{3},
h(Δ(3{3}3{3}3{3}3), t) = 1 + 4796t + 56886t^{2} + 79196t^{3} + 14641t^{4}.

All of these have real zeroes by ad hoc computation.

Acknowledgments

The authors thank Luchezar Avramov, Francesco Brenti, Xun Dong, Vesselin Gasharov, Jürgen Herzog, Takayuki Hibi, Hidefumi Ohsugi, Irena Peeva, Mark Skandera, Richard Stanley, Dennis Stanton, David Wagner, and Dennis White for helpful conversations.

References

[1] J. Backelin and R. Fröberg, Poincaré series of short Artinian rings, J. Algebra, 96 (1985), 495–498.

[2] A. Björner, J. Farley, Descent enumerators of linear extensions are 75 % unimodal, in preparation.

[3] A. Björner and M. Wachs, Shellable nonpure complexes and posets, I, Trans. Amer. Math. Soc. 348 (1996), 1299–1327.

[4] A. Björner and G.M Ziegler, Broken circuit complexes: factorizations and generalizations, J. Combin. Theory Ser. B 51 (1991), 96–126.

[5] F. Brenti, Unimodal, Log-Concave and Polya Frequency Sequences in Combinatorics, Memoirs Amer. Math. Soc. 413, Amer. Math. Soc., Providence, 1989.

[6] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, European J. Combin. 15 (1994), 417–441.

[7] W. Bruns and J. Herzog, Cohen-Macaulay rings (revised edition), Cambridge University Press, Cambridge, 1998.

[8] W. Bruns, J. Herzog, U. Vetter, Syzygies and walks, in: Commutative Algebra (Trieste, 1992), 36–57, World Scientific Publishing, River Edge, NJ, 1994.

[9] R. Charney and M. Davis, Euler characteristic of a nonpositively curved, piecewise Euclidean manifold. Pac. J. Math., 171 (1995), 117–137.

[10] H.S.M. Coxeter, Regular Complex Polytopes, (2nd edition), Cambridge University Press, Cambridge, 1991.

[11] M. Davis and B. Okun, Vanishing theorems and conjectures for the ℓ^{2}- homology of right-angled Coxeter groups, Geom. Topol. 5 (2001), 7–74 (electronic).

[12] D. Eisenbud, Commutative Algebra with a View toward Algebraic Geometry, Graduate Texts in Math. 150, Springer, New York, 1995.

[13] S.V. Fomin and A.V. Zelevinsky, Y-systems and generalized associahedra, ArXiV preprint hep-th/0111053, 2001, 35 pages.

[14] R. Fröberg, Determination of a class of Poincaré series, Math Scand. 37 (1975), 29–39.

[15] R. Fröberg, Koszul algebras, In: Advances in Commutative Ring Theory. Proceedings of the 3rd International Conference, Fez, Lect. Notes Pure Appl. Math. 205, 337–350, Marcel Dekker, New York, 1999.

[16] W. Fulton, Introduction to Toric Varieties. Annals of Math. Stud. 131, Princeton University Press, Princeton, NJ, 1993.

[17] V. Gasharov, On the Neggers-Stanley conjecture and Eulerian polynomials, Comb. Theory, Ser. A 82 (1998) 134-146.

[18] S. Goto, K. Watanabe, On graded rings, I, J. Math. Soc. Japan 30 (1978), 179-213.

[19] O. J. Heilmann, E. H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232.

[20] P. H. Hai, Koszul property and Poincaré series of matrix bialgebras of type A_{n}, J. Algebra 192 (1997), 734–748.

[21] P. H. Hai, Poincaré aeries of quantum spaces associated to Hecke operators, Acta Math. Vietnamica 24 (1999), 235–246 (and as ArXiv preprint

q-alg/9711020).

[22] L.H., Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist. 38 1967 410–414.

[23] T. Hibi, Algebraic Combinatorics on Convex Polytopes, Carslaw Publications, Glebe NSW, Australia, 1992.

[24] T. Hibi, Toric varieties arising from canonical triangulations of poset polytopes are projective. In: Words, Languages and Combinatorics, II (Kyoto, 1992), 192–199, World Sci. Publishing, River Edge, NJ, 1994.

[25] T. Hibi, Distributive lattices, affine semigroups rings and algebras with straightening laws. In: Commutative Algebra and Combinatorics, US-Jap. joint Seminar, Kyoto/Jap. 1985, Adv. Stud. Pure Math. 11, 93–109, North-Holland, Amsterdam, 1987.

[26] S. Karlin, Total Positivity. Volume I, Stanford University Press. Stanford, 1968.

[27] N.C. Leung and V. Reiner, The signature of a toric variety, Duke Math. J. 111 (2002), 253–286.

[28] P. McMullen and G.C. Shephard, Convex Polytopes and the Upper Bound Conjecture, London Math. Soc. Lecture Note Series 3, Cambridge University Press, 1971.

[29] J. Neggers, Representations of finite partially ordered sets. J. Comb. Inf. Syst. Sci. 3 (1978), 113–133.

[30] P. Orlik, Milnor fiber complexes for Shephard groups, Adv. Math. 83 (1990), 135–154.

[31] V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195–222.

[32] V. Reiner, Descents and one-dimensional characters for classical Weyl groups, Discrete Math. 140 (1995), 129–140.

[33] V. Reiner, D. Stanton and V. Welker, The Charney-Davis quantity for certain graded posets, preprint 2002.

[34] R. Simion, A multiindexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences. J. Comb. Theory, Ser. A 36 (1984), 15–22.

[35] M. Skandera, A characterization of (3+1)-free posets, J. Combin. Theory, Ser. A. 93 (2001), 231-241.

[36] R.P. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc. 119, Amer. Math. Soc., Providence, 1972.

[37] R.P. Stanley, The number of faces of simplicial polytopes and spheres, Ann. New York Acad. Sci. (1985) 440, 212–223.

[38] R.P. Stanley, Two poset polytopes. Discrete Comput. Geom. 1 (1986), 9–23.

[39] R.P. Stanley, Flag f-vectors and the cd-index. Math. Z. 216 (1994), 483–499.

[40] R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics 49. Cambridge University Press, Cambridge, 1997.

[41] R.P. Stanley, Graphs and related symmetric functions: ideas and applications, Disc. Math. 193 (1998), 267-286.

[42] R.P. Stanley, Enumerative combinatorics Vol. 2, Cambridge Studies in Advanced Mathematics 62. Cambridge University Press, Cambridge, 1999.

[43] R.P. Stanley, Combinatorics and Commutative Algebra, 2nd ed., Birkhäuser, Basel, 1996.

[44] E. Steingrímsson, Permutation statistics of indexed permutations. European J. Combin. 15 (1994), 187–205.

[45] Stückrad, Jürgen; Vogel, Wolfgang On Segre products and applications. J. Algebra 54 (1978), 374–389.

[46] E.C. Titchmarsh, The Theory of Functions, 2nd ed., Oxford University Press, Oxford, 1985.

[47] D. Wagner, Enumeration of functions from posets to chains, Eur. J. Comb. 13 (1992), 313–324.

[48] D. Wagner, Total positivity of Hadamard products, J. Math. Anal. Appl. 163 (1992), 459–483.

[49] D. Wagner, personal communication, 2002.

[50] D. White, personal communication, 2002.

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

  E-mail address: reiner@math.umn.edu

Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, 35032 Marburg, Germany

  E-mail address: welker@mathematik.uni-marburg.de