Combinatorics of Polyhedra for n-Categories

Todd Trimble

September 5, 1999

This is part A of a long email from Todd Trimble; part B is here. Both parts have been nicely LaTeXed by Samuel Vidal: and the LaTeX files are here.

In these notes, we give some combinatorial techniques for constructing 
various polyhedra which appear to be intimately connected with the 
geometry of weak n-categories. These include 

1. Associahedra (and "monoidahedra"; see below); 
2. Permutoassociahedra, and the cellular structure of 
   Fulton-MacPherson compactifications of moduli spaces 
3. "Functoriahedra" (related to the A_n maps of Stasheff) 

Our basic techniques use derivations on operads and bar constructions. 
In part A, we introduce derivations, which should be regarded as 
"boundary operators" on (set-valued) operads satisfying a Leibniz rule. 
Such derivations can be used to construct poset-valued operads; taking 
nerves, one gets polyhedral operads. In this way we reconstruct the 
associahedra and the Fulton-MacPherson compactifications. 

A. Derivations on operads. 

Sections A.1. and A.2. preface the main definitions which begin in 
section A.3: they establish notation and terminology and categorical 
formalizations of fairly trivial facts. The reader may wish to skip 
them or refer back to them as necessary. 

Initially, we work with set-valued non-permutative operads M, which may 
be viewed as models of a multisorted algebraic theory with operations 
sub_k: M_{p} x M_{q} --> M_{p+q-1}. (This is the appropriate presentation 
when working with *non-unital* operads.) The sorts in this case are 
parametrized by natural numbers p, so that we have for each operad M 
an underlying sequence of sets. Such a sequence may be regarded as a 
functor N --> Set on the discrete category N of natural numbers. 

When working with permutative operads, it is often convenient to work 
with functors on the category of finite sets and bijections, rather 
than with functors on the permutation category (which is a skeleton). 
(Logically it makes no difference, but some things are clearer and 
easier to describe in the former setting.) There are analogues of the 
sub_{k} operations, parametrized by pairs (S, E) where S is a finite 
set and E is a subset. Let S/E denote the (pointed) set in which all 
of the points of E are identified with a basepoint; if E is empty then 
S/E is the disjoint sum of S with a basepoint. Then there is a 
substitution map 
                 sub_{S, E}: M(S/E) x M(E) --> M(S). 

Throughout these notes, we work in a setting which can be adapted to 
both non-permutative and permutative operads. 

The functor category [N, Set] is a Boolean topos. In this case, this 
means that the power object of a sequence is the sequence of power sets. 
We let P: [N, Set] --> [N, Set] denote the covariant power object 
functor. Thus if f: X --> Y is a morphism (= sequence of functions), 
then Pf: PX --> PY sends a sequence of subsets S_n to the sequence of 
images f_{n}(S_n). 

The functor P carries a structure of monoidal monad. The monoidal 
structure map PA x PB --> P(A x B) sends a pair of subsets to their 
product. The monad unit uX: X --> PX sends a sequence of elements to 
the corresponding sequence of singletons, and the multiplication 
mX: PPX --> PX sends a sequence of subset-collections to the 
corresponding sequence of unions. (It is easily checked that u and 
m are monoidal natural transformations, so we do get a monoidal monad.) 

The algebras of P are sup-lattice objects, i.e., sequences of sup-lattices. 
Using the monoidal monad structure on P, one can produce a closed 
symmetric monoidal structure on P-Alg. There is an underlying functor 
from P-Alg into the category of (idempotent) commutative monoids in 
[N, Set]. 

The morphisms A --> B in the Kleisli category of P are maps A --> PB 
in [N, Set], i.e., relations between A and B. Thus a binary relation 
on A is a Kleisli morphism A --> A, and the hom-object Kl(A, A) of 
binary relations is a monoid P-Alg(PA, PA) in the category of sup-lattices. 
The reflexive transitive closure of a binary relation R on A may be 
defined as the geometric series 1 + R + R^2 + ... in this sup-lattice 
monoid. Of course, this is an incarnation of the free monoid construction, 
although in this case, R* = 1 + R + R^2 + ... gives an idempotent monad T. 
A poset may be defined as an object A together with a T-algebra in 
Kl(A, A). Here it just means a sequence of ordinary posets.  

All of this section carries over to species, braided species, and 
more generally permutation representations of arbitrary groupoids, 
starting from the observation that each of these gives a Boolean topos. 
In fact, the Boolean assumption isn't even needed. 

On [N, Set], we have a substitution tensor product whose monoids 
are non-permutative operads. If X is a sequence of sets, we let 
OX denote the sequence underlying the free operad on X. 

Using the monoidal structure on the covariant power set functor P, 
each operad M induces an operad structure on PM. Thus we have for 
example an operad POX. It is very easy to see that the elementhood 
relation e_{M} >--> M x PM defines a suboperad. 

Definition: If A is a set-valued operad, and B an operad valued in 
            commutative monoids, then a derivation d: A --> B is a 
            map in [N, Set] such that 
            d(sub_{k}(a, b)) = sub_{k}(da, b) + sub_{k}(a, db). 

For the remainder of these notes, we take B to be of the form PM, and 
the main examples of derivations take the form M --> PM. Such derivations 
extend uniquely to derivations PM --> PM which preserve arbitrary sups. 

Given a derivation d: M --> PM, it is suggestive to regard the elements m 
of M as "cells", and d(m) as the collection of face-cells lying on the 
boundary of m. The idea is to use (M, d) as combinatorial data to describe 
a polyhedral operad. (It seems that Clemens Berger has a notion of 
"cellular operad", but I don't know his definition, or how it fits 
with the notions given here.) 

Many examples occurring in nature are derivations of the form OX --> POX. 
Notice that derivations of this form correspond bijectively to maps 
X --> POX (much as linear maps V --> A from a vector space V into an 
algebra A correspond bijectively to derivations TV --> A on the tensor 

Example 1: Let X be empty in degrees 0 and 1, and terminal in degrees 
           2 and higher. Then the elements of OX correspond bijectively 
           to (combinatorial) planar rooted trees, in which every vertex 
           adjacent to fewer than two incoming edges must be a leaf. 
           For n>1, the unit map X --> OX sends the element in degree n 
           to the "n-sprout" (no nodes except leaves and root). Let [n] 
           denote the n-sprout. Define X --> POX by sending the element 
           in X_n to the set of all trees in (OX)_n of the form 
           sub_{k}([p], [q]). Extend this uniquely to a derivation  
           d: OX --> POX.

This example is connected with Stasheff's associahedra, as we explain 
in a moment. First, some generalities. 

Each derivation d: M --> PM may be regarded as a binary relation on M. 
Consider its reflexive transitive closure d*, i.e., the poset generated 
by this binary relation, viewed as a map M --> PM, or as a sup-lattice 
map PM --> PM. 

Proposition: d*: PM --> PM is an operad map. 
Proof: We must show that d*(sub_{k}(x, y)) = sub_{k}(d*(x), d*(y)). 
       Being sup-lattice morphisms, the sub_{k} operations distribute 
       over arbitrary sums. Then we calculate, as with ordinary 
       derivations (except that we may drop binomial coefficients, 
       on account of the idempotency of + in PM), 

       d^{n}(sub_{k}(x, y)) = \sum_{p+q=n} sub_{k}(d^{p}(x), d^{q}(y)) 

       and since d* = 1 + d + d^2 + ..., the desired equation 
       follows easily. 

Remark: There is a well-known theorem that if A is a Banach algebra 
        and if d: A --> A is a bounded linear derivation, then 
        exp(d): A --> A is a Banach algebra map. The proposition is 
        analogous: algebra multiplication is replaced by operad 
        substitution maps, the completeness property of the Banach 
        algebra by the sup-lattice property of PM, and exp(d) 
        is replaced by the geometric series d* = 1 + d + d^2 + ... 

Since P is a monoidal monad, the unit uM: M --> PM is an operad morphism, 
and we may compose this with d*: PM --> PM to get an operad map M --> PM, 
again denoted by d*: M --> PM. Now, if we pull back (take the inverse 
image of) the elementhood relation e_{M} --> M x PM along the map 
1 x d*: M x M --> M x PM, we get a suboperad 

                   R --> M x M, 

since this is obtained as a pullback in the category of operads. In 
other words, for each derivation d: M --> PM, we get a poset (M, R) 
in the category of operads, which is the same as an operad in the 
category of posets. 

Definition: Given a derivation d: M --> PM, we denote by M_d the 
            posetal operad whose characteristic map is d*: M --> PM. 

Example 1 (continued): Given planar trees t, t', let us write t' --> t
          if t' belongs to d*(t). Thus --> is a poset relation. From 
          before, we have that t' is contained in d([n]), where [n] is 
          the n-sprout, if t' = sub_{k}([p], [q]), i.e., if t' has exactly 
          one internal edge, and [n] is obtained from t' by contracting that 
          internal edge. In general, t' --> t if t is obtained by 
          contracting a finite number of internal edges of t'. Since 
          contraction of all internal edges results in an n-sprout, we 
          see that the n-th component of the posetal operad (OX)_d 
          has [n] as terminal object, so that its nerve is contractible. 

          With a little work, one can show that the realization of the 
          nerve of each component (OX)_{d}(n) is homeomorphic to an n-disk. 
          Indeed, the nerve gives a natural triangulation of Stasheff's 
          associahedron in dimension n. 

The remainder of part A is devoted to the construction of a polyhedral 
operad which corresponds to a natural triangulation of the Fulton-MacPherson 
compactification of moduli spaces (for R^k). In this case, we need to work 
with permutative operads. We begin by defining a cell structure for the 
moduli space. 

For finite sets S of cardinality greater than 1, we let F_k[S] denote the 
spatial species of injective functions S --> R^k. For S = {1, ..., n}, this 
is usually denoted F_k[n]: the space of configurations of n points in R^k. 
We partition F_k[n] into convex cells by using a kind of lexicographic order 
(in which the j-th coordinate takes priority over the i-th coordinate if 
j > i [not j < i]). For example, (x, y) < (x', y') if y < y' or y=y' and x < x'. 

The points p_1, ..., p_n of a configuration may be rearranged in ascending
lexicographic order: p_{f1} < ... < p_{fn} for some permutation f. (Note: if 
the species F_k is defined on finite sets S, then we get an induced linear 
order on S, not a permutation.) Let us define the type of the configuration 
to be a tuple (f; k_1, ..., k_{n-1}) where f is the permutation and k_j is 
the index of the last coordinate where p_{fj} and p_{f(j+1)} disagree. One 
often uses a "bar notation" for denoting such types, by placing k_j bars 
between f(j) and f(j+1). For example, working with configurations in the 
plane, 2||3|1 is the type of a configuration of three points where points 1 
and 3 lie on the same horizontal line lying above point 2, and point 3 is to 
the left of point 1. It is immediate that the region of configurations of 
common type form a convex cell. Letting T(k, n) denote the set of types, we 
have a typing function F_k[n] --> T(k, n) whose convex fibers partition the 
configuration space. 

Let M_k[n] ("moduli space") denote the orbit space of F_k[n] under the 
action of translations and positive dilatations on R^k. Observe that the 
typing function factors through M_k[n], so that we have an induced typing 
function M_k[n] --> T(k, n). 
Keeping k fixed, we let T_n = T(k, n) for n>1, and take T_0 and T_1 to be 
empty: this gives a species T. We will define a boundary d: T --> POT whose 
induced derivation d: OT --> POT provides data for a posetal operad, whose 
nerve components naturally triangularize the Fulton-MacPherson (or really 
"Axelrod-Singer" for the real case) compactifications. First, a few 
First, it is convenient to view a type in terms of a collection of mutually 
disjoint transitive relations |_{1}, |_{2}, ..., |_{k} on the set of 
indices {1, ..., n}, whose join (in the poset of transitive relations) 
is a linear order f(1) < ... < f(n). Namely, define these |_{j} to be 
the minimal relations such that 
      (1) f(i) |_{j} f(i+1) if there are j bars between f(i) and f(i+1); 
      (2) p |_{i} q and q |_{j} r implies p |_{max(i, j)} r. 
(The reader should consider what this means geometrically.) 
Instances of p |_{i} q shall be called "consequences" of the type. 
The maximum i where p |_{i} q occurs is called the "degree" of the type. 

By (2), and the fact that the transitive join of all the relations |_{i} 
is a linear order on {1, ..., n}, we see that the transitive join of |_{i} 
for i = 1 up to j must be a disjoint sum of linear orders. Each of these 
orders will be called a j-connected component, or j-component for short. 
We may also speak of the j-component of a given element in {1, ..., n}. 

In what follows, we will need certain kinds of "shufflings". Given two 
disjoint j-components A and B in a type, a j-shuffle of them is a shuffle 
on the underlying linear orders, in such a way that a in A is interposed 
between b and b' in B only when b |_{j} b', and b in B is interposed between 
a and a' in A only when a |_{j} a'. Together with all the |_{i} relations on 
A and on B, one adjoins new relations b |_{j} a, a |_{j} b' in the former 
case, and a |_{j} b, b |_{j} a' in the latter. As a special case, we have 
the notion of "intercalating" one j-component within another, where one 
places the entire component B between two successive elements a, c of A. 
Or, if a < b < c are successive elements in A, we get the same thing by 
replacing b by B, and we speak then of intercalating B at b. 

Now let us give rules for describing the boundary operator d: T --> POT. 

Rule (1): If t and t' are two types, let us say t' is in d(t) if 
          t' can be obtained from t as follows: if t has the linear order 
          f(1) < ... < f(n), then there exists i such that f(i) |_{j} f(i+1) 
          in t, and t' is obtained by removing this pair and the set of 
          consequences derived using this pair, followed by (j-1)-shuffling 
          the (j-1)-components of f(i) and f(i+1), and deriving a new set 
          of consequences from the relations which result. 
Rule (2): The remaining elements in d(t) are of the form sub_{E}(t', t''), 
          where E is a subset of S = {1, ..., n}, t belongs to X[S] = X_n, 
          t' to X[S/E], and t'' to X[E] (see section A.1. for the sub_E 
          operations). Such an element belongs to d(t) if the following 
          conditions hold. Let b be the basepoint in S/E, and suppose t' 
          has degree d. Then the type t'' on E should be the same as that 
          obtained by restriction of t-consequences on S to the subset E, 
          and there should exist a list of sets C_1, ..., C_d, nested in 
          ascending order, where each C_j is a j-component in t'' which, 
          when intercalated at b in the j-component of b in t', yields 
          only correct consequences of t. 

The ideas which govern this description are as follows. First, each type 
t represents a convex cell in moduli space, and the boundary of t (in 
the moduli space) should be the set of types whose cells are codimension 
0 parts of the boundary of the cell for t. If p represents a configuration 
moving through the closure of the t-cell, with the points of p ordered 
lexicographically, then p undergoes a type transition when the relation 
between two points p(i) and p(i+1) changes at the j-th coordinate, from 
p(i)_j < p(i+1)_j to p(i)_j = p(i+1)_j. (We are assuming p(i) and p(i+1) 
agree in coordinates with indices greater than j.) After the transition, 
the largest index where p(i) and p(i+1) disagree is at most j-1. And in 
order for p after the transition to be interior to the codimension 0 
stratum of the boundary, that largest index must be equal to j-1. Now we 
take into account the possible ways in which the (j-1)-th coordinates 
differ, while still maintaining the order of points in p, and we are led 
to the first part of the description of the boundary operator. 

As for the second part, the idea is that we are peering into a first-order 
infinitesimal neighborhood of a singular configuration, blowing it up, 
and examining what types of moving non-singular configurations can approach 
the inverse image or blow-up of the singular configuration. Now a singular 
configuration, as a function from a finite set S into R^k, factors through 
a quotient S/~ which maps injectively into R^k; in order to get the 
highest dimensional stratum (of the boundary of a t-cell in the 
Fulton-MacPherson compactification), we restrict to equivalence relations 
on S which merely squash a single subset E down to a point. Then we have 
a non-singular configuration on S/E, so that the singularity is concentrated 
on E; after blowing up, the points of E are then distinguished according 
to tangent directions, thus giving non-singular configurations on E 
in the blow-up. The resulting pairing of a type on S/E with a type on E may 
be viewed as an instance of a formal sub_{E} operation in the operad freely 
generated from the species of types, and the description of how boundaries 
of types intersect these applications of sub_{E} merely reflect properties 
of configuration-types as some of their points become infinitely close. 

As this example of a polyhedral operad is somewhat complicated, it may be 
well to calculate the explicit structure of a few cells. In what follows, 
* denotes the basepoint E/E in a quotient S/E of S. Hence sub(*||3, 1|2) 
indicates the expression obtained by substituting 1|2 for * in *||3. 
Substituted expressions are indicated using a bracket notation, e.g., 
Example 2: The boundary of 1||2 is {1|2, 2|1}, by rule (1), and 1|2, 2|1 
           each have empty boundaries. So the picture is 

                   1|2 ------ 2|1

           and one should think of a braiding c_{x, y}: xy --> yx. 

Example 3: The boundary of 1||[2|3] = sub(1||*, 2|3) is calculated by the 
           Leibniz rule. We get 
           d(1||[2|3]) = sub(d(1||*), 2|3) + sub(1||*, d(2|3)) 
           where the second summand is 0 since 2|3 has empty boundary. 
           From the preceding example, the first summand is 
           sub(1|*, 2|3) + sub(*|1, 2|3) = { 1|[2|3], [2|3]|1 } 
           so the picture becomes 

              1|[2|3] ---------- [2|3]|1

           which is reminiscent of c_{x, yz}: x(yz) --> (yz)x. 

Example 4: To calculate the boundary of 1|2|3, we use rule (2). The 
           only consequences are 1|2, 2|3, and 1|3; and the only ones 
           which occur as intercalated relations are 1|2 and 2|3. 
           Hence the boundary is { [1|2]|3, 1|[2|3] }. The picture is 

                 [1|2]|3 ------- 1|[2|3], 

           reminiscent of an associativity a_{xyz}: (xy)z --> x(yz). 

Example 5: It follows easily from Leibniz that d(1|[2||3]) = 
           { 1|[2|3], 1|[3|2] }. 

Example 6: For 1|2||3, we first apply rule (1), where we remove the 
           relation 2||3. This leaves only the consequence 1|2, so we 
           perform all possible 1-shufflings of 3 with 1|2. This produces 
           1|2|3, 1|3|2, 3|1|2 as part of the boundary. 

           We can also apply rule (2), which is trickier. Let us start by 
           writing down the complete set of consequences of 1|2||3: they 
           are 1|2, 2||3, 1||3. Now, types involve two or more entries, 
           so the substituted expression must be one of these consequences. 
           Now [1|2]||3 is clearly a boundary cell: we have 
           C_1 = C_2 = 1|2, and intercalating 1|2 for * in *||3 gives 
           the original type expression; therefore this is OK. 1|[2||3] 
           is also a boundary cell, which we verify by taking C_1 = 2 as 
           the 1-component: intercalating 2 in 1|* gives the correct 
           consequence 1|2. Finally, [1||3]|2 is a boundary: by taking 
           C_1 = 1, intercalation in *|2 gives a correct consequence. It 
           is easy to check that no other boundary cells are possible. 

           Of course, these boundary cells also have non-trivial boundaries, 
           which are calculated essentially as in our prior examples. The 
           reader might like to verify that the resulting poset has a nerve 
           where the star of 1|2||3 looks like 

                   [1|2]|3 ---------- 3|[1|2]
                     /                    \ 
               1|2|3/                      \3|1|2
                   /                        \ 
               1|[2|3]       1|2||3       [3|1]|2 
                   \                        / 
            1|[2||3]\                      /[1||3]|2
                     \                    /
                  1|[3|2] ----------- [1|3]|2

           which of course is an instance of a braiding hexagon. 

Example 7: For [1||2]||3, the boundary is calculated using Leibniz: 
           it is easy to check that this yields 
           { [1|2]||3, [2|1]||3, [1||2]|3, 3|[1||2] }. These cells 
           also have non-trivial boundaries, and the resulting picture 
           looks like an instance of naturality for the braiding. 

Example 8: Here is our granddaddy example. We calculate the structure 
           of 1||2||3. Using rule (1), we can remove 1||2 and 1-shuffle 
           the 1-components of 1 and 2 (which are just 1 and 2 again), 
           or remove 2||3 and 1-shuffle the 1-components of 2 and 3 
           (which are 2 and 3 again). This yields the cells 
           1|2||3, 2|1||3, 1||2|3, 1||3|2. 

           Using rule (2), we first write the consequences 1||2, 2||3, 
           1||3. Now 1||3 is impossible as a substituted expression, 
           since it equals its own 2-component, and intercalating it 
           in 2||* or *||2 leads to a consequences false in 1||2||3. 
           The only correct possibilities are [1||2]||3 and 1||[2||3]. 

           We have already done the essential calculations for obtaining 
           the structure of these boundary cells. To save space, we will 
           not exhibit the full-blown 3-cell structure of 1||2||3: it 
           turns out to be a 3-cell which mediates between the two 
           ways of giving a commutative diagram proof of the Yang-Baxter 
           identity in a braided monoidal category. In other words, it 
           is a structure cell which obtains in a braided monoidal 

© 1999 Todd H. Trimble