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.
A.1.
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.
A.2.
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.
A.3.
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
algebra).
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
preliminaries.
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.,
[1|2]||3.
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
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]
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 ------- 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
[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
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
2-category.
© 1999 Todd H. Trimble