EQUIVARIANT FIBER POLYTOPES

VICTOR REINER

Abstract. The equivariant generalization of Billera and Sturmfels’ fiber polytope construction is described. This gives a new relation between the associahedron and cyclohedron, a different natural construction for the type B permutohedron, and leads to a family of order-preserving maps between the face lattice of the type B permutohedron and that of the cyclohedron.

To the memory of Rodica Simion.

Contents

1. Introduction 1 2. Equivariant polytope bundles 3 2.1. Group actions on polytope bundles 3 2.2. Equivariant fiber polytopes 7 2.3. Equivariant secondary polytopes 9 3. Small, visualizable examples 10 3.1. The standard example. 10 3.2. Triangulations of a regular hexagon. 11 4. Application examples. 13 4.1. Cyclohedra and associahedra. 13 4.2. The type B permutohedron. 14 4.3. Maps from the type B permutohedron to the cyclohedron. 15 5. Remarks/Questions 18 Acknowledgements 20 References 21

1. Introduction

Much of this paper is motivated by a new relationship between two families of convex polytopes which have appeared in diverse places within topology, geometry, and combinatorics (see e.g. [4, 9, 11, 12, Figure 1. The 3-dimensional associahedron, containing the 2-dimensional cyclohedron as a planar slice.

Key words and phrases. fiber polytope, associahedron, cyclohedron, equivariant.

Supported by NSF grant DMS–9877047.

15]): the associahedra (or Stasheff polytopes), and the cyclohedra (or type B associahedra).

There is already a well-known relation between these two families: any face in a cyclohedron is combinatorially isomorphic to a Cartesian product of a lower-dimensional cyclohedron along with a collection of lower-dimensional associahedra [15, §3.3], [5, Proposition 3.2.1]. Our point of departure is a different relationship, illustrated in Figure 1. The 3-dimensional associahedron is depicted in Figure 1(a), with its vertices indexed by triangulations of a (centrally symmetric) hexagon. Figure 1(b) shows inside it a hexagonal slice representing the 2-dimensional cyclohedron, with vertices indexed by the subset of triangulations possessing central symmetry - this slice is the invariant subpolytope for a reflection symmetry acting on the associahedron, which swaps two vertices if they correspond to triangulations that differ by 180^{∘} rotation.

Our main result (Theorem 2.10) asserts a similar relationship generally when one considers subdivisions of a polytope which are invariant under some finite group of symmetries. The theory of fiber polytopes introduced by Billera and Sturmfels [1] shows that whenever one has a linear surjection of convex polytopes P →^{π} Q, there is an associated convex polytope Σ(P →^{π} Q), called the fiber polytope. This fiber polytope has dimension dim P − dim Q, and its faces correspond (roughly) to the subdivisions of Q by cells which are projections of families of faces of P. Our result says that when the projection P →^{π} Q is Gequivariant for some finite group G acting as symmetries on both P and Q, then G acts a group of symmetries on Σ(P →^{π} Q), and the G-invariant subpolytope Σ^{G}(P →^{π} Q) (the equivariant fiber polytope) is a polytope of dimension dim P^{G} − dim Q^{G} whose faces correspond to those subdivisions which are G-invariant.

The paper is structured as follows. Section 2 proves the main results, with Subsection 2.1 containing the technical details needed to generalize fiber polytopes to the equivariant setting. Theorem 2.10 on the existence and dimension of the equivariant fiber polytope is deduced in Subsection 2.2. The special case of equivariant secondary polytopes is discussed in Subsection 2.3.

Section 3 contains some low-dimensional examples that are easily visualized, while Section 4 gives some general examples as applications. In particular, Example 4.1 explains the above relation between associahedra and cyclohedra, and Example 4.2 explains how the type B permutohedron (that is, the zonotope generated by the root system of type B) occurs as an equivariant fiber polytope. In Section 4.3 we answer a question of R. Simion, by exhibiting a family of natural maps between the face lattices of the B_{n}-permutohedron and n-dimensional cyclohedron.

Section 5 lists some remarks and open questions.

2. Equivariant polytope bundles

2.1. Group actions on polytope bundles. For convenience, we work with the same notation as in [1, §1] in working out the equivariant versions of the same results.

Let B → Q be a polytope bundle, that is, Q is a convex polytope in ℝ^{d}, and for each x in Q, the set B_{x} is a convex polytope in ℝ^{n}, such that the graph ⋃{B_{x} × x : x ∈ Q} is a bounded Borel subset of ℝ^{n+d}. We further assume that we have a finite group G acting linearly on both ℝ^{d} and ℝ^{n}. Definition 2.1. Say that B → Q is a G-equivariant polytope bundle if

• G acts as symmetries of Q, i.e. g(Q) = Q for all g in G. In particular, without loss of generality, the centroid of Q is the origin 0.

• for every x in Q and g in G one has B_{g(x)} = g(B_{x}). Alternatively, equivariance of a polytope bundle is equivalent to G-

invariance of Q, along with G-invariance of B with respect to a natural G-action on polytope bundles: given B → Q and g in G, let gB → Q be the polytope bundle defined by (gB)_{x} := g(B_{g^{−1}x}).

The linear action of G on ℝ^{n} induces a contragredient action on the dual space ℝ^{n∗} of functionals: g(ψ)(x) := ψ(g^{−1}(x)) for g ∈ G, y ∈ ℝ^{n}, ψ ∈ ℝ^{n∗}.

A section γ of B → Q is a choice of γ(x) ∈ B_{x} for each x. If B → Q is equivariant, there is a G-action on sections defined by g(γ)(x) := gγ(g^{−1}x).

For any of these G-actions, define the averaging (or Reynolds) operator

π_{G} = \frac{1}{|G|} ∑_{g∈G} g

which is an idempotent projector onto the subset (or subspace) of Ginvariants. It turns out that much of the reason that fiber polytopes interact well with finite group actions boils down to π_{G} being a linear operator which is a convex combination of the group operations g in G.

Recall that for a polytope bundle B → Q, the Minkowski integral ∫_{Q} B is the subset of ℝ^{n} consisting of all integrals ∫_{Q} γ of measurable sections γ, and that this is a non-empty compact, convex subset of ℝ^{n}.

Proposition 2.2. Integration commutes with the G-action on sections of a G-equivariant polytope bundle B → Q:

∫_{Q} gγ = g (∫_{Q} γ)

for all g in G.

Proof.

∫_{Q} gγ = ∫_{Q} g(γ(g^{−1}x))dx
= g (∫_{Q} γ(g^{−1}x)dx)
= g (∫_{Q} γ(u)du)

Here the second equality uses linearity of g and linearity of integration. The third equality comes from the change of variable x = g(u), using the fact that the Jacobian determinant for this change of variable is det(g), which must be ±1, since g is an element of finite order in GL(ℝ^{n}). □

Corollary 2.3. For any G-equvariant polytope bundle B → Q, the group G acts on the convex set ∫_{Q} B.

Furthermore, one has

(2.1)

(∫_{Q} B)^{G} := (∫_{Q} B) ∩ (ℝ^{n})^{G}

= π_{G} (∫_{Q} B)

= {∫_{Q} γ : G-equivariant, measurable sections γ} ,

Proof. Proposition 2.2 implies the first assertion.

For the second equality in (2.1), we claim more generally that

C ∩ (ℝ^{n})G = π_{G}(C)

for any convex G-invariant subset C ⊂ ℝ^{n}. To see this, note that the left-hand side is contained in the right because of idempotence of π_{G}. The right-hand side is obviously contained in (ℝ^{n})^{G}. It also lies in C since for any x in C, the convex combination π_{G}(x) = \frac{1}{|G|} ∑_{g∈G} g(x) will also lie in C.

For the third equality in (2.1), note that the right-hand side is contained in the left since the integral ∫_{Q} γ of any G-equivariant section will be a G-invariant point of ℝ^{n} by Proposition 2.2. Conversely, a typical point on the left-hand side is ∫_{Q} γ where γ is a section such that g(∫_{Q} γ) = ∫_{Q} γ for all g ∈ G, and one can check using Proposition 2.2 that the G-equivariant section π_{G}γ has the same integral:

∫_{Q} π_{G}γ = \frac{1}{|G|} ∑_{g∈G} ∫_{Q} gγ

= \frac{1}{|G|} ∑_{g∈G} ∫_{Q} γ)

= ∫_{Q} γ

□

We wish to interpret faces of (∫_{Q} B)^{G} in terms of face bundles. Recall that a face bundle F → Q of B → Q is a polytope bundle in which F_{x} is a face of B_{x} for every x in Q. A coherent face bundle of B → Q is one of the form B^{ψ} → Q having B_{x}^{ψ} := (B_{x})^{ψ}, where ψ ∈ ℝ^{n∗} is any linear functional and P^{ψ} denotes the face of P on which the functional ψ is maximized.

When B → Q is G-equivariant, the G-action on bundles restricts to a G-action on face bundles, and as before, a face bundle is G-equivariant if and only if it is invariant under the G-action. The next proposition points out the compatibility between the G-action on face bundles and the G-action on functionals. Proposition 2.4. For any G-equivariant polytope bundle B → Q and any functional g in ℝ^{n∗},

B^{gψ} = g(B^{ψ}).

Consequently, B^{ψ} is a G-equivariant (coherent) face bundle if and only if B^{ψ} = B^{π_{G}ψ}.

Proof. For the first assertion, we compute

g(B^{ψ})_{x} := g(B_{g^{−1}x}^{ψ})
= g({y ∈ B_{g^{−1}x} : ψ(y) is maximized})
= {y′ ∈ gB_{g^{−1}x} : ψ(g^{−1}y′) is maximized})
= {y′ ∈ B_{x} : g(ψ)(y′) is maximized})
= B_{x}^{gψ}.

For the second, note that

B^{ψ} is G-equivariant ⇔ g(B^{ψ}) = B^{ψ} ∀g ∈ G
⇔ B_{x}^{gψ} = B_{x}^{ψ} ∀g ∈ G, x ∈ Q
⇔ B_{x}^{π_{G}ψ} = B_{x}^{ψ} ∀x ∈ Q

where the last equality uses the fact that if for every g in G the functional gψ maximizes on the same face of the polytope B_{x}, then the convex combination π_{G}ψ will also maximize on this face. □

We recall also these key results from [1]. Proposition 2.5. [1, Prop. 1.2]. The Minkowski integral commutes with taking faces (face bundles) in the following sense

(∫_{Q} B)^{ψ} = ∫_{Q} B^{ψ} ∀ψ ∈ ℝ^{n∗}. □

Theorem 2.6. [1, Thm. 1.3, Cor. 1.4] If B → Q is piecewise-linear, then ∫_{Q} B is a convex polytope. Furthermore, the map B^{ψ} ↦ ∫_{Q} B^{ψ} induces an isomorphism from its face lattice to the poset of coherent face bundles of B → Q ordered by inclusion. □

Here is the equivariant generalization. Theorem 2.7. Let B → Q be any G-equivariant piecewise-linear poly-

tope bundle. Then (∫_{Q} B)^{G} is a convex polytope whose face lattice is isomorphic to the poset of G-equivariant coherent face bundles of B → Q ordered by inclusion.

Proof. We use the following well-known fact about face lattices of affine images of polytopes:

Lemma 2.8. [1, Lemma 2.2] For any affine surjection of polytopes P̂ →^{f} P, the map sending a face F of P to the face f^{−1}(F) of P̂ embeds the face lattice of P as the subposet of faces of P̂ of the form P^{ψ∘f} for some ψ in ℝ^{n∗}. □

Applying this lemma to the surjection ∫_{Q} B →^{π_{g}} (∫_{Q} B)^{G}, we conclude that (∫_{Q} B)^{G} has face poset isomorphic to the subposet of faces of ∫_{Q} B consisting of all faces of the form

(∫_{Q} B)^{ψ∘π_{G}} for ψ ∈ ℝ^{n∗}

= (∫_{Q} B)^{π_{G}ψ} for ψ ∈ ℝ^{n∗}
= ∫_{Q} B^{π_{G}ψ} for ψ ∈ ℝ^{n∗}

where the last equality uses Proposition 2.5. By Proposition 2.4, the set of faces ∫_{Q} B^{π_{G}ψ} of ∫_{Q} B for ψ ∈ ℝ^{n∗} is exactly the same as the subset of faces ∫_{Q} B^{ψ} for ψ ∈ ℝ^{n∗} with B^{ψ} → Q being G-equivariant. By Theorem 2.6, the inclusion order on these faces is the same as the inclusion order on the set of G-equivariant coherent face bundles of B → Q. □

2.2. Equivariant fiber polytopes. We apply Theorem 2.7 to the situation of a G-equivariant projection of polytopes.

Let P →^{π} Q be a linear surjection of convex polytopes, with

\begin{matrix}P ⊂ ℝ^{n}, dim(P) = n \\ Q ⊂ ℝ^{d}, dim(Q) = n \end{matrix}

Recall from [1] that this gives rise to a polytope bundle B → Q via x ↦ B_{x} := π^{−1}(x), and in this setting, the fiber polytope defined by

Σ(P →^{π} Q) := ∫_{Q} B.

is a full (n − d)-dimensional polytope living in the fiber ker π of the map π over the centroid of Q.

For the equivariant set-up, we further assume that G is a finite group with linear G-actions on ℝ^{n} and ℝ^{d} which have G acting as symmetries of P, Q, and also that π is G-equivariant: g(π(y)) = π(g(y)) for all y ∈ ℝ^{n}. In particular, this implies that P, Q both have centroids at the origin. It is then easy to check that B → Q defined as above is G-equivariant. Definition 2.9. Define the equivariant fiber polytope by

Σ^{G}(P →^{π} Q) := \frac{1}{vol(Q)} (∫_{Q} B)^{G} = π_{G}Σ(P →^{π} Q).

Theorem 2.10. The equivariant fiber polytope Σ^{G}(P →^{π} Q) is a fulldimensional polytope inside dim ker(π) ∩ (ℝ^{n})^{G}, and therefore has the same dimension as this space, namely

dim(ℝ^{n})^{G} − dim(ℝ^{d})^{G}
(= dim P^{G} − dim Q^{G}).

Its face lattice is isomorphic to the poset of all G-equivariant π-coherent subdivisions of Q ordered by refinement.

Proof. If R is any full-dimensional polytope in ℝ^{r} containing the origin in its interior, then its intersection R ∩ V with any linear subspace V has dim(R ∩ V) = dim V. Since Σ^{G}(P →^{π} Q) = Σ(P →^{π} Q) ∩ (ℝ^{n})^{G}, this proves the first assertion.

To see that dim ker(π) ∩ (ℝ^{n})^{G} = dim(ℝ^{n})^{G} − dim(ℝ^{d})^{G}, note that

(ℝ^{n})^{G}/(ker(π) ∩ (ℝ^{n})^{G}) ≅ (ℝ^{d})^{G}

since G-equivariance of π implies that the surjection ℝ^{n} →^{π} ℝ^{d} restricts to a surjection (ℝ^{n})^{G} →^{π} (ℝ^{d})^{G}.

The last assertion comes from the interpretation of coherent face bundles of B → Q as π-coherent subdivisions, just as in [1, Thm 1.3].

□

Recall that the fiber polytope Σ(P →^{π} Q) has an expression [1, Thm 1.5] as a finite Minkowski sum

Σ(P →^{π} Q) = ∑_{i} \frac{vol(σ_{i})}{vol(Q)}π^{−1}(x_{i}).

where the x_{i} are the centroids of the chambers (maximal cells) σ_{i} in the cell decomposition of Q induced by the projection of faces of P. From this one immediately deduces a similar expression for Σ^{G}(P →^{π} Q) by applying the averaging operator symmetrizer π_{G}:

Σ^{G}(P →^{π} Q) = ∑_{i} \frac{vol(σ_{i})}{vol(Q)}π_{G}(π^{−1}(x_{i}))

Similarly, one can obtain a (redundant) set of vertex coordinates for Σ^{G}(P →^{π} Q) by applying π_{G} to the vertex coordinates for Σ(P →^{π} Q) given in [1, Cor 2.6]. On the other hand, identifying an irredundant subset of these vertices is not so simple. One might expect that vertices of Σ^{G}(P →^{π} Q) correspond to tight G-invariant π-coherent subdivisions (see [1, §2] for the definition of tightness). However, Example 3.1 below shows that this is not the case. Rather, vertices of Σ^{G}(P →^{π} Q) correspond to G-invariant π-coherent subdivisions satisfying the weaker condition that they cannot be further refined while retaining both Ginvariance and π-coherence.

2.3. Equivariant secondary polytopes. We specialization Theorem 2.10 to the situation where P is an (n − 1)-dimensional simplex.

Let A := {a_{1}, …, a_{n}} be the images of the vertices of P under the map π, so that Q = π(P) is the convex hull of the point set A, a d-dimensional polytope in ℝ^{d}. Note that not every point in A need be a vertex of Q, but we assume that the group G of symmetries acting linearly on ℝ^{d} not only preserves Q, but also the set A, i.e. gA = A for all g ∈ G. There is a well-defined notion of a polytopal subdivision of A, and when such subdivisions are coherent (or regular); see [1, §1], [7, Chap. 7]. Say that such a subdivision is G-invariant if G permutes the polytopal cells occurring in the subdivision, taking into account the labelling of cells by elements of A.

We may assume without loss of generality (e.g. by choosing P to be a regular (n − 1)-simplex, that there is a linear G-action on ℝ^{n−1} which permutes the vertices of P in the same way that G permutes A. In this setting, define the equivariant secondary polytope

Σ^{G}(A) := Σ^{G}(P →^{π} Q).

Let A/G denote the set of G-orbits of points in A. Corollary 2.11. Σ^{G}(A) is an (|A/G| − dim(ℝ^{d})^{G} − 1)-dimensional polytope, whose face lattice is isomorphic to the poset of all G-invariant coherent polytopal subdivisions of Q ordered by refinement.

Proof. Immediate from Theorem 2.10, once one notes that

dim(ℝ^{n−1})^{G} = |A/G| − 1

Figure 2. Equivariant secondary polytopes for subgroups G of the dihedral group D_{6} acting on the point configuration A shown in (a).

(b) G = 1. (c) G = C_{2}. (d) G = C_{3} or D_{6}.

and that G-invariance and coherence of a polytopal subdivision correspond to G-equivariance and π-coherence with respect to the map

P →^{π} Q. □

3. Small, visualizable examples

3.1. The standard example. There is a classic example of a configuration A of 6 points in the plane ℝ^{2}, depicted at the top of Figure 3.1(a), which has up to two incoherent triangulations (shown below it), depending on the exact coordinates of its 6 points. If we choose coordinates so that A has the dihedral group D_{6} as symmetries, then both of the triangulations shown in Figure 3.1 (a) are incoherent, and hence do not correspond to vertices of the secondary polytope Σ(A) := Σ^{1}(A) depicted in (b) of the same figure. The only non-trivial proper subgroups of D_{6} up to conjugacy are C_{2} generated by a reflection symmetry, and C_{3} generated by a three-fold rotation. Figures 3.1(c), (d) respectively depict as slices of Σ(A) the equivariant secondary polytopes Σ^{C_{2}}(A) (a pentagon) and Σ^{C_{3}}(A)(= Σ^{D_{6}}(A) (a line segment) respectively. In both cases, the G-invariant coherent triangulations labelling their vertices are shown.

If instead we slightly perturb the coordinates of the three interior points of A, so that the D_{6}-symmetry is destroyed, but still maintaining the C_{3}-symmetry, then something interesting happens in both Σ(A) and Σ^{C_{3}}(A). One of the two incoherent triangulations depicted in Figure 3.1 (a) becomes coherent, and corresponds to a vertex which subdivides the “front” hexagon of Σ(A) in (b) into 3 quadrangles. This new vertex also lies on the 1-dimensional slice Σ^{C_{3}}(A), replacing one of its old endpoints.

Note that in Figure 3.1, some of the subdivisions labelling the vertices of Σ^{G}(A) are not triangulations, that is, they are not tight πcoherent subdivisions of Q.

3.2. Triangulations of a regular hexagon. Consider the vertex set A of a regular hexagon. Its symmetry group is the dihedral group

D_{12} = ⟨s, r : s^{2} = r^{3} = 1, srs = r^{−1}⟩

where s is any reflection symmetry, and r is a rotation through \frac{π}{3}. In what follows, we will assume for the sake of definiteness that s is chosen in the conjugacy class of reflections whose reflection line passes through two vertices of the hexagon.

A list of representatives of the subgroups G of D_{12} up to conjugacy is given in the table below, along with the calculation of the dimension of the equivariant secondary polytope Σ^{G}(A) in each case.

G  dim(ℝ^{n})^{G} dim(ℝ^{d})^{G}  dim Σ^{G}(A)
(= |A/G| − 1)  (= dim(ℝ^{n})^{G} − dim(ℝ^{d})^{G})
1  5  2  3
⟨s⟩  3  1  2
⟨r^{3}⟩  2  0  2
⟨sr⟩  2  1  1
⟨r^{2}⟩  1  0  1
⟨r⟩  0  0  0
⟨s, r^{3}⟩  1  1  0
⟨s, r⟩(= D_{12})  0  0  0

Figure 3. Equivariant secondary polytopes Σ^{G}(A) for subgroups G of the dihedral group D_{12} acting on the set A of vertices of a regular hexagon.

(a) G = ⟨s⟩. (b) G = ⟨sr⟩. (c) G = ⟨r^{2}⟩.

Depictions of these Σ^{G}(A) as a slice of the 3-dimensional associahedron, in all the non-trivial cases where it has dimension at least 1, appear in Figures 1 and 3.2.

4. Application examples.

4.1. Cyclohedra and associahedra. The case G = ⟨r^{3}⟩ in the previous example was discussed in the Introduction, and is a special case of a new construction for the cyclohedron.

The cyclohedron was introduced by Bott and Taubes [4], rediscovered independently and called the type B associahedron by Simion [15], and has been studied by several other authors [5, 6, 12]. The n-dimensonal cyclohedron can be thought of as the unique regular cell complex whose faces are indexed by centrally symmetric subdivisions of a centrally symmetric 2n-gon. A proof that this cell complex is realized by a convex polytope appears in [12] and in [15, §2], and proceeds by a sequence of shavings (or blow-ups) of faces of an n-simplex, similar to the construction of the associahedron in [11].

Simion provided one of the original motivations for our work by asking whether a polytopal realization could be given along the lines of the fiber polytope construction. An answer is that it can be achieved as the equivariant secondary polytope Σ^{C_{2}}(A), where A is the set of vertices of a centrally-symmetric 2n-gon, on which C_{2} acts antipodally. The only issue is whether every centrally-symmetric subdivision of such a 2n-gon is actually coherent, but it is easy to verify this holds.

It turns out that all equivariant secondary polytopes for a regular polygon are either associahedra or cyclohedra. Proposition 4.1. Let A be the vertex set of a regular n-gon, and G a non-trivial subgroup of its the dihedral symmetry group D_{2n}.

Then the combinatorial type of the equivariant secondary polytope Σ^{G}(A) is either that of an associahedron or cyclohedron, depending upon whether G contains reflections or not (that is, whether G is dihedral or cyclic).

Proof. Assume G contains some reflections, so G ≅ D_{2m} for some m dividing n. Choose a fundamental domain for the action of G on the regular n-gon Q_{n} consisting of a sector between two adjacent reflection lines. Label the vertices in A which lie in this (closed) sector consecutively as v_{1}, …, v_{r} (here r is approximately \frac{n}{2m}, but its exact value depends upon which conjugacy classes of reflections in D_{2m} are represented among the reflections in G).

The assertion then follows from the claim that there is an isomorphism between the poset of G-invariant polygonal subdivisions of Q_{n} and the poset of all polygonal subdivisions of an (r + 1)-gon Q_{r+1} labelled with vertices w_{1}, w_{2}, w_{3}, …, w_{r}, w: the isomorphism sends a G-invariant subdivision σ of Q_{n} to the unique subdivision τ of Q_{r+1} having an edge connecting w_{i}, w_{j} if and only if v_{i}, v_{j} are connected by an edge in in σ, and with an edge between w_{i}, w if and only if σ has v_{i} connected by an edge to some vertex of A outside the fundamental sector. The fact that this map is a bijection requires some straightforward geometric argumentation, which we omit. However, once one knows that it is a bijection, it is easy to see that both it and its inverse are order-preserving, since the refinement partial order on subdivisions of a polygon can be defined by the inclusion ordering of their edge sets.

Now assume G contains only rotations, so G ≅ C_{m} for some m dividing n, and let k = \frac{n}{m}. Label the vertices of Q_{n} consecutively in m groups of size k by

1_{1}, 2_{1}, …, k_{1}, 1_{2}, 2_{2}, …, k_{2}, … 1_{m}, 2_{m}, …, k_{m}.

Note that any C_{m}-invariant subdivision of Q_{n} is completely determined by the set of interior edges connecting vertices in the first two groups 1_{1}, 2_{1}, …, k_{1}, 1_{2}, 2_{2}, …, k_{2}. This leads to an isomorphism between the poset of G-invariant polygonal subdivisions of Q_{n} and the poset of centrally symmetric polygonal subdivisions of a centrally symmetric 2kgon Q_{2k}: label the vertices of Q_{2k} using the same scheme, and send a Ginvariant subdivision σ of Q_{n} to the unique subdivision τ of Q_{2k} whose interior diagonals have exactly the same endpoint labels as the interior diagonals of σ involving vertices in the first two groups in Q_{2n}. Again we omit the straightforward geometric details involved in checking that this is a bijection. □

4.2. The type B permutohedron. Given any finite reflection group W, form the zonotope which is the Minkowski sum of any collection of line segments which contains exactly one line segment perpendicular to each of the reflecting hyperplanes for a reflection in W. Call this zonotope the W -permutohedron. It is known that the vertices of this zonotope are indexed by the elements of W, and its 1-skeleton is isomorphic to the (undirected) Cayley graph for W with respect to a natural set of Coxeter generators. Explicit descriptions of the facial structure of W -permutohedra when W is one of the classical reflection groups of type A, B(= C), or D may be found in [13].

In the case where W = A_{n−1} is the symmetric group on n letters, the A_{n−1}-permutohedron is usually known simply as the permutohedron. It can be constructed [1, Example 5.4] as the equivariant fiber polytope Σ(P →^{π} Q) where P = [0, 1]^{n} is the unit n-cube, π : ℝ^{n} → ℝ^{1} is the linear map sending e_{i} ↦ 1 for each standard basis vector e_{i}, and Q is the line segment [0, n] = π(P). This is a special case of a monotone path polytope [1, §5]: the vertices correspond to edge paths in the ncube P which are monotone with respect to the functional π. In this case there is an obvious bijection between such paths and permutations of {1, 2 …, n}; one simply reads off the parallelism class of the edges in the edge paths.

In the case where W = B_{n}, something similar works using the equivariant fiber polytope construction. Let P be the unit 2n-cube in ℝ^{2n} with standard basis vectors labelled {e_{+i}, e_{−i} : i = 1, 2 …, n}. Consider the linear map π : ℝ^{2n} → ℝ^{1} sending e_{±i} ↦ ±1, and let Q = π(P) = [−n, n]. Let the generator of the group C_{2} of order 2 act on ℝ^{2n} by swapping e_{+i}, e_{−i}, and let it act on ℝ^{1} by −1. Then C_{2} acts as symmetries of both P, Q, and the map π is C_{2}-equivariant. It is then straightforward to check that the equivariant fiber polytope Σ^{C_{2}}(P →^{π} Q) is combinatorially isomorphic to the B_{n}-permutohedron. Its vertices correspond to the C_{2}-invariant monotone edge paths in the 2n-cube P, which biject with signed permutations again by reading off the parallelism class of the edges in the edge path.

4.3. Maps from the type B permutohedron to the cyclohedron. There is a well-known set-map from the symmetric group S_{n+1} to triangulations of a convex (n + 2)-gon, or to equivalent objects such as binary trees - see [17], [3, §9], [16, §1.3]. This map has several pleasant properties, including the fact that it extends to a map from faces of the A_{n}-permutohedron to faces of the n-dimensional associahedron. Simion [15, §4.2] asked whether there is an analogous map between the B_{n}-permutohedron and n-dimensional cyclohedron.

In fact, there is a whole family of such maps. To explain this, we first further explicate [3, Remark 9.14] on how to view the map in type A as a consequence of some theory of iterated fiber polytopes [2].

Given any tower P →^{π} Q →^{ρ} R of linear surjections of polytopes, it turns out that π restricts to a surjection Σ(P →^{ρ∘π} R) →^{π} Σ(Q →^{ρ} R) and so one can form the iterated fiber polytope

Σ(P →^{π} Q →^{ρ} R) := Σ (Σ(P →^{ρ∘π} R) →^{π} Σ(Q →^{ρ} R)) .

Both Σ(P →^{π} Q →^{ρ} R) and Σ(P →^{π} Q) live in the vector space ker(π), and [2, Theorem 2.1] says that the normal fan of Σ(P →^{π} Q →^{ρ} R) refines that of Σ(P →^{π} Q) (or equivalently, the latter is a Minkowski summand of the former). This implies the existence of an order-preserving map from faces of Σ(P →^{π} Q →^{ρ} R) to faces of Σ(P →^{π} Q), corresponding to the map on their normal cones which sends a cone in the finer fan to the unique cone containing it in the coarser fan.

We apply this to the tower of projections

Δ^{n+1} →^{π} Q_{n+2} →^{ρ} I

in which Δ^{n+1} is an (n + 1)-dimensional simplex whose vertices map canonically to the vertices of a convex (n + 2)-gon Q_{n+2}, which then projects onto a 1-dimensional interval I. In [2, §4] it is shown that Σ(Δ^{n+1} →^{ρ∘π} I) and Σ(Δ^{n+1} →^{π} Q_{n+2} →^{ρ} I), are combinatorially isomorphic (but not affinely equivalent) to the n-cube and to the A_{n−1}- permutohedron, respectively. Since Σ(Δ^{n+1} →^{π} Q_{n+2}) is the (n − 1)- dimensional associahedron, in this case the above general theory gives a map from the faces of the permutohedron to the faces of the associahedron, which can be checked to coincide with the usual one.

Now suppose we instead apply this theory to the following tower of C_{2}-equivariant projections

(4.1)  Δ^{2n+1} →^{π} Q_{2n+2} →^{ρ} I

in which Q_{2n+2} is a centrally-symmetric (2n+2)-gon, Δ^{2n+1} is a (2n+1)- dimensional (regular) simplex, and I is an interval. We assume that the vertices of Q_{2n+2} are labelled in cyclic order as

+1, +2, …, +(n + 1), −1, −2, …, −(n + 1)

and that the C_{2}-actions on Δ^{2n+1}, Q_{2n+2}, I are chosen so that the projections are equivariant, i.e. C_{2} swaps the two vertices of I, and exchanges the pairs of vertices of Δ^{2n+1} which map to the vertices labelled +i, −i of Q_{2n+2}. We further assume that the map ρ is generic in the sense that it takes on distinct values on the different vertices of Q_{2n+2}, and hence gives a linear ordering of these vertices, which we will assume orders the vertices labelled −(n+1), +(n+1) first and last, respectively. The map we eventually define will depend on this ordering.

Note that Σ(Δ^{2n+1} →^{ρ∘π} I) will still be a combinatorial 2n-cube, and by Corollary 2.3, it will carry a C_{2}-action that makes the map π onto the interval Σ(Q^{2n+2} →^{ρ} I) equivariant. We still have from [2, §4], that the iterated fiber polytope Σ(Δ^{2n+1} →^{π} Q_{2n+2} →^{ρ} I) is combinatorially an A_{2n−1}-permutohedron, and by Corollary 2.3 will carry a C_{2}-action. With some work, for which we omit the details, one can check that the C_{2}-action on faces corresponds to the same C_{2}-action as in Example 4.2. Hence C_{2}-invariant faces under this action are identified with the faces of the B_{n}-permutohedron, so that the C_{2}-invariant subpolytope Σ^{C_{2}}(Δ^{2n+1} →^{π} Q_{2n+2} →^{ρ} I) is combinatorially isomorphic to the B_{n}-permutohedron.

Figure 4. (a) The tower of projections (4.1) for n = 2 (the 5-simplex Δ^{5} is shown only in a 2-dimensional projection). (b) One of the 4(= 2^{2}) maps from vertices of the B_{2}-permutohedron to vertices of the 2-dimensional cyclohedron. The B_{2}-permutohedron is shown with vertices labelled both by a signed permutation and by the centrally-symmetric hexagon triangulation which is their image under the map.

On the other hand, Σ^{C_{2}}(Δ^{2n+1} →^{π} Q_{2n+2}) is the n-dimensional cyclohedron, by Example 4.1. Since the normal fan of Σ^{G}(P →^{π} Q →^{ρ} R) refines that of Σ^{G}(P →^{π} Q) (by restricting this refinement of fans from the non-equivariant setting to the invariant subspace (ℝ^{n})^{G}), we obtain the existence of an order-preserving map between their face lattices as desired.

To be explicit about this map and its dependence on the ordering of the vertices of Q_{2n+2} by ρ, it suffices to describe its effect on vertices. A vertex of the n-dimensional permutohedron is indexed by a signed permutation, that is a sequence w = w_{1}w_{2} … w_{n} where w_{i} ∈ {±1, …, ±n} containing exactly one value from each pair ±i. To obtain a centrallysymmetric triangulation of Q_{2n+2} from w, we associate to w a sequence of 2n + 1 polygonal paths γ_{0}, γ_{1}, …, γ_{2n} visiting only vertices of Q_{2n+2}, and let the triangulation be the one whose edges are the union of these paths. Each γ_{i} is a section of the map Q_{2n+2} →^{ρ} I, and hence completely specified by the set of vertices of Q_{2n+2} it visits (although this implicitly requires knowledge of the fixed ordering of vertices of Q_{2n+2} by ρ). Set γ_{0} to be the path visiting vertices −(n + 1), +1, +2, …, +(n + 1), that is, γ_{0} is half of the boundary of the polygon Q_{2n+2}. Then inductively define γ_{i} to be the unique path obtained from γ_{i−1} by reading the i^{th} value in the sequence ŵ := w_{1}w_{2} … w_{n} − w_{n} … − w_{2} − w_{1} and either removing this value from the list of visited vertices when it is positive, or adding it when it is negative. Note that the palindromic nature of ŵ insures that the associated triangulation is centrally symmetric.

How many maps have we defined in this way? The map depends only the ordering of the vertices of Q_{2n+2} by ρ. Any such ordering starts and ends with −(n + 1), +(n + 1), and in between is a shuffle of the usual integer order on the positive vertices +1, …, +n with the usual order on the negative vertices. Since Q_{2n+2} is centrally-symmetric and ρ is linear, the order is determined by knowing its first half. Hence it can be parametrized by the set S ⊂ {1, 2, …, n} giving the positions in the first half of the order where the negative vertices occur. This means there are 2^{n} such maps.

5. Remarks/Questions

Remark 5.1. One might expect a relation between

\begin{matrix}Σ(P^{G} →^{π} Q^{G}) \\ Σ^{G}(P →^{π} Q) \end{matrix}

since both are full-dimensional polytopes embedded in the subspace (ℝ^{n})^{G} ∩ ker π. The case G = C_{2} in Example 3.1 already shows that they are not isomorphic: here Σ(P^{G} →^{π} Q^{G}) = P^{G} is a triangle, while Σ^{G}(P →^{π} Q) is a pentagon.

Neither is there an inclusion in either direction, as illustrated by the following example. Let P →^{π} Q be the canonical projection of a regular 3-simplex onto a square Q, with an equivariant C_{2}-action that reflects the square across one of its diagonals. Label the vertices of P by v_{1}, v_{2}, v_{3}, v_{4} in such a way that the C_{2}-action swaps π(v_{1}), π(v_{2}) and fixes π(v_{3}), π(v_{4}). Then both polytopes in question are 1-dimensional intervals, and one can calculate directly that

\begin{aligned}Σ(P^{G} →^{π} Q^{G}) & = [\frac{1}{3}x + \frac{2}{3}y, \frac{2}{3}x + \frac{1}{3}y] \\ Σ^{G}(P →^{π} Q) & = [0 · x + 1 · y, \frac{1}{2}x + \frac{1}{2}y] (= Σ(P →^{π} Q)) \end{aligned}

where x = \frac{v_{1}+v_{2}}{2} , y = \frac{v_{3}+v_{4}}{2} .

The distinction between the two relates to weighted averages^{1} We know from Corollary 2.3 that Σ^{G}(P →^{π} Q) is the set of all average values of G-equivariant sections γ of P →^{π} Q, while Σ(P^{G} →^{π} Q^{G}) consists of average values of sections γ̄ of P^{G} →^{π} Q^{G}. Using Fubini’s Theorem, one can show that the average value over Q of a G-equivariant section γ is the same as the weighted average value of an appropriately defined section γ̄ of P^{G} →^{π} Q^{G}, obtained by integrating γ over fibers π_{G}^{−1}(x), in which the weight at a point x in Q^{G} is equal to the volume of the fiber π_{G}^{−1}(x). If these fiber volumes are not constant, the weighted average and the average need not coincide.

One might still ask whether there is a relation between their associated normal fans living in ker(π)^{∗G}, e.g. one refining the other so that the one polytope is a Minkowski summand of the other. But as far as we know there is no a priori reason for such a relation. Using the notation of [2], one has that

N Σ^{G}(P →^{π} Q) := N π_{G}Σ(P →^{π} Q)

= N Σ(P →^{π} Q) ∩ im(π_{G}^{∗})

= (proj_{ker(π)^{∗}}N P) ∩ ker(π)^{∗G}

whereas

N Σ(P^{G} →^{π} Q^{G}) := proj_{ker(π)^{∗}}N P^{G}
= proj_{ker(π)^{∗}}N π_{G}P
= proj_{ker(π)^{∗}}(N P ∩ ℝ^{n∗G})

which need not coincide with (proj_{ker(π)^{∗}}N P) ∩ ker(π)^{∗G}.

Remark 5.2. The fiber polytope Σ(P →^{π} Q) has a toric interpretation given by Kapranov, Sturmfels and Zelevinsky [10]. The associated toric variety X_{Σ(P →^{π}Q)} is the Chow quotient X_{P} /T of the toric variety X_{P} by the subtorus T defined by the kernel of π.

One might then expect in the G-equivariant setting that there is a more general interpretation for X_{Σ^{G}(P →^{π}Q)}, perhaps relating it to the G-invariant subvariety (X_{P} /T)^{G} for an induced G-action on X_{P} /T. However, even in the very special case where Q = {0}, so that

\begin{aligned}Σ(P →^{π} Q) & = P \\ Σ^{G}(P →^{π} Q) & = P^{G} \\ X_{P} /T & = X_{P} \end{aligned}

1Thanks to John Baxter for an enlightening conversation in this regard.

the general relation between the G-invariant subvariety X_{P}^{G} and the toric variety X_{P^{G}} seems not to be trivial- see [8, Theorem 2] for a special case. We leave the problem of interpretating Σ^{G}(P →^{π} Q) torically to the real experts. Remark 5.3. Fomin and Zelevinsky [6] recently introduced a family of simplicial spheres associated to each finite (crystallographic) root system, whose facial structure coincides with the associahedron in type A and with the cyclohedron in type B. They conjecture [6, Conj. 1.13] that their spheres have the same face lattice as some convex polytope in general. One might hope that their face lattice is realized by some equivariant fiber polytope, as it is in the case of types A and B. However we do not see how to do this for their spheres in the case of type D, whose 1-skeleton is described in [6, Prop. 3.16]. Remark 5.4. In type A, the 1-skeleton of the permutohedron and associahedron each have an acyclic orientation making them the Hasse diagrams for the weak Bruhat order on S_{n} and the Tamari lattice, respectively. Both of these partial orders are self-dual lattices, and the map betwen them mentioned in Section 4.3 enjoys some very pleasant properties [3, §9].

There is a similar acyclic orientation for the 1-skeleton of the type B permutohedron, and Simion [15, §4.1] asked whether there are corresponding well-behaved acyclic orientations and partial orders for the 1-skeleton of the cyclohedron. She proposed two such orders, one of which is self-dual and has some nice properties explored in [14], but neither of which is a lattice.

Because the maps introduced in Section 4.3 are surjective, they can be used to transfer the acyclic orientation from the 1-skeleton of the type B permutohedron to an orientation of the 1-skeleton of the cyclohedron, which may or may not be acyclic. Do any of these induced orientations end up being acyclic, and are their partial orders wellbehaved in any sense? Remark 5.5. It was pointed out in the proof of Proposition 2.3 that whenever a finite group G acts linearly on a convex polytope P, there is induced a linear surjection P →^{π_{G}} P^{G}. Does the “coinvariant polytope” Σ(P →^{π_{G}} P^{G}) enjoy any nice properties or interpretations?

Acknowledgements

The author thanks Mike Matsko for helpful comments, and Nirit Sandman for making available her work [14].

References

[1] L.J. Billera and B. Sturmfels, Fiber polytopes, Ann. of Math. 135 (1992), 527–549.

[2] L.J. Billera and B. Sturmfels, Iterated fiber polytopes, Mathematika, 41 (1994), 348–363.

[3] A. Björner and M. Wachs, Shellable nonpure complexes and posets, II, Trans. Amer. Math. Soc. 349 (1997), 3945–3975.

[4] R. Bott, C. Taubes, On the self-linking of knots, Topology and physics J. Math. Phys. 35 (1994), 5247–5287.

[5] S. Devadoss, A space of cyclohedra, preprint 2001.

[6] S.V. Fomin and A.V. Zelevinsky, Y-systems and generalized associahedra, preprint 2001, Los Alamos archive hep-th/0111053.

[7] I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications. Birkhäuser Boston, Inc., Boston, MA, 1994.

[8] H.A. Jorge, Smith-type inequalities for a polytope with a solvable group of symmetries, Adv. Math. 152 (2000), 134–158.

[9] M.M. Kapranov and M. Saito, Hidden Stasheff polytopes in algebraic K-theory and in the space of Morse functions, Higher homotopy structures in topology and mathematical physics (Poughkeepsie, NY, 1996), 191–225, Contemp. Math. 227, Amer. Math. Soc., Providence, RI, 1999.

[10] M.M. Kapranov, B. Sturmfels, and A.V. Zelevinsky, Quotients of toric varieties, Math. Ann. 290 (1991), 643–655.

[11] C.W. Lee, The associahedron and triangulations of the n-gon. European J. Combin. 10 (1989), 551–560.

[12] M. Markl, Martin, Simplex, associahedron, and cyclohedron, in “Higher homotopy structures in topology and mathematical physics” (Poughkeepsie, NY, 1996) Contemp. Math. 227, 235-265 Amer. Math. Soc., Providence, RI, 1999.

[13] V. Reiner and G.M. Ziegler, Coxeter-associahedra, Mathematika 41 (1994), 364–393.

[14] N. Sandman, Honors Senior Thesis, George Washington University, 2000.

[15] R. Simion, A type B associahedron, Adv. Applied Math., to appear.

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

[17] A. Tonks, Relating the associahedron and the permutohedron. “Operads: Proceedings of Renaissance Conferences” (Hartford, CT/Luminy, 1995), 33–36, Contemp. Math. 202, Amer. Math. Soc., Providence, RI, 1997.

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

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