New York Journal of Mathematics

New York J. Math. 4 (1998) 83–95.

Two Signed Associahedra

H. Burgiel and V. Reiner

Abstract. The associahedron is a convex polytope whose vertices correspond to triangulations of a convex polygon. We define two signed or hyperoctahedral analogues of the associahedron, one of which is shown to be a simple convex polytope, and the other a regular CW-sphere.

Contents

1. Introduction 83 2. The Simple Signed Associahedron 85 3. The Non-simple Signed Associahedron 90 4. Remarks, Open Problems 93 Acknowledgments 94 References 94

1. Introduction

The d-dimensional associahedron or Stasheff polytope is a d-polytope whose facial structure relates to triangulations of a polygon (see [13]) or associative bracketings of a product. This paper is about two signed or hyperoctahedral analogues of the associahedron.

To briefly describe these two signed associahedra, we define the graphs which form their 1-skeleta. Both signed associahedra have vertices indexed by completely signed triangulations of a convex (n+2)-gon P_{n}, which we now define. Number the vertices of P_{n} from 0 to n + 1 proceeding counter-clockwise around its perimeter, as in Figure 1. A completely signed triangulation is a triangulation along with an assignment of + or − to each of the vertices 1, 2, …, n (so nothing is assigned to the vertices labelled 0, n + 1).

The classical associahedron has the property that each vertex lies on d edges, that is to say it is a simple polytope. One of the two signed associahedra shares this

\begin{matrix}c \\ ◯ \end{matrix}1998 State University of New York ISSN 1076-9803/98

Received June 20, 1997.

Mathematics Subject Classification. Primary, 52B12, 20F55.

Key words and phrases. associahedron, Coxeter groups, convex polytope, triangulation.

First author’s research supported by a Postdoctoral fellowship at The Geometry Center at the University of Minnesota. Second author’s research supported by a Sloan Foundation Fellowship and a University of Minnesota McKnight-Land Grant Fellowship.

property, and hence we dub it the simple signed associahedron. In the simple signed associahedron, there will be an edge between two completely signed triangulations if either

• the assignments of + or − are the same, but the triangulations differ by flipping the diagonal in a single quadrilateral, or

• the triangulations are the same, but the signs differ exactly on the third vertex of the triangle which contains the vertices 0, n + 1.

Figure 2(a) depicts a small part of the graph of the 3-dimensional simple signed associahedron.

In the non-simple signed associahedron, there will be an edge between two completely signed triangulations if either

• the assignments of + or − are the same, but the triangulations differ by flipping the diagonal in a single quadrilateral, or

• the triangulations are the same, but the signs differ exactly on some vertex i which lies in a triangle of the triangulation having vertices i − 1, i, i + 1.

Figure 2(b) depicts a small part of the graph of the 3-dimensional non-simple signed associahedron.

Our main results are as follows. Corollary 2.3 shows that the graph of the simple signed associahedron is actually the 1-skeleton of a simple polytope, whose entire facial structure is described in the next section. Theorem 3.1 shows that the graph of the non-simple signed associahedron is actually the 1-skeleton of a regular CW - sphere (see Section 3) whose facial structure is described in Section 3. We do not know whether this sphere is the boundary of a convex polytope.

Before closing this section, we offer some motivation for these results, and also contrast them with a recent construction of a signed associahedron by Simion [17].

The classical associahedron makes its appearance in many different places, such as coherence theorems for monoidal categories [14, 18], moduli spaces of pointed curves [10], spaces of Morse functions [11], and resolutions both for the associative law [1] and the Steinberg relations on elementary matrices [11]. In many of these contexts, the sphericity of the boundary of the associahedron plays an important role. It is our hope that one or both of the two signed associahedra we describe will occur in similar contexts, and that our proof of their sphericity will make them easier to use.

There is a third signed associahedron recently defined by Simion [17] which is also a simple polytope. The vertices in this signed associahedron correspond to the triangulations of a centrally-symmetric 2(n+1)-gon which are themselves centrallysymmetric. She was motivated by the beauty of the results on enumerating faces in the usual associahedron (see [13, §6]), and her signed associahedron is indeed very well-behaved from the point of view of face-enumeration. Her construction also provides the first motivating example for a theory of “equivariant fiber polytopes” (see [2] for the usual theory of fiber polytopes) which studies subdivisions of polytopes which are invariant under symmetry groups. In contrast, our signed associahedra are not as well-behaved from the enumerative point of view, and seem not to be part of any variant of the theory of fiber polytopes yet discovered. In this way, they seem more akin to the Coxeter-associahedra studied in [15].

Figure 1. The labelling of vertices in the (n + 2)-gon P_{n}.

Figure 2. A part of the graph for (a) the simple signed associahedron, (b) the non-simple signed associahedron

Figure 3. The two trees associated to a dissection

2. The Simple Signed Associahedron

In this section we define a poset K_{n}^{B} which we will eventually interpret as the face poset of our first signed associahedron. Our goals are to show that it is the face poset of a simple n-dimensional polytope, and compute its f-vector.

We define a dissection of P_{n} to be a subset of non-crossing diagonals in the polygon. We think of the diagonals chosen as decomposing P_{n} into smaller polygons. The smaller polygon containing the edge {0, n + 1} will be denoted the root polygon. This terminology derives from the following picture which we will use frequently (see Figure 3 (a)): we think of the the polytopal decomposition as defining a rooted plane tree having a vertex for each of the smaller polygons, the root vertex corresponding to the root polygon, and an edge connecting two vertices if their corresponding polygons share a boundary edge.

A signed dissection is a dissection of P_{n} along with an assignment of a sign from {0, +, −} to each of the vertices labelled, 1, 2, …, n with the following property: vertices assigned 0 may only occur in the root polygon, and if any of the vertices in the root polygon are assigned 0, then they must all be assigned 0. We call the improper signed dissection the one which uses no diagonals in the decomposition, and assigns every vertex 0.

Define a partial order on the signed dissections of P_{n} as follows: δ ≤ δ′ if

• as a dissection, δ refines δ′, i.e., the diagonals used in δ contain all the diagonals used in δ′, and

• for each vertex i = 1, 2, …, n, the sign assigned to vertex i by δ is less than

or equal to the one assigned by δ′ in the partial order +, − < 0. Finally, let K_{n}^{B} denote the poset of all proper signed polytopal decompositions under the above partial order, and let (K_{n}^{B})^{∗} denote the order dual to K_{n}^{B} with an extra minimum element ˆ0 adjoined (corresponding to the improper signed dissection).

Proposition 2.1. (K_{n}^{B})^{∗} is the face poset of an (n − 1)-dimensional simplicial complex.

By abuse of notation we also denote this simplicial complex by (K_{n}^{B})^{∗}.

Proof. We must show that

• for every maximal element x, the interval [ˆ0, x] in (K_{n}^{B})^{∗} is isomorphic to a Boolean algebra of rank n, and

• (K_{n}^{B})^{∗} is a meet-semi-lattice, i.e., any two elements x, y have a greatest lower bound x ∧ y.

To show the first assertion, assume x is some maximal element in (K_{n}^{B})^{∗}, so that x is a completely signed triangulation. Create a Boolean algebra on the ground set X = {d_{1}, …, d_{n}} ∪ {v}, where {v} is just a singleton set. Given y ∈ [ˆ0, x], it must use some subset of the diagonals d_{1}, …, d_{n}, and it either assigns the same sign + or − as x did to the root vertex, or it assigns 0 to the root vertex. Let f(y) be the subset of X consisting of the diagonals y uses, unioned with either {v} or the empty set depending on whether y assigns ± or 0 to the root vertex, respectively. It is easy to check that y is completely determined by the set f(y) once we know it is in [ˆ0, x]. Furthermore, it is easy to check that the order relation on [ˆ0, x] corresponds to inclusion of the sets f(y). Thus f gives the desired isomorphism between [ˆ0, x] and the Boolean algebra 2^{X}.

To show the second assertion, given x, y in (K_{n}^{B})^{∗}, we will construct x ∧ y. First, we produce a precursor candidate w by taking the dissection whose set of diagonals is the intersection of the sets of diagonals from x and from y, and assigning {+, −, 0} to the vertices 1, 2, …, n by taking the componentwise meet of the sign assignments of x and y in the partial order 0 < +, −. The problem is that w may fail to be a signed dissection in that it may have 0 assigned to a vertex which is not in the root polygon, or it may have 0 assigned to some but not all of the root polygon’s vertices. To fix this problem, we start with w and let T be the tree associated to its dissection. Form a new dissection by removing all diagonals corresponding to edges in T that lie on a path to the root from some polygon in w containing a vertex assigned 0. In this new dissection, if there are any 0 assignments to vertices in the root polygon, then change the assignment to 0 for all vertices in the root polygon. This clearly gives a signed dissection, which we claim is x ∧ y.

To see that x ∧ y really is the greatest lower bound of x, y, let z be any other lower bound for x, y, so that z < x, y. Certainly the dissection in z must be coarser than that of the precursor w, and it must have 0 assigned to a vertex whenever w

Figure 4. The simplicial complexes (K_{2}^{B})^{∗} and (K_{3}^{B})^{∗}

did. But this then implies that all these 0 vertices must lie in the root polygon of z, and hence all the diagonals of w lying on a path from one of these vertices to the root in T must not be present in z. This implies z has a coarser dissection than x ∧ y, and it is easy to check that it must also have sign assignment componentwise bounded by that of x ∧ y. □

Figure 4 depicts the geometric realizations of the simplicial complexes (K_{n}^{B})^{∗} for n = 2, 3. Note that in both cases the simplicial complexes triangulate a sphere 𝕊^{n−1}. Furthermore, the sphere appears to be polytopal, i.e., the boundary complex of a simplicial polytope, in anticipation of the next theorem.

Theorem 2.2. The simplicial complex (K_{n}^{B})^{∗} is isomorphic to the boundary complex of an n-dimensional simplicial polytope.

Proof. We emulate the proof in §3 of [13].

Let Δ_{0} be the boundary complex of an n-dimensional hyperoctahedron or crosspolytope, with vertices labelled {±1, …, ±n} in such a way that the vertices ±i are antipodal for all i. Faces of Δ_{0} are then isotropic subsets of {±1, …, ±n}, that is subsets which do not contain any pair {+i, −i}. Say that a face F = {i_{1}, …, i_{r}} is contiguous if the set of absolute values {|i_{1}|, …, |i_{r}|} form an interval in ℤ.

Next, perform stellar subdivisions (see [13], §2) of each of the contiguous faces of Δ_{0} to obtain a simplicial complex Δ^{∗} in any order which subdivides the higher dimensional faces before the lower dimensional faces (actually any order which extends the partial ordering by reverse inclusion will do). These stellar subdivisions are well-defined since at the stage where one is about to subdivide the face corresponding to some contiguous subset, that subset is still a face in the subdivided complex. See Figure 5 for pictures of Δ_{0} and Δ^{∗} when n = 3.

The complex Δ^{∗} is clearly the boundary complex of an n-dimensional simplicial polytope, since it comes from Δ_{0} by a sequence of stellar subdivisions which preserve polytopality. We claim that Δ^{∗} is isomorphic to the simplicial complex (K_{n}^{B})^{∗}, and our proof exactly follows the plan in [13], §3.

One first notes that the vertices of Δ^{∗} correspond to contiguous isotropic subsets of {±1, …, ±n}. Contiguous isotropic subsets in turn correspond to diagonals in P_{n} along with a partial assignment of signs to the vertices strictly enclosed by that

Figure 5. Δ_{0}, Δ^{∗} ≃ (K_{n}^{B})^{∗} and Σ_{n}^{B} when n = 3

diagonal (except if the isotropic subset has cardinality n, in which case there is no diagonal, just a complete assignment of signs).

One then checks that if two contiguous isotropic subsets form an edge in Δ^{∗}, then

• they must agree on any signs which both assign, i.e., their union cannot contain any pair {+i, −i}, and

• they cannot correspond to crossing diagonals (checking this uses Lemma 1 of [13]).

One concludes that every maximal face of Δ^{∗} corresponds to a completely signed triangulation of P_{n}, i.e., to some maximal face of (K_{n}^{B})^{∗}. It is easy to check that Δ^{∗} is a simplicial pseudomanifold, i.e., every codimension 1 face lies in exactly 2 maximal faces, and any two maximal faces are connected by a path of maximal faces with adjacent ones sharing a codimension 1 face. Since both (K_{n}^{B})^{∗} and Δ^{∗} are obviously pseudomanifolds, the two complexes must be isomorphic. □

Corollary 2.3. The poset K_{n}^{B} is the face poset of the boundary of an n-dimensional simple polytope.

From now on, the simple polytope in the corollary will be referred to as the simple signed associahedron. We again abuse notation and refer to the polytope as K_{n}^{B}.

Remark 2.4. It follows immediately from the construction in the previous proof that as a simplicial complex, we may view (K_{n}^{B})^{∗} as a refinement (subdivision) of the boundary complex of the n-dimensional cross-polytope Δ_{0}. One can also show using this construction that (K_{n}^{B})^{∗} can be further subdivided into a complex isomorphic to the first barycentric subdivision of Δ_{0}, which is sometimes known as the Coxeter complex Σ_{n}^{B} for B_{n} (see [12]). Figure 5 illustrates this relationship.

Our next goal is to compute the f-vector of K_{n}^{B} or equivalently of its dual (K_{n}^{B})^{∗}. Recall that the f-vector of a polytope P is simply the sequence

(f_{−1}(P), f_{0}(P), …, f_{d−1}(P)),

where f_{i}(P) is the number of i-dimensional faces of P. It is not difficult to show that

f_{k}((K_{n}^{B})^{∗}) = 2^{n}a_{n,k} + ∑_{m=2}^{n} 2^{n+1−m}a_{n,k,m} (1)

where a_{n,k} is the number of dissections of the (n+2)-gon P_{n} using k diagonals, and a_{n,k,m} is the number of dissections of P_{n} using k + 1 diagonals in which the root polygon has m + 1 vertices. A formula for a_{n,k} was given by Kirkman (see [13]):

a_{n,k} = \frac{1}{n + 1}\binom{n − 1}{k}\binom{n + k + 1}{k + 1} (2)

To obtain a formula for a_{n,k,m}, we first revise the the correspondence between dissections and rooted trees that was illustrated in Figure 1. Given a dissection of P_{n}, add on to its tree an extra leaf outside each of the edges (i, i + 1) with 1 ≤ i ≤ n − 1, as shown in Figure 3 (b). This correspondence shows that a_{n,k,m} = b_{n+1,k+2,m} where b_{n,k,m} is the number of plane rooted trees with

• n leaves,

• every internal vertex (including the root) having at least two children,

• k non-leaf vertices (including the root),

• root vertex of degree m.

We next define the generating function

\begin{aligned}F (x, y, z) & = x + ∑_{n≥2,k≥1,m≥2} b_{n,k,m}x^{n}y^{k}z^{m} \\ & = x + x^{2}yz^{2} + x^{3}(2y^{2}z^{2} + yz^{3}) + x^{4}(5y^{3}z^{2} + 2y^{2}z^{2} + 3y^{2}z^{3} + yz^{4}) + … \end{aligned}

in which the extra term x on the right-hand side accounts for the degenerate case of a tree with only one vertex, which we count as a leaf. We will next use generating function manipulations to prove the following lemma.

Lemma 2.5.

b_{n,k,m} = \frac{m}{n} ( \begin{matrix}n − m − 1 \\ k − 2 \end{matrix} ) ( \begin{matrix}n + k − 2 \\ k − 1 \end{matrix} ) .

Proof. The standard recursive construction for rooted plane trees removes the root vertex, leaving a sequence of rooted plane subtrees. This yields the following functional equation for F:

F (x, y, z) = x + y ∑_{m≥2} z^{m}F (x, y, 1)^{m} = x + \frac{yz^{2}F (x, y, 1)^{2}}{1 − zF (x, y, 1)}. (3)

We next attempt to determine the coefficients of powers of F (x, y, 1), from which we can determine the b_{n,k,m}. Let p(x, y) = F (x, y, 1), so that setting z = 1 above gives

\begin{aligned}p & = x + \frac{yp^{2}}{1 − p} \\ x & = p − \frac{yp^{2}}{1 − p} \end{aligned} (4)

Equation (3) says that for m ≥ 2 the coefficient of z^{m} in F (x, y, z) is yp(x, y)^{m}. Lagrange Inversion applied to equation (4) allows us to find the coefficient of x^{n} in the power series p^{m}. Letting

g(x) = x − \frac{yx^{2}}{1 − x} = p^{−1}(x),

yields

[x^{n}]p^{m} = \frac{m}{n}[x^{n−m}] (\frac{x}{g(x)})^{n}

where here [x^{n}]h(x, y) denotes the coefficient of x^{n} in h(x, y). From this, it is not difficult to calculate that

[x^{n}]p^{m} = \frac{m}{n} ∑_{i+j=n−m}(−1)^{i} ( \begin{matrix}n \\ i \end{matrix} ) ( \begin{matrix}n + j − 1 \\ j \end{matrix} ) (1 + y)^{j}.

Applying this to equation (3), we see

b_{n,k,m} = [x^{n}y^{k−1}]p^{m}
= \frac{m}{n} ∑_{i+j=n−m}(−1)^{i} ( \begin{matrix}n \\ i \end{matrix} ) ( \begin{matrix}n + j − 1 \\ j \end{matrix} ) ( \begin{matrix}j \\ k − 1 \end{matrix} ) .

This simplifies to:

b_{n,k,m} = \frac{m}{n} ( \begin{matrix}2n − m − 1 \\ n − m \end{matrix} ) ( \begin{matrix}n − m \\ k − 1 \end{matrix} ) _{2}F_{1} ( \begin{matrix}−n & k + m − n − 1 \\ & 1 + m − 2n & 1 \end{matrix} ) .

where we are using standard hypergeometric series notation (see e.g. [16]). Applying the Chu-Vandermonde summation formula to the _{2}F_{1} then gives the desired result. □

If we now observe that a_{n,k} = b_{n+1,k+2,1}, then equation (1) yields the following:

Theorem 2.6.

f_{k}((K_{n}^{B})^{∗}) = ∑_{m=1}^{n} 2^{(n−m+1)} \frac{m}{n + 1} ( \begin{matrix}n − m \\ k \end{matrix} ) ( \begin{matrix}n + k + 1 \\ k + 1 \end{matrix} )

= _{3}F_{2} ( \begin{matrix}n + 2 & 1 − k & m − n \\ & 2 & −n & 1 \end{matrix} )

It is somewhat disappointing that the summation in the preceding theorem does not appear to simplify in any nice way, making the f-vector for (K_{n}^{B})^{∗} somewhat more complicated than its unsigned counterpart from [13]. Even more unfortunately, we do not know how to simplify the formula for the h-vector (see [13] for a definition) of (K_{n}^{B})^{∗} which comes from summing the above formula for the f-vector.

3. The Non-simple Signed Associahedron

In this section we briefly discuss another signed analogue of the associahedron. It will be a poset N_{n}^{B} which is again the face poset of a regular CW -sphere, but we do not know whether this sphere is polytopal.

Given a dissection of the (n + 2)-gon P_{n}, the leaf polygons are the polygons which contain at most one edge not of the form {i, i + 1} with 1 ≤ i, i + 1 ≤ n. For a polygon in a dissection, the interior vertices are those which neither carry the maximum nor the minimum label among all vertices of the polygon. Say that an assignment of a sign from {0, +, −} to each of the vertices labelled 1, 2, …, n is a signed dissection of the 2^{nd} kind if

• every vertex assigned 0 is an interior vertex of some leaf polygon, and

• whenever a leaf polygon has some interior vertex assigned 0, then all of its interior vertices must be assigned 0.

Figure 6. The map ψ: A chain of isotropic subsets S_{1} ⊂ S_{2} ⊂ S_{3} of {±1, ±2, …, ±11}, and the associated signed dissection

The partial order on signed dissections of P_{n} of the 2^{nd} kind is the same as that on signed dissections, and we let N_{n}^{B} denote this poset. Let (N_{n}^{B})^{∗} denote its dual poset. The goal of this section will be to sketch the proof of the following fact:

Theorem 3.1. (N_{n}^{B})^{∗} is the face poset of a regular CW -complex homeomorphic to an (n − 1)-sphere.

We recall here [3, (12.4)] that a Hausdorff space X is a regular CW -complex if it has a covering by a family of closed balls (homeomorphs of d-balls for d ≥ 0) whose interiors partition X, and for which the boundary of each ball is a union of other balls. We will call the CW -sphere referred to in Theorem 3.1 the non-simple signed associahedron, and by abuse of notation, denote it (N_{n}^{B})^{∗}. We have depicted (N_{3}^{B})^{∗} in Figure 8.

Our strategy is very similar to the one employed in [15, §2]. We define a map ψ from the poset of faces of the hyperoctahedral group’s Coxeter complex Σ_{n}^{B} to the poset (N_{n}^{B})^{∗}. Then we show that the inverse image ψ^{−1}((N_{n}^{B})_{≤y}^{∗}) of each principal order ideal (N_{n}^{B})_{≤y}^{∗} in N_{n}^{B} is a ball, and that this gives a regular CW-decomposition of Σ_{n}^{B}.

To this end, recall that the Coxeter complex Σ_{n}^{B} for the hyperoctahedral group B_{n} is the barycentric subdivision of the n-cube or the n-hyperoctahedron. Faces of Σ_{n}^{B} may be identified with chains

x := (S_{1} ⊂ S_{2} ⊂ ⋯ ⊂ S_{r})

of isotropic subsets of {±1, ±2, …, ±n}; recall that S_{i} is isotropic if it contains at most one element of each pair {+i, −i}.

Given such a chain x, we can produce a signed dissection ψ(x) of P_{n} of the second kind in the following way (see Figure 6). Let E_{i} be the path of edges which starts at the vertex of P_{n} labelled 0, visits the vertices labelled by the elements of S_{i} in order of increasing absolute value, and then ends at the vertex labelled n + 1. The union of the paths ⋃_{i} E_{i} gives a dissection of P_{n}, and the largest set S_{r} gives a partial assignment of + or − signs to the vertices, which can be completed to a full assignment by putting 0 on the remaining vertices. It is not hard to check that this gives a signed dissection of the 2^{nd} kind.

For a given signed dissection of the 2^{nd} kind y in (N_{n}^{B})^{∗}, we now describe the inverse image ψ^{−1}((N_{n}^{B})_{≤y}^{∗}) of the principal order ideal (N_{n}^{B})_{≤y}^{∗} generated by y. Let P_{y} be the partial order coming from the tree structure on those polygons of the dissection y which do not contain vertices assigned 0, in which the root polygon is lowest in the partial order. An example is shown in Figure 7. Any non-empty order

Figure 7. An illustration of Δ(J(P_{y}) − ∅) ≃ ψ^{−1}((N_{n}^{B})_{≤y}^{∗})

ideal I in P_{y} gives rise to an isotropic subset by replacing each polygon in I by the set of labels of its interior vertices along with their assigned signs. This gives a poset isomorphism κ between ψ^{−1}((N_{n}^{B})_{≤y}^{∗}) and the poset of chains (ordered by inclusion) in the distributive lattice J(P_{y}) of order ideals in P_{y}.

Since only non-empty order ideals are relevant, the map κ then induces a simplicial isomorphism from the order complex Δ(J(P_{y})−∅) to ψ^{−1}((N_{n}^{B})_{≤y}^{∗}), where here we are considering ψ^{−1}((N_{n}^{B})_{≤y}^{∗}) as a simplicial complex (and in fact, a subcomplex of Σ_{n}^{B}).

It is known that for any poset P, the order complex ΔJ(P) is shellable [4], and since every codimension 1 face lies in at most 2 maximal faces, shellability implies that it is homeomorphic either to a (|P |−2)-dimensional ball or to a (|P |−2)-sphere [8]. Furthermore, if the poset P has at least one order relation (as is the case for P_{y}), the complex Δ(J(P) − ∅) will be homeomorphic to a ball. One can check that under the simplicial isomorphism

Δ(J(P_{y}) − ∅) ≅ ψ^{−1}((N_{n}^{B})_{≤y}^{∗})

the boundary ∂Δ(J(P_{y})−∅) maps to the subcomplex ψ^{−1}((N_{n}^{B})_{<y}^{∗}). Consequently, the decomposition

Σ_{n}^{B} = ⋃_{y∈N_{n}^{B}} ψ^{−1}((N_{n}^{B})_{≤y}^{∗})

is a regular CW-sphere whose face poset is (N_{n}^{B})^{∗}, finishing the sketch proof of Theorem 3.1.

Remark 3.2. It is well-known that the Coxeter complex Σ_{n}^{B} may be identified with the barycentric subdivision of either the n-cube or the n-hyperoctahedron, and hence refines them both. The map ψ shows that the sphere (N_{n}^{B})^{∗} is a coarsening of Σ_{n}^{B}, and a slightly closer look reveals the fact that (N_{n}^{B})^{∗} refines both the n-cube and the n-hyperoctahedron (Figure 8).

To see this fact, note that two maximal chains

\begin{aligned}x : & = (S_{1} ⊂ S_{2} ⊂ ⋯ ⊂ S_{n}) \\ x′ : & = (S′_{1} ⊂ S′_{2} ⊂ ⋯ ⊂ S′_{n}) \end{aligned}

represent faces of Σ_{n}^{B} that lie in a common (subdivided) face of the n-cube if and only if S_{1} = S′_{1}. They lie in a common (subdivided) face of the n-hyperoctahedron if and only if S_{n} = S′_{n}. So one must check that ψ(x) = ψ(x′) implies both S_{1} = S′_{1} and S_{n} = S′_{n}, which is straightforward: ψ(x) = ψ(x′) will be some fully signed Figure 8. Σ_{n}^{B} refines (N_{n}^{B})^{∗}, which refines both the nhyperoctahedron and n-cube, illustrated for n = 3

triangulation of the second kind y, and then S_{1} = S′_{1} is the sign and label of the root vertex in y, while S_{n} = S′_{n} is the set of signs and labels on the vertices in y.

4. Remarks, Open Problems

Remark 4.1. Is the non-simple signed associahedron N_{n}^{B} the face poset of a convex polytope? Are there embeddings of it and of the simple signed associahedron K_{n}^{B} using Gale transforms as in [13, §4] and [9, Chapter 7]?

Remark 4.2. In [6], the authors consider a natural map α from the symmetric group S_{n} to the vertices of the usual (n − 2)-dimensional associahedron, having many nice properties:

• permutations π, π′ ∈ S_{n} which differ by an adjacent transposition map to either the same vertex, or to adjacent vertices of the associahedron,

• the inverse image under α of any vertex in the associahedron is a set of permutations which forms an interval [π_{1}, π_{2}] in the weak order on S_{n},

• any linear extension of the weak Bruhat order on S_{n} gives rise to a shelling of the Coxeter complex for S_{n}, and pushing such an ordering forward by α gives rise to a shelling order of the dual simplicial complex to the associahedron.

In particular, the last property listed allows one to compute the h-vector of the associahedron by a method very similar to [13, §6].

In the signed case, there are again natural maps from the hyperoctahedral group B_{n} of signed permutations to the vertices of the two signed associahedra K_{n}^{B}, N_{n}^{B} which have properties analogous to the first property above. More specifically, the map from B_{n} to the vertices of N_{n}^{B} is no more than the restriction of the map ψ from the previous section to the set of maximal faces of the Coxeter complex. If one chooses a set of Coxeter generators for B_{n} to be the adjacent transpositions s_{i} = (i, i + 1) along with the sign change s_{n} in the last coordinate, then two signed permutations which differ by some s_{i} with 1 ≤ i ≤ n will either map to the same vertex of N_{n}^{B} (= maximal face of (N_{n}^{B})^{∗}) or to two adjacent vertices. A similar map can be defined from B_{n} to the vertices of K_{n}^{B}, and the same property holds.

94 H. Burgiel and V. Reiner

Unfortunately, there are examples of vertices from K_{4}^{B} and N_{4}^{B} whose inverse images in B_{n} under these maps do not form an interval in the weak Bruhat order (with respect to the above set of Coxeter generators), although they will always be convex subsets of B_{n} in the sense of Tits (see [5, Appendix]). It is also unfortunate that linear extensions of the weak Bruhat order on B_{n} do not map forward to a shelling order on the simplicial complex (K_{n}^{B})^{∗}. In fact, we do not know of any simple explicit shelling of (K_{n}^{B})^{∗} which helps to compute its h-vector, even though shellings are known to exist because it is a polytope [7].

Acknowledgments

The authors would like to thank Ira Gessel for suggesting Lagrange inversion in the proof of Lemma 2.5, Dennis Stanton for help with hypergeometric series, and Rodica Simion for explaining her results [17].

References

[1] R. Adin and D. Blanc, Resolutions of associative and Lie algebras. preprint 1998.

[2] L. J. Billera and B. Sturmfels, Fiber polytopes. Ann. Math. 135 (1992), 527–549, MR 93e:52019.

[3] A. Björner, Topological methods, Handbook of Combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 1819–1872, MR 96m:52012.

[4] A. Björner, A. Garsia and R. Stanley, An introduction to Cohen-Macaulay partially ordered sets, Ordered sets (Banff, Alberta 1981), NATO Adv. Study Inst. Ser. C: Math. Phys. Sci. 83 Reidel, Dordrecht-Boston, 1982, pp. 583–615, MR 83i:06001.

[5] A. Björner and M. Wachs, Permutation statistics and linear extensions of posets. J. Comb. Theory Series A 58 (1991), 85–114, MR 92m:06010.

[6] A. Björner and M. Wachs, Shellable nonpure complexes and posets, II, Trans. Amer. Math. Soc. 349 (1997), 3945–3975, MR 98b:06008.

[7] H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971), 197–205.

[8] G. Danaraj and V. Klee, Shellings of spheres and polytopes, Duke Math. J. 41 (1974), 443– 451.

[9] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, Resultants, and Multidimensional Determinants Birkhäuser, Boston, 1994, MR 95e:14045.

[10] M. M. Kapranov, Permutoassociahedron, Mac Lane’s coherence theorem and asymptotic zones for the KZ equation, J. Pure and Appl. Algebra 85 (1993), 119–142, MR 94b:52017.

[11] M. M. Kapranov and M. Saito, Hidden Stasheff polytopes in algebraic K-theory and in the space of Morse functions, preprint, 1997.

[12] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no. 29, Cambridge Univ. Press, Cambridge, 1990, MR 92h:20002.

[13] C. Lee, The associahedron and triangulations of an n-gon, Europ. J. Combin. 10 (1989), 551–560, MR 90i:52010.

[14] S. Mac Lane, Natural associativity and commutativity, Rice Univ. Studies 49 (1963), 28–46.

[15] V. Reiner and G. Ziegler, Coxeter-associahedra, Mathematika 41 (1994), 364–393, MR 95m:52023.

[16] R. Roy, Binomial identities and hypergeometric series, Amer. Math. Monthly 94 (1987), 36–46, MR 88f:05012.

[17] R. Simion, personal communication 1998.

[18] J. D. Stasheff, Homotopy associativity of H-spaces, I, II, Trans. Amer. Math. Soc. 108 (1963), 275–292; Trans. Amer. Math. Soc. 108 (1963), 293–312.

Two Signed Associahedra 95

Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 South Morgan St. (M/C 249), Chicago, IL 60607-7045

burgiel@math.uic.edu http://math.uic.edu/˜ burgiel

University of Minnesota School of Mathematics, Minneapolis, MN 55455 reiner@math.umn.edu http://www.math.umn.edu/˜ reiner

This paper is available via http://nyjm.albany.edu:8000/j/1998/4-7.html.