DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA
AND ASSOCIAHEDRA
SAMSON SANEBLIDZE1 AND RONALD UMBLE2
Abstract.We construct an explicit diagonal on the permutahedra {Pn}.
Related diagonals on the multiplihedra {Jn}and the associahedra {Kn}are
induced by Tonks' projection ` : Pn ! Kn+1[19] and its factorization thr*
*ough
Jn. We use the diagonal on {Kn}to define the tensor product of A1 (co)a*
*lgebras.
We introduce the notion of a permutahedral set Z, observe that the double
cobar construction 2C*(X) is a naturally occurring example and lift the
diagonal on {Pn}to a diagonal on Z.
1.Introduction
A permutahedral set is a combinatorial object generated by permutahedra {Pn}
and equipped with appropriate face and degeneracy operators. Permutahedral sets
are distinguished from cubical or simplicial set by higher order (nonquadratic)
relations among face and degeneracy operators. In this paper we define the noti*
*on
of a permutahedral set and observe that the double cobar construction 2C*(X) is
a naturally occurring example. We construct an explicit diagonal P : C*(Pn) !
C*(Pn) C*(Pn) on the cellular chains of permutahedra and show how to lift P
to a diagonal on any permutahedral set. We factor Tonks' projection Pn ! Kn+1
through the multiplihedron Jn and obtain diagonals J on C*(Jn) and K on
C*(Kn). We apply K to define the tensor product of A1 (co)algebras in maximal
generality; this solves a longstanding open problem in the theory of operads. *
*One
setting in which the need to construct the tensor product of two A1 algebras a*
*rises
is the open string field theory of M. Gaberdiel and B. Zwiebach [7].
We mention that Chapoton [4], [5] constructed a diagonal on the direct sum
n 2C*(Kn) of the form : C*(Kn) ! i+j=nC*(Ki) C*(Kj) that coincides
with Loday and Ronco's diagonal on binary trees [13] in dimension zero. While
Chapoton's diagonal is primitive on generators, ours is not.
The paper is organized as follows: Section 2 reviews the polytopes we consider
and establishes our notation and pointofview. The diagonal P is introduced in
Section 3; related diagonals J and K are obtained in Section 4. Tensor produc*
*ts
of A1 (co)algebras are defined in Section 5 and permutahedral sets are introdu*
*ced
in Section 6.
____________
Date: November 22, 2002.
1991 Mathematics Subject Classification. Primary 55U05, 52B05, 05A18, 05A19;*
* Secondary
55P35.
Key words and phrases. Diagonal, permutahedron, multiplihedron, associahedro*
*n.
1This research was funded in part by Award No. GM12083 of the U.S. Civilian*
* Research and
Development Foundation for the Independent States of the Former Soviet Union (C*
*RDF) and by
Award No. 9900817 of INTAS.
2This research was funded in part by a Millersville University faculty resea*
*rch grant.
1
2 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
The first author wishes to acknowledge conversations with JeanLouis Loday
from which our representation of the permutahedron as a subdivision of the cube
emerged. The second author wishes to thank Millersville University for its gene*
*rous
financial support and the University of North Carolina at Chapel Hill for its k*
*ind
hospitality during work on parts of this project.
2. Permutahedra, Multiplihedra and Associahedra
We begin with a review of the relevant polytopes and establish our notation. *
*Let
Sn+1 denote the symmetric group on n_+_1_= {1, 2, . .,.n +a1}nd recall that the
permutahedron Pn+1 is the convex hull of (n + 1)! vertices (oe(1), . .,.oe(n2+ *
*1))
Rn+1, oe 2 Sn+1 [6], [15]. As a cellular complex, Pn+1 is an ndimensional conv*
*ex
polytope whose (n  k)faces are indexed either by (planar rooted) (k + 1)leve*
*led
trees (PLT's) with n + 2 leaves or by permutations M1 . ..Mk+1 of (ordered)
partitions of n_+_1_. Elements of these two indexing sets correspond in the fol*
*lowing
way: Let Tnk+1+2denote a (k + 1)leveled tree with root node in level k + 1 and*
* n + 2
leaves numbered from left to right. For 1 m n+1, assign the label m to the *
*node
at which branches containing leaves m and m + 1 meet (a node can have multiple
labels) and let Mj = {labels assigned to nodes atjlevel}; we refer to Mj as the*
* set
of jlevel meets in Tnk+1+2. Then M1 . ..Mk+1 is the partition of n_+_1_corre*
*sponding
to Tnk+1+2(see Figure 1). In particular, vertices of Pn+1 are indexed either by*
* binary
(n + 1)leveled trees or by partitions M1 . ..Mn+1 of n_+_1_, i.e., elements *
*of Sn+1.
The map from Sn+1 to binary (n + 1)leveled trees was constructed by Loday and
Ronco [13]; its extension to faces of Pn+1 was given by Tonks [19].
The associahedra {Kn+2} , which serve as parameter spaces for higher homotopy
associativity, are closely related to the permutahedra. In his seminal papers o*
*f 1963
[18], J. Stasheff constructed the associahedra in the following way: Let K2 = **
*; if
Kn+1 has been constructed, define Kn+2 to be the cone on the set
[
(Kr x Ks)k.
1r+s=n+3 k ns+3
Thus, Kn+2 is an ndimensional convex polytope.

@   @ 
@@ @   @ 
@ o2 o 56 ! 256134
@ o 
1 @  ! d(0,2)d(0,1)d(1,1)(4,2)
@o
34
 ! ((x1(x2x3))x4(x5x6x7))


Figure 1.
Stasheff's motivating example of higher homotopy associativity in [18] is the
singular chain complex on the loop space of a connected CW complex. Here asso
ciativity holds up to homotopy, the homotopies between the various associations
are homotopic, the homotopies between these homotopies are homotopic, and so
on. An abstract A1 algebra is a dga in which associativity behaves as in Stash*
*eff's
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 3
motivating example. If '2 : A A ! A is the multiplication on an A1 algebra
A, the homotopies 'n : A n ! A are multilinear operations such that '3 is a
homotopy between the associations (ab)c and a (bc)thought of as quadratic com
positions '2 '2 1 and '2 1 '2 in three variables, '4 is a homotopy bound
ing the cycle of five quadratic compositions in four variables involving '2 and*
* '3,
and so on. Let C*(Kr) denote the cellular chains on Kr. There is a chain map
C*(Kr) ! Hom (A r, A), induced by the natural correspondence between faces of
Kr and all possible compositions of the 'n's in rvariables (modulo an appropri*
*ate
equivalence), which determines the relations among the compositions of 'n's. A
detailed discussion of A1 algebras and their tensor product appears in Section*
* 5.
Now if we disregard levels, a PLT is simply a planar rooted tree (PRT). Quite
remarkably, A. Tonks [19] showed that Kn+2 is the identification space Pn+1= ~
obtained from Pn+1 by identifying all faces indexed by isomorphic PRT's. Since
the quotient map ` : Pn+1 ! Kn+2 is cellular, the faces of Kn+2 are indexed by
PRT's with n + 2 leaves. The correspondence between PRT's with n + 2 leaves
and parenthesizations of n + 2 indeterminants is simply this: Given a node N,
parenthesize all indeterminants corresponding to all leaves on branches that me*
*et
at node N.
Example 1. With one exception, all classes of faces of P3 consist of a single
element. Tonks' projection ` sends elements of the exceptional class
[132, 132, 312]
to the vertex on K4 represented by the parenthesization ((oo)(oo)). The permuta
tions 132 = d(1,1)d(0,1)and 312 = d(0,1)d(2,1)insert inner parentheses in t*
*he oppo
site order; the partition 132 = d(0,1)(2,1)represents a homotopy between them.*
* The
classes of faces of P4 with more than one element and their representations on *
*K5
are:
[1243, 1243, 4123]= ((o o o)(oo))
[1324, 1324, 3124]= ((oo)(oo)o)
[1423, 1423, 4123]= ((oo)o (oo))
[2413, 2413, 4213]= (o (oo)(oo))
[1342, 1342, 3412]= ((oo)(o o o))
[1324, 1324, 3124]= (((oo)(oo))o)
[2431, 2431, 4231]= (o ((oo)(oo)))
[1243, 1243, 1423, 1423,=4123](((oo)o)(oo))
[1342, 1342, 3142, 3142,=3412]((oo)((oo)o))
[1432, 1432, 4132, 4132,=4312]((oo)(o)(oo))
[2143, 2143, 2413, 2413,=4213]((o((oo))oo)).
Elements of the first five classes above correspond to faces and edges that pro*
*ject
to an edge; elements of the next six classes correspond to edges and vertices t*
*hat
project to a vertex.
Whereas the correspondence between PRT's and parenthesizations allows us to
insert parentheses without regard to order, the analogous correspondence between
PLT's and parenthesizations constrains us in the following sense: First, simult*
*ane
ously insert all level 1 (innermost) parentheses as indicated by the 1level m*
*eets
in M1; second, simultaneously insert all level 2 parentheses as indicated by the
2level meets in B, and so on. This procedure suggests a correspondence between
4 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
partitions M1 . ..Mk+1 of n_+_1_and kfold compositions of face operators act*
*ing
on n + 2 indeterminants, which we now define.
For s 1, choose pairs of indices {(ir, `r)}1 rssuch that 0 ir < ir+1 n
and ir + `r + 1 ir+1. The face operator
d(i1,`1)...(is,`s)
acts on x1x2. .x.n+2by inserting s disjoint (nonnested) pairs of parentheses i*
*n the
following way: The first pair encloses the `1 + 1 indeterminants xi1+1. .x.i1+`*
*1+1,
where i1+ `1+ 1 i2. The second pair encloses the `2+ 1 indeterminants xi2+1. *
*. .
xi2+`2+1, where i2 + `2 + 1 i3, and so on. Thus, d(i1,`1)...(is,`s)produces t*
*he
parenthesization
x1. .(.xi1+1. .x.i1+`1+1).(.x.is+1.x.i.s+`s+1).x.n.+2.
A composition of face operators
(2.1) d(0,`)d(ik1,`k1)...(iks,`k.d.i.1,`1...i1 ,`1
k sk)( 1 1)( s1 s1)
continues this process inductively. If the jth operator has been applied, apply
the (j + 1)stby treating each pair of parentheses inserted by the jth as a sing*
*le
indeterminant. Since each such composition determines a unique (k + 1)leveled
tree, the (n  k)faces of Pn+1 are indexed by compositions of face operators o*
*f the
form in (2.1) above (see Figure 1). For simplicity we usually suppress the left*
*most
operator d(0,`), which inserts a single pair of parentheses enclosing everythin*
*g.
Conversely, given an operator d(ij1,`j1)...(ijs,`js)with pairs of indices def*
*ined as
[
above, let Mj = 1 r s ijr+ 1, . .,.ijr+.`jrThen a composition of the form in
(2.1) acting on n + 2 indeterminants corresponds to the partition M1 . ..Mk of
n_+_1_.
Example 2. Refer to Figure 1 above. The composition d(0,2)d(0,1)d(1,1)(4,2)acti*
*ng
on x1. .x.7corresponds to the partition 256134 of 6_and acts in the following*
* way:
First, the operator d(1,1)(4,2)inserts two pairs of parentheses
x1(x2x3)x4(x5x6x7).
Note that {2, 5, 6}decomposes as {2}[ {5, 6}, i.e., the union of subsets of con*
*sec
utive integers with maximal cardinality. Next, the operator d(0,1)inserts the s*
*ingle
pair
(x1(x2x3))x4(x5x6x7).
Finally, d(0,2)inserts the single pair
((x1(x2x3))x4(x5x6x7)).
We summarize this discussion as a proposition.
Proposition 1. There exist onetoone correspondences:
{Faces ofPn+1} $ {Leveled trees withn + 2 leaves}
$ {Partitions ofn_+_1}
æ oe
$ Compositionsaofcfacetoperatorsingnon+ 2 indetermi*
*nants.
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 5
In the discussion that follows, we choose to represent the permutahedra and
related polytopes as subdivisions of the ncube. Although our representations d*
*iffer
somewhat from the classical ones, they are inductively defined and possess the
combinatorics we need.
The permutahedron Pn+1 can be realized as a subdivision of the standard n
cube In in the following way: For ffl = 0, 1 and 1 i n, let en1i,ffldenote*
* the
(n  1)face (x1, . .,.xi1, ffl, xi+1, . .,.xn) In. For 0 i j 1, let I*
*i,j=
1  2i, 1  2j I, where 21 is defined to be 0, and let `(k)= `1 + . .+.`k.
Set P1 = * and label this vertex d(0,1). To obtain Pn+1, n 1, assume that Pn
has been constructed. Subdivide and label the (n  1)faces of Pn x I as indica*
*ted
below:
_Face_of_Pn+1____________Label_________________________

en1n,0 d(0,n)

en1n,1 d(n,1)

d(i1,`1)...(ik,`k)x I0,n`(k)d(i1,`1)...(ik,`k)
æ 
d(i1,`1)...(ik,`k)x In`(k),1d(i1,`1)...(ik,`k)(n,1),ik + `k < n
d(i1,`1)...(ik,`k+1),ik + `k = n
d(0,1)d(2,1) d(2,1) d(1,1)d(2,1)
_____________oo
d(0,1)(2,1) d(1,2)
 
 
d(1,1)d(0o,1) P3 od(1,1)d(1,1)
 
 
d(0,1) d(1,1)
_____________oo
d(0,1)d(0,1) d(0,2) d(0,1)d(1,1)
Figure 2: P3 as a subdivision of P2 x I.
(1, 1, 1)
o__________________oQQ
 Q  Q
 Q o  Qo
o____Q___________o Q
  Q   Q
 o Q o_________________ooQ
oQ Q  oQ Q 
 Q  Q   Q  Q 
 Qo Q o  Qo Qo
     
     
  o________________o_
o____ __________o  
Q   Q  
Q Q  Q Q  
(0, 1, 0) Qo  oQ 
Q  Q 
Q o_________________oQ
(0, 0, 0) (1, 0, 0)
Figure 3a: P4 as a subdivision of P3 x I.
6 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
 
 
o_________________oo
 
 
 
 
 
 d(3,1) 
 
 
 
  (1, 1, 1)
 
_________________________________________________________________ooooooo
      
 d(1,1)(3,1)  d(2,2) d(0,1)(2,2)d(0,1)(3,1)
o d o________od _________________oo _________oo
 (0,2)(3,1)   (1,3)   
      
_________________oo ________oo o________o o
      
  d(1,1)  d(2,1) d(0,1)(2,1)d(0,1)
 d(0,2)   d(1,2)   
      
      
_________________________________________________________________ooooooo
 
(0, 0, 0)  
 
 
 
 d(0,3) 
 
 
 
 
 
o_________________oo
Figure 3b: P4 as a subdivision of P3 x I.
The multiplihedra {Jn+1}, which serve as parameter spaces for homotopy mu*
*lti
plicative morphisms of A1 algebras, lie between the associahedra and permu*
*tahe
dra (see [18], [8]). If f1 : A ! B is such a morphism, there is a homotopy *
*f2 between
the quadratic compositions f1'2Aand '2B f1 f1 in two variables, there is *
*a ho
motopy f3 bounding the cycle of the six quadratic compositions in three var*
*iables
involving f1, f2, '2A, '3A, '2Band '3B, and so on. The natural corresponden*
*ce be
tween faces of Jr and all possible compositions of fi, 'jAand 'kBin rvaria*
*bles (mod
ulo an appropriate equivalence) induces a chain map C*(Jr)! Hom (A r, B).
The multiplihedron Jn+1 can also be realized as a subdivision of the cube*
* In in
the following way: For n = 0, 1, 2, set Jn+1 = Pn+1. To obtain Jn+1, n 3,*
* assume
that Jn has been constructed. Subdivide and label the (n  1)faces of Jn x*
* I as
indicated below:
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 7
_Face_of_Jn+1_________Label__________________________
en1n,0 d(0,n)

en1n,1 d(n,1)

d(0,`1)...(ik,`k)x I0,nkd(0,`1)...(ik,`k)
æ 
d(0,`1)...(ik,`k)x Ink,1d(0,`1)...(ik,`k)(n,1),ik < n  `k
d(0,`1)...(ik,`k+1),ik = n  `k
d(i,`)x I d(i,`), 1 i < n  `

d(i,`)x I0,i d(i,`), 1 i = n  `

d(i,`)x Ii,1 d(i,`+1), 1 i = n  `

 
 
o________________oo
 
 
 
 
 d 
 (3,1) 
 
 
 
  (1, 1, 1)
___________________________________________________________ooooooo
 d(0,2)(3,1)    d(2,2) d(0,1)(2,2)d(0,1)(3,1)
      
________________oo  d(1,3)_________________oo ________oo
      
  ________ ________ 
 d(0,2)  d(1,1)o o o o 
    d(2,1) d  d(0,1) 
   d   (0,1)(2,1) 
   (1,2)   
      
_____________________________________________________________ooooooo
 
(0, 0, 0)  
 
 
 d(0,3) 
 
 
 
 
 
o________________oo
Figure 4: J4 as a subdivision of J3 x I.
Thus faces of Jn+1 are indexed by compositions of face operators of the form
(2.2) d(0,`)d(im ,`m.).d.(ik1,`k1)...(iks,`ks).d.(.i1,`1).
In terms of trees and parenthesizations this says the following: Let T be a (k *
*+ 1)
leveled tree with leftmost branch attached at level p. For 1 j < p, insert l*
*evel
j parentheses one pair at a time without regard to order as in Kn+2; next, inse*
*rt
all level p parentheses simultaneously as in Pn+1; finally, for j > p, insert l*
*evel j
parentheses one pair at a time without regard to order. Thus multiple lower ind*
*ices
8 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
in a composition of face operators may only occur when the leftmost branch is
attached above the root. This suggests the following equivalence relation on the
set of (k + 1)leveled trees with n + 2 leaves: Let T and T 0be pleveled trees*
* with
n + 2 nodes whose plevel meets Mp and M0pcontain 1. Then T ~ T 0if T and T 0
are isomorphic as PLT's and Mp = M0p. This equivalence relation induces a cellu*
*lar
projection ß : Pn+1 ! Jn+1 under which Jn+1 can be realized as an identification
space of Pn+1. Furthermore, the projection Jn+1 ! Kn+2 given by identifying fac*
*es
of Jn+1 indexed by isomorphic PLT's gives the following factorization of Tonks'
projection:
Pn+1 ß! Jn+1
`& #
Kn+2
It is interesting to note the role of the indices `j in compositions of face op*
*erators
representing the faces of Jn+1 as in (2.2). With one exception, each Mj in the
corresponding partition M1 . ..Mm+1 is a set of consecutive integers; this ho*
*lds
without exception for all Mj on Kn+2. The exceptional set Mp is a union of s
sets of consecutive integers with maximal cardinality, as is typical of sets Mj*
* on
Pn+1. Thus the combinatorial structure of Jn+1 exhibits characteristics of both
Kn+2 and Pn+1.
In a similar way, the associahedron Kn+2 can be realized as a subdivision of *
*the
cube. For n = 0, 1, set Kn+2 = Pn+1. To obtain Kn+2, n 2, assume that Kn+1
has been constructed. Subdivide and label the (n  1)faces of Kn+2 as indicated
below:
_Face_of_Kn+2_Label_________________

en1`,0 d(0,`), 1 ` n

en1n,1 d(n,1),

d(i,`)x I d(i,`), 1 i < n  `

d(i,`)x I0,i d(i,`), 1 i = n  `

d(i,`)x Ii,1 d(i,`+1),1 i = n  `

d(2,1)
(0, o_____________o1)(1, 1)
 
 d(1,2)
 
d(0,1) K4 o
 
 d(1,1)
 
o_____________o
(0, 0) d(0,2) (1, 0)
Figure 5: K4 as a subdivision of K3 x I.
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 9
 
 
o_____________o
 
 
 
 d(3,1) 
 
 
 (1, 1, 1)
_______________________________________________oooooo
    d(2,2)  
   d _____________oo 
   (1,3)  
  ______  
 d(0,2) d(1,1o) o  d(0,1) 
    d(2,1)  
   d(1,2)  
     
_________________________________________________oooooo
 
(0, 0, 0)  
 
 d(0,3) 
 
 
 
 
o_____________o
Figure 6: K5 as a subdivision of K4 x I.
3. A Diagonal on the Permutahedra
In this section we construct a combinatorial diagonal on the cellular chains *
*of
the permutahedron Pn+1 (up to sign). Issues related to signs will be resolved in
Section 6. Given a polytope X, let (C*(X) , @)denote the cellular chains on X w*
*ith
boundary @.
Definition 1. A map X : C*(X) ! C*(X) C*(X) is a diagonal on C*(X) if
(1) X (C*(e)) C*(e) C*(e) for each cell e X and
(2) (C*(X) , X , @)is a dg coalgebra.
A diagonal P on C*(Pn+1) is unique if the following two additional properties
hold:
(1) The canonical cellular projection Pn+1 ! In induces a dgc map C*(Pn+1) !
C*(In) (see Figures 7 and 8).
(2) There is a minimal number of components a b in P (Ck (Pn+1))for
0 k n.
Since the uniqueness of P is not used in our work, verification of these facts*
* is
left to the interested reader.
Certain partitions of n_+_1_can be conveniently represented in a tableau, the
simplest of which are the ``step'' tableaux. A step tableau is a matrix whose n*
*onzero
entries form a ``staircase path'' connecting the lowerleft and upperright cor*
*ners;
entries decrease when reading upward along a ``riser'' and increase when reading
from lefttoright along a ``tread'' (see Example 3 below). More formally,
10 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
Definition 2. A q x p matrix Eqxp = (ei,j)is a step tableau if and only if
(1) {ei,j2 Eqxp ei,j6= 0}= p_+_q__1.
(2) eq,16= 0.
(3) If ei,j6= 0 then
(a) ei1,j1= ei+1,j+1= 0 and either ei1,j= 0 or ei,j+1= 0, exclu
sively.
(b) If ei,j= ek,`then i = k and j = `.
(c) If ei1,j= 0 then ei,j< ei,j+1.
(d) If ei,j+1= 0 then ei1,j< ei,j.
Definition 3. A partition A1 . ..Ap of n_is increasing (resp. decreasing) if *
*minAj
< max Aj+1 (resp. max Aj1 > minAj) for all j.
Given an increasing partition A1 . ..Ap of n_+_1_, order the elements of ea*
*ch Aj
so that Aj = a1,j< . .<.anj,j; then minAj = a1,jand max Aj = anj,j. There
is a unique q x p step tableau E associated with A1 . ..Ap determined as foll*
*ows:
Fill in the first column from the bottom row upward, beginning with an1,1first,
then an11,1, and so on. Inductively, if the (j  1)stcolumn has been filled wi*
*th
minAj1 in row k, fill in the jth column from row k upward, beginning with anj,j
first, then anj1,j, and so on. This process terminates after p steps with the *
*q x p
step tableau E. For 1 i q, let Bi= {nonzero entries in row q i+1 of E}; t*
*hen
B1 . ..Bq is a decreasing partition uniquely determined by A1 . ..Ap. Simil*
*arly, a
given decreasing partition B01 . ..B0quniquely determines a q x p step tablea*
*u E0
and an increasing partition A01 . ..A0pwith A0j= {nonzero entries in column *
*j of
E0}.
Definition 4. Given a step tableau Eqxp, let a = A1 . ..Ap be the increasing
partition given by the columns of E; let b = B1 . ..Bq be the decreasing part*
*ition
given by the rows of E. Then a b is a (p, q)strong complementary pairing (SC*
*P).
The discussion above establishes the following:
Proposition 2. There is a onetoone correspondence
{Step tableaux}$ {Strong complementary pairings}.
Example 3. The (4, 6)SCP 179348256 971384652 is associated with the
6 x 4 step tableau ____________
______2_
______5_
____4_6_.
_1_3_8__
_7______
_9______
Let a b be a (p, q)SCP with p + q = n + 2. The components of P (Cn (Pn+1))
range over all such SCP's and their ``derivatives'' produced by rightshift ope*
*rations
on a and leftshift operations on b.
Definition 5. Let a = A1 . ..Ap and b = B1 . ..Bq be partitions of n_+_1_. *
*For
1 i < p and 1 < j q, let M Ai and N Bj be proper nonempty subsets
such that minM > max Ai+1 and max Bj1 < minN. Define
RiM(a)= A1 . ..Ai\ MAi+1[ M . ..Ap
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 11
and
LjN(b)= B1 . ..Bj1[ NBj\ N . ..Bq.
Also define Rk?= Lk?= Id, for all k.
The operators R and L can be thought of as ``adjacency'' operators on the faces
of Pn+1. A partition a = A1 . ..Ap of n_+_1_corresponds to an (n  p + 1)face
of Pn+1; if M is nonempty, the partition RiM(a) corresponds to an (n  p + 1)
face adjacent to a. Thus, given a partition a1 = A1 . ..Ap of n_+_1_, the seq*
*uence
a1, . .,.ak+1 = RkMk(ak), . .,.apcorresponds to a path of adjacent (n  p + 1)
faces from a1 to ap.
Definition 6. Let a b be a (p, q)SCP. A pairing u v is a (p, q)complement*
*ary
pairing (CP) related to a b if there exist compositions Rp1Mp1.R.1.M1and L2*
*N2. . .
LqNqsuch that u = Rp1Mp1.R.1.M1(a)and v = L2N2. .L.qNq(b).
Let a b be a (p, q)SCP with associated step tableau Eqxp. A related CP
Rp1Mp1.R.1.M1(a) L2N2. .L.qNq(b)can be represented by a q x p tableau derived
from Eqxp in the following way: Set E1 = Eqxp. Inductively, for 1 k p  1
assume that Ek has been obtained. Since RkMkis defined, Mk {nonzero entries *
*in
column k of Ek} and either minMk > max{column k +1 of Ek} or Mk = ?. Define
Ek+1 = RMk Ek
to be the tableau obtained from Ek by shifting Mk right to column k + 1 and
replacing the cells previously occupied by Mk with zeros. The induction termina*
*tes
with the tableau
Ep = RMp1 . .R.M1E.
Now continue the induction as follows: For 1 k q  1, assume that Ep+k1 has
been obtained. Since LkNkis defined, Nk Bqk+1 = {nonzero entries in row k of
Ep+k1} and either minNk > max{row k + 1 of Ep+k1} or Nk = ?. Define
Ep+k = LNkEp+k1
to be the tableau obtained from Ep+k1 by shifting Nk down to row k + 1. The
induction terminates with the tableau
LNq1. .L.N1RMp1 . .R.M1E,
referred to as a q x p derived tableau, and determines a (p, q)CP with one of *
*the
following forms:
RMp1 . .R.M1(a) LN2 . .L.Nq(b),Mi6= ? and Nj 6= ? for some i, j
RMp1 . .R.M1(a) b, Mi6= ? and Nj = ? for some i, all j
a LN2 . .L.Nq(b),Mi= ? and Nj 6= ? for all i, some j
a b, Mi= Nj = ? for all i, j.
For each n 1 and p + q = n + 2, let p,q= {(p, q)complementary pairings}.
Since a q x p derived tableau uniquely determines a (p, q)CP and conversely, we
conclude that
Proposition 3. There is a onetoone correspondence:
p,q$ {q x p derived tableaux}.
We are ready to define a diagonal on C*(Pn+1) up to sign.
12 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
Definition 7. Define P (1_)= 1_ 1_. Inductively, assume that P : Ci(Pi+1)!
C*(Pi+1) C*(Pi+1) has been defined for all i < n. For i = n, define P (up to
sign) by
X
(3.1) P (n_+_1_)= u v.
u v2 p,np+2
0 p n
Multiplicatively extend P to all of C*(Pn+1) using the fact that each cell of *
*Pn+1
is a Cartesian product of cells Pi+1, i < n.
Example 4. Four tableaux can be derived from the step tableau
_________
___2_3_
E = _1_5__ :
_4____
_________
___2_3_
L? L? R? R? E = _1_5__ $ 14253 41523
_4____
_________
___2_3_
L? L? R{5}R? E = _1__5_ $ 14235 41523
_4____
_________
___2_3_
L{5}L? R? R? E = _1____ $ 14253 45123
_4_5__
_________
___2_3_
L{5}L? R{5}R? E = _1____ $ 14235 45123
_4__5_
Up to sign, four components of P (5_)arise from E, namely,
(14235 + 14253) (41523 + 45123).
Definition 8. The transpose of a pairing A1 . ..Ap B1 . ..Bq is the pairi*
*ng
(A1 . ..Ap B1 . ..Bq)T= Bq . ..B1 Ap . ..A1.
Note that the transpose of a step tableau is another step tableau. In fact, A1*
* . ..Ap
B1 . ..Bq is the (p, q)SCP associated with the q x p step tableau E if and *
*only
if its transpose Bq . ..B1 Ap . ..A1 is the (q, p)SCP associated with th*
*e p x q
step tableau ET . In general, the transpose of a (p, q)CP is a (q, p)CP.
Example 5. On P3, all but two of the eight derived tableaux are step tableaux:
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 13
___
_________ _1_ ______21 ______21
_1_2_3_ _2_ ______3 ! R{3}! ______3
_3_ _____  ____ 
______ ______ ______ ______
___2_ ___1_ _1_3_ ! L{3}! _1__
_1_3_ _2_3_ _2__ _2_3_
Up to sign,
P (3_)= 123 123+ 123 321
+ 123 132+ 213 231
+ 132 312+ 123 213
+ 123 312+ 123 231.
Note that each component in the righthand column is the transpose of the compo
nent to its left.
Example 6. Up to sign,
P (4_) = 1234 4321
+1234 (3214 + 3241 + 3421)
+1234 (2143 + 2413)
+1234 1432
+2314 (3241 + 3421)
+1324 (3142 + 3412)
+ (1324 + 1234 + 1423 + 1342) 4312
+ (1234 + 1243) (4213 + 4231)
+3124 3421
+2134 (2431 + 4231)
+2413 4231
+ (1234 + 1423) 4132
+(all transposes of the above).
We conclude this section with our main theorem:
Theorem 1. The cellular boundary map @ : C*(Pn+1) ! C*(Pn+1) is a P 
coderivation for all n 1.
Theorem 1 is an immediate consequence of Lemmas 1 and 2 below. Let A1 . ..Ap
be a partition of n_+_1_. For 1 k p and a proper nonempty subset M Ak,
define a face operator dkM: Cnp+1 (Pn+1)! Cnp (Pn+1)by
dkM(A1 . ..Ap)= A1 . ..Ak1MAk \ M . ..Ap;
then (up to sign) the cellular boundary @ : Cnp+1 (Pn+1)! Cnp (Pn+1)decom
poses as X
@ (A1 . ..Ap)= dkM(A1 . ..Ap).
1 k p
M Ak
14 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
P
In particular, @ (n_+_1)= S1S2, where S2 = n_+_1_\ S1Pand ranges over all
nonemptyPproper subsetsPof n_+_1_. Thus, P @ (n_+_1)= P (S1) P (S2)=
(ui vj) uk v` = uiuk vjv`, where ui vj and uk v` range over all
CP's of partitions of S1 and S2, respectively. Note that although uiuk vjv`*
* is
not a CP, there is the associated block tableau
_________________
  `xk 
 0 E 
  
(3.2) _______________
 jxi  
 E  0 
  
_______________
in which Ejxiand E`xk are the derived tableaux associated with ui vj and uk v`;
in fact, the components of P @ (n_+_1)lie in onetoone correspondence with bl*
*ock
tableaux of this form. Now consider a particular component (ui vj) uk v` ,
where ui vj = U1 . ..Ui V1 . ..Vj is a CP of partitions of S1 and uk v`*
* =
U1 . ..Uk V 1 . ..V `is a CP of partitions of S2. Let ai bj = A1 . ..Ai
B1 . ..Bj and ak b` = A1 . ..Ak B1 . ..B` be the SCP's related to ui *
* vj
and uk v`; then
_______ _______
   ` 
 Bj   B 
_________________  _________________ 
    ______.  1   k  ______.
 A1 . ..Ai =  ..  and  A . ..A  =  .. 
    ______     ______
______________   ______________  
 B1   B1 
   
______ ______
are step tableaux involving the elements of S1 and S2, respectively, and the bl*
*ock
tableau associated with the component (ai bj) ak b` can be expressed in the
following two ways:
_____________
  ` 
 B 
  
 ______
 .. 
__________________________________  0 __.___
  1   k    1 
 0  A  . ..A   B 
       
______________________________= ___________.
       
 A1  . .. Ai  0   Bj  
       
______________________________ ______ 
 ..  
___.__0 
  
 B1  
  
___________
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 15
Lemma 1. Each component of P @ (n_+_1)is also a component of
(1 @ + @ 1) P (n_+_1_).
Proof.Let (ui vj) uk v` be a component of P @ (n_+_1)and consider its
related component of SCP's (ai bj) ak b` . There are two cases.
Case_1_: Assume min (Ai)> max A1 .
Then min(Ui)= min(Ai)> max A1 max U1 and
____________________________
  1   k 
 0  U . .. U 
    
________________________
    
 U1  . . .Ui  0 
    
________________________
is the derived tableau associated with the CP U1 . ..Ui[ U1 . ..Uk vjv` *
*of
partitions of n_+_1_. Hence
1 k ` k `
diUiU1 . ..Ui[ U  . ..U vjv = uiu vjv
is a component of (1 @ + @ 1) P (n_+_1_).
Case_2_: Assume max (Bj)< min B1 .
Then max (Vj) max (Bj)< min B1 = min V 1 and
_____________
  ` 
 V 
  
 ______
 0  
  .. 
  . 
  
___________
  1 
 Vj V 
  
___________
  
 ..  
 .  
  0 
_____ 
  
 V1  
  
___________
is the derived tableau associated with the CP uiuk V1 . ..Vj [ V 1 . ..V*
* `of
partitions of n_+_1_. Again,
1 ` k `
uiuk djVjV1 . ..Vj[ V  . ..V= uiu vjv
is a component of (1 @ + @ 1) P (n_+_1_)and the conclusion follows.
16 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
Lemma 2. Each nonvanishing component of (1 @ + @ 1) P (n_+_1_)is a com
ponent of P @ (n_+_1). Specifically, let a b = A1 . .A.p B1 . ..Bq be a *
*SCP
of partitions of n_+_1_, let u v = U1 . ..Up V1 . ..Vq be a CP such tha*
*t u =
Rp1Mp1.R.1.M1(a)and let M be a proper nonempty subset of Uk, 1 k p. Then
dkM(u) v (and dually for u dkM(v)with M Vq and 1 k q) is a nonvanishing
component of P @ (n_+_1)if and only if Ak \ M 6= ?, min (Uk \ M)< max Ak+1
when k < p, max (Uk \ M) < minM and Mk = ?.
Proof.Let M0 = Mp = ?; then clearly, Ui= (Ai[ Mi1)\Mifor 1 i p. Under
the conditions above, dkM(u) v is a component of
P (A1 [ . .[.Ak1 [ M(Ak \ M) [ Ak+1 [ . .[.Ap).
In particular, a b = ap1ap2 bq1bq2where ap1= A1 . ..Ak2Ak1 [ (Ak \ M)
and ap2= Ak\MAk+1 . ..Ap. The dual u dkM(v)follows by ``mirror symmetry.''
Conversely, if the conditions above fail to hold, we exhibit a unique CP ~u ~vd*
*istinct
from u v such that u v  ~u ~v2 ker(@ 1 + 1 @) P . For uniqueness, note
that if u v  ~u ~v2 ker(@ 1 + 1 @) P , then exactly one of the the foll*
*owing
relations hold:
__
(1) dkM(u) = d`N(~u) and v = ~vfor some M Uk, N U`, 1 k, ` p;
__
(2) dkM(u) = ~uand v = d`N(~v) for some M Uk, 1 k p, and some N V`,
1 ` q  1;
__
(3) u = ~uand dkM(v) = d`N(~v) for some M Vk, N V`, 1 k, ` q.
For existence, we consider all possible cases.
Case_1_: Assume Ak \ M = ?.
Then M Mk1 \ Mk and Mk Ak [ Mk1 \ M. Let
~u= U1 . ..Uk1 [ MUk \ M . ..Up;
then
dk1Uk1(~u) = dkM(u).
Furthermore, since min(Mk1 \ M) minMk1 > max Ak, we may replace Rk1Mk1
with Rk1Mk1\Mand obtain
~u= Rp1Mp1.R.k.MkRk1Mk1\M.R.1.M1(a).
Therefore ~u v is a CP related to a b and (u  ~u) v 2 ker(@ 1 + 1 @) P*
* ,
i.e., the component dkM(u) v vanishes.
Case_2_: Assume Ak \ M 6= ? and min (Uk \ M)> max Ak+1 when k < p.
Let
~u= U1 . ..Uk1M (Uk \ M)[ Uk+1Uk+2 . ..Up;
then
dk+1Uk\M(~u)= dkM(u).
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 17
Furthermore, min [(Uk \ M)[ Mk]> max Ak+1 by assumption and the fact that
minMk > max Ak+1. Hence we may replace RkMkwith RkMk[(Uk\M)and obtain
~u= Rp1Mp1.R.k.+1Mk+1RkMk[(Uk\M). .R.1M1(a)
so that ~u v is a CP related to a b. Again, (u  ~u) v 2 ker(@ 1 + 1 @)*
* P .
Case_3_: Assume Ak \ M 6= ?, min(Uk \ M) < max Ak+1 when k < p, and either
minM < max(Uk \ M) or Mk 6= ?.
Let
~ = min{x 2 (Ak [ Mk1) \ M  x > minM}.
Subcase_3A_: Assume ~ =2Ak \ M.
Then either ~ 2 Ai\ (Uk \ M) for some i < k or ~ 2 Ai\ Uj for some i k and
some j > k.
Subcase_3A1_: Assume min Ai1> max (Ai\ ~)with 1 < i k.
First consider 1 < i < k. Then ~ = max Ai > max Ak since ~ 2 Uj with j > k,
and it follows that A1 . ..Ai1[ Ai\ ~Ai+1 . ..Ak[ ~Ak+1 . ..Ap is incr*
*easing.
Now min (Ak \ M) < max [(Ak \ M)[ ~]and furthermore max Ak 2 M (if not,
either max Ak 2 Uk \ M, which is impossible since ~ =2Ak, or max Ak 2 Mk,
which is also impossible since this would imply max Ak minMk > max Ak+1 >
min(Uk \ M) ~ = max Ai > max Ak). Thus min Ak1 < max Ak = max (Ak \
M) and
~a= A1 . ..Ai1[ Ai\ ~Ai+1 . ..Ak \ M (Ak \ M)[ ~Ak+1 . ..Ap
is increasing and uniquely determines a SCP ~a ~b. Let
~u= U1 . ..Ui1[ UiUi+1 . ..MUk \ MUk+1 . ..Up;
note that ~ =2M [ Mj and ~ 2 Ms for i s j  1. Thus
u~= Rp1Mp1.R.k.MkRk1Mk1\~\MRk2Mk1\~.R.i.1Mi\~Ri2Mi2.R.1.M1(~a)
and ~u v is a CP related to ~a ~b. Finally,
dkM(u)= di1Ui1(~u)
so that (u  ~u) v 2 ker(@ 1 + 1 @) P . On the other hand, if 1 < i = k, s*
*et
~a= A1 . ..Ak1 [ (Ak \ M)Ak \ MAk+1 . ..Ap
and
~up= U1 . ..Uk1 [ MUk \ MUk+1 . ..Up.
Subcase_3A2_: Assume min Ai1< max (Ai\ ~)with 1 i k.
Again, first consider 1 i < k. Let
~a= A1...Ai1Ai\ ~Ai+1...Ak \ M(Ak \ M) [ ~Ak+1...Ap
and
~u= dkM(u) = U1 . ..MUk \ MUk+1 . ..Up.
18 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
By the argument in Subcase 3A1, ~ais increasing and uniquely determines a SCP
~a ~b. Furthermore, since minMk1 = minMk1\M = ~ > max Ak, both Rk1Mk1\~
and Rk(Mk1\~)\Mare defined and we have
~u= Rp1Mp1.R.k.+1MkRk(Mk1\~)\MRk1Mk1\~.R.i.Mi\~Ri1Mi1.R.1.M1(~a).
Choose r such that ~ 2 Br and let
~v= V1 . ..Vr1Vr [ Vr+1Vr+2 . ..Vq.
Then drVr(~v) = v and ~u ~vis a CP related to ~a ~b. Therefore u v  ~u ~v2
ker(@ 1 + 1 @) P . Finally, when i = k, define ~vqas above and set
~a= A1 . ..Ak \ MAk \ MAk+1 . ..Ap.
Subcase_3B_: Assume ~ 2 Ak \ M.
Note that minM < ~ max (Uk \ M)whether or not Mk = ?.
Subcase_3B1_: Assume either ~ < max Ak or min Ak1 < max(Ak \ ~).
Note that when k = 1, ~ 2 A1 \ M. Let
Dk = {x 2 Ak \ M x ~}.
If ~ < max Ak, then max (Ak \ Dk)= max Ak. On the other hand, if ~ = max Ak,
then max (Ak \ ~)=2Dk (otherwise max (Ak \ ~)2 (Uk \ M)[ (Ak [ Uj)for some
j > k, and minM < max (Ak \ ~)< ~ contradicting the choice of ~) and it follows
that max (Ak \ Dk)= max (Ak \ ~). In either case, minAk1 < max(Ak \ Dk) by
assumption, and furthermore, min(Ak \ Dk) = min (Ak \ M) = min M < ~ =
max Dk. Finally, either min Dk = min Ak (when min Ak < min M) or min Dk =
~ = min(Uk\M) (when minAk = minM ), and in either case minDk < max Ak+1.
Let
~a= A1 . ..Ak1Ak \ DkDkAk+1 . ..Ap.
Then ~ais increasing and uniquely determines a SCP ~a ~b. Since min{[(Ak \ Dk)[
Mk1 \ M]} > ~ = max Dk, the operator Rk((Ak\Dk)[Mk1)\Mis defined and we
have
RpMp1. .R.k+1MkRk[(Ak\Dk)[Mk1]\MRk1Mk1.R.1.M1(~a)= dkM(u).
Choose r such that ~ 2 Br and let
~v= V1 . ..Vr1Vr [ Vr+1Vr+2 . ..Vq.
Then drVr(~v) = v and ~u ~v= dkM(u) ~vis a CP related to ~a ~b. Therefore
u v  ~u ~v2 ker(@ 1 + 1 @) P .
Subcase_3B2_: Assume ~ = max Ak and min Ak1 > max(Ak \ ~), 1 < k p.
Let
~u= U1 . ..Uk1 [ MUk \ M . ..Up;
then
dk1Uk1(~u) = dkM(u).
Let
~a= A1 . ..Ak1 [ (Ak \ M)Ak \ MAk+1 . ..Ap.
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 19
We have that min(Ak1 [ (Ak \ M)) = minAk1 < max Ak = max Ak \ M. Also
min(Ak \ M) min(Uk \ M) < max Ak+1. Then ~ais increasing and uniquely
determines a decreasing partition ~bsuch that ~a ~bis a SCP. In particular, b *
*can
be obtained from ~bby successively shifting ~ to the left. Since min(Mk1 \ M)
minMk1 > max Ak, the operator Rk1Mk1\Mis defined and we obtain
~u= Rp1Mp1.R.k.MkRk1Mk1\MRk2Mk2.R.1.M1(~a).
Then ~u v is a CP related to ~a ~b. Therefore (u  ~u) v 2 ker(@ 1 + 1 @) P*
* .
By ``mirror symmetry'' the case of u dr(v) is entirely analogous and the proo*
*f is
complete.
4. Diagonals on the Associahedra and Multiplihedra
The diagonal P on C*(Pn+1) descends to diagonals J on C*(Jn+1) and K
on C*(Kn+2) under the cellular projections ß : Pn+1 ! Jn+1 and ` : Pn+1 ! Kn+2
discussed in Section 2 above. This fact is an immediate consequence of Proposit*
*ion
5.
Definition 9. Let f : W ! X be a cellular map of CWcomplexes, let W be
a diagonal on C*(W ) and let X(r)denote the rskeleton of X. A kcell e W
is degenerate under f if f(e) X(r)with r < k. A component a b of W is
degenerate under f if either a or b is degenerate under f.
Let us identify the nondegenerate cells of Pn+1 under ß and `.
Definition 10. Let A1 . ..Ap be a partition of n_+_1_with p > 1 and let 1 k*
* <
p. The subset Ak is exceptional if for k < j p, there is an element ai,j2 Aj *
*such
that minAk < ai,j< max Ak.
Proposition 4. Given a face e of Pn+1, consider its unique representation as a
partition A1 . ..Ap of n_+_1_or as a composition of face operators
d(0,`)d(ip11,`p11)...(ip1sp1,`p1sp1).d.(.i11,`11)...(i1s1,`1*
*s1)(en).
(1) The following are all equivalent:
(1a) The face e is degenerate under ß.
(1b) minAj > min(Aj+1[ . .[.Ap) with Aj exceptional for some j < p.
(1c) ik1> 0 and sk > 1 for some k < p.
(2) The following are all equivalent:
(2a) The face e is degenerate under `.
(2b) Aj is exceptional for some j < p.
(2c) sk > 1 for some k < p.
Proof.Obvious.
Example 7. The subset A1 = {13}in the partition 1324 is exceptional; the face
e of P4 corresponding to 1324 is degenerate under `. In terms of compositions *
*of
20 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
face operators, e corresponds to d(0,2)d(0,1)(2,1)(4_)with s1 = 2. Furthermore,*
* since
i11= 0 (or equivalently minA1 < minA2) the face e is nondegenerate under ß.
Next, we apply Tonks' projection and obtain an explicit formula for the diago*
*nal
K on the associahedra.
Proposition 5. Let f : W ! X be a surjective cellular map and let W be
a diagonal on C*(W ). Then W uniquely determines a diagonal X on C*(X)
consisting of the nondegenerate components of W under f. Moreover, X is the
unique map that commutes the following diagram:
C*(W ) W! C*(W ) C*(W )
f # # f f
C*(X) ! C*(X) C*(X) .
X
Proof.Obvious.
In Section 2 we established correspondences between faces of the associahedron
Kn+2 and PRT's with n + 2 leaves and between faces of the permutahedron Pn+1
and PLT's with n + 2 leaves. Consequently, a face of Kn+2 can be viewed as a fa*
*ce
of Pn+1 by viewing the corresponding PRT as a PLT.
Definition 11. For n 0, let P be the diagonal on C*(Pn+1) and let ` : Pn+1 !
Kn+2 be Tonks' projection. View each face e of the associahedron Kn+2 as a face
of Pn+1 and define K : C*(Kn+2) ! C*(Kn+2) C*(Kn+2) by
K (e) = (` `) P (e).
Corollary 1. The map K given by Definition 11 is the diagonal on C*(Kn+1)
uniquely determined by P .
Proof.This is an immediate application of Proposition 5.
We note that both components of a CP u v are nondegenerate under ` if and
only if u v is associated with a SCP a b such that b is nondegenerate and
u = Rp1Mp1.R.1.1(a)with each Mj having maximal cardinality.
Choose a system of generators en 2 Cn (Kn+2), n 0. The signs in formula
(4.1) below follow from formula (6.12) in Section 6.
Definition 12. Define K e0 = e0 e0. Inductively, assume that K : C*(Ki+2) !
C*(Ki+2) C*(Ki+2) has been defined for all i < n and define
(4.1) X
K (en)= (1)ffld(ip1,`p1).d.(.i1,`1) d(i0q1,`0q1).d.(.i01,`01)(e*
*n, en)
0 p p+q=n+2
where
p1X q1X
ffl = ij(`j+ 1) + (i0k+ k + q)`0k,
j=1 k=1
and lower indices (i1, `1), . .,.(ip1, `p1); (i01,,`01).,.i.0q1,r`0q1ange *
*over all
solutions of the following system of inequalities:
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 21
8 9
>>>1 i0j< i0j1 n + 1 (1)>>
>>> >>>
>< 1 `0j n + 1  i0j `0(j1) (2)>>=
(4.2) > 0
>>>0 ik 0min ir, itk `(o0(tk))(3)>>>
>>> o (tk)>>
: 1 `k = fflk  ik  ` >;
(k1), (4) 11k p1j q1
where
{ffl1 < . .<.fflq1}= {1, . .,.n}\ i01, . .,.i0q1;
ffl0 = `0 = `00= ip = i0q= 0;
i0 = i00= fflq = `(p)= `0(q)= n + 1;
P u
`(u)= j=0`j for 0 u p;
P u
`0(u)= k=0`0kfor 0 u q;
n o
tu = min r  i0r+ `0(r) `0(o(u))> fflu;> i0r
o (u)= max {r  i0r fflu}; and
o0(u)= max {r  fflr .i0u}
Multiplicatively extend K to all of C*(Kn+2) using the fact that each cell of *
*Kn+2
is a product of cells Ki+2 with i < n.
Theorem 2. The map K given by Definition 12 is the diagonal induced by `.
Proof.If v = Lfi(v0) is nondegenerate in some component u v of P , then so *
*is
v0, and we immediately obtain inequality (1) of (4.2). Next, each nondegenerat*
*e de
creasing b uniquely determines a SCP a b. Although a may be degenerate, there is
a unique nondegenerate u = RMp1 . .R.M1(a) obtained by choosing each Mj with
maximal cardinality (the case Mj = ? for all j may nevertheless occur); then u *
*b is
a nondegenerate CP associated with a b in P . As a composition of face operat*
*ors,
straightforward examination shows that u has form u = d(ip1,`p1).d.(.i1,`1)(e*
*n)
and is related to b = d(i0q1,`0q1).d.(.i01,`01)(en)by
0
ik = min ir, it  `(o0(tk)), 1 k < p;
o0(tk) 0 factors and define V 0=
R; then T V = n 0V n and T aV (respectively, T cV ) denotes the free tensor
algebra (respectively, cofree tensor coalgebra) of V. Given Rmodules V1, . .,.*
*Vn
and a permutation oe 2 Sn, define the permutation isomorphism oe : V1 . . .Vn !
Voe1(1) . . .Voe1(n)by oe(x1. .x.n) = xoe1(1).x.o.e1(n), where the sign *
*is
determined by the Mac Lane commutation rule [14] to which we strictly adhere. In
particular, oem : (V1 V2) m ! V1 m V2 m is the permutation isomorphism
induced by oem = (1 3 . . .(2m  1)2 4 . .2.m). If f : V p ! V q is a map,
we let fi,npi= 1 i f 1 npi : V n ! V np+q, where 0 i n 
p. The abbreviations dgm, dga,and dgc stand for differential graded Rmodule, dg
Ralgebra and dg Rcoalgebra, respectively.
We begin with a review of A1 (co)algebras paying particular attention to the
signs. Let A be a connected Rmodule equipped with operations {'k 2
Homk2 A k, A }k 1. For each k and n 1, linearly extend 'k to A n via
nkX
'ki,nki: A n ! A nk+1 ,
i=0
and consider the induced map of degree 1 given by
nkX __ n __ nk+1
" 'k # ki,nki: Ä ! Ä .
i=0
__
Let eBA = T c Ä and define a map dBeA: eBA ! eBA of degree 1 by
X
(5.1) dBeA= " 'k # ki,nki.
1 k n
0 i nk
The identities (1)[n=2]" n # n = 1 n and [n=2]+[(n + k)=2] nk +[k=2](mod 2)
imply that
X [(nk)=2]+i(k+1)
(5.2) dBeA= (1) " nk+1 'ki,nki# n .
1 k n
0 i nk
Definition 13. (A, 'n)n 1is an A1 algebra if d2eBA= 0.
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 23
Proposition 6. For each n 1, the operations {'n} on an A1 algebra satisfy the
following quadratic relations:
X `(i+1)
(5.3) (1) 'n`'`+1i,n`1i= 0.
0 ` n1
0 i n`1
Proof.For n 1,
X [(nk)=2]+i(k+1)
0= (1) " 'nk+1 # nk+1 " nk+1 'ki,nki# n
1 k n
0 i nk
X nk+i(k+1)
= (1) 'nk1'ki,nki
1 k n
0 i nk
X `(i+1)
=  (1)n (1) 'n`'`+1i,n`1i.
0 ` n1
0 i n`1
It is easy to prove that
i j
Proposition 7. Given an A1 algebra (A, 'n)n 1, eBA, dBeAis a dgc.
Definition 14.iLet (A,j'n)n 1be an A1 algebra. The tilde bar construction on A
is the dgc eBA, dBeA.
Definition 15. Let A and C be A1 algebras. A chain map f = f1 : A ! C is a
map of A1 algebras if there exists a sequence of maps {fk 2 Homk1 A k, C }k 2
such that i j n
ef= P n 1 P k 1 " fk # k : eBA ! eBC
is a dgc map.
Dually, consider a sequence of operations {_k 2 Homk2 A, A k }k 1. For each
k and n 1, linearly extend each _k to A n via
n1X
_ki,n1i: A n ! A n+k1 ,
i=0
and consider the induced map of degree 1 given by
n1X __ n __ n+k1
# k _k "i,n1i: # A ! # A .
i=0
__
Let eA = T a # A and define a map deA : eA ! eA of degree 1 by
X
deA = # k _k "i,n1i,
n,k 1
0 i n1
which can be rewritten as
X [n=2]+i(k+1)+k(n+1)
(5.4) deA = (1) # n+k1 _ki,n1i" n .
n,k 1
0 i n1
24 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
Definition 16. (A, _n)n 1is an A1 coalgebra if d2eA= 0.
Proposition 8. For each n 1, the operations _k on an A1 coalgebra satisfy
the following quadratic relations:
X `(n+i+1)
(5.5) (1) _`+1i,n`1i_n` = 0.
0 ` n1
0 i n`1
Proof.The proof is similar to the proof of Proposition 6 and is omitted.
Again, it is easy to prove that
i j
Proposition 9. Given an A1 coalgebra (A, _n)n 1, eA, deA is a dga.
Definition 17. Leti(A, _n)nj1be an A1 coalgebra. The tilde cobar construction
on A is the dga eA, deA .
Definition 18. Let A and B be A1 coalgebras. A chain map g = g1 : A ! B is a
map of A1 coalgebras if there exists a sequence of maps {gk 2 Homk1 A, B k }k*
* 2
such that
P iP k k j n
(5.6) eg= n 1 k 1 # g " : eA ! eB,
is a dga map.
The structure of an A1 (co)algebra is encoded by the quadratic relations amo*
*ng
its operations (also called ``higher homotopies''). Although the ``direction,'*
*' i.e.,
sign, of these higher homotopies is arbitrary, each choice of directions determ*
*ines a
set of signs in the quadratic relations, the ``simplest'' of which appears on t*
*he algebra
side when no changes of direction are made; see (5.1) and (5.3) above. Interest*
*ingly,
the ``simplest'' set of signs appear on the coalgebra side when _n is replaced *
*by
(1)[(n1)=2]_n, n 1, i.e., the direction of every third and fourth homotopy *
*is
reversed. The choices one makes will depend on the application; for us the appr*
*o
priate choices are as in (5.3) and (5.5).
Let A1 = n 2C*(Kn) and let (A, 'n)n 1be an A1 algebra with quadratic
relations as in (5.3). For each n 2, associate en2 2 Cn2 (Kn)with the opera*
*tion
'n via
(5.7) en2 7! (1)n'n
and each codimension 1 face d(i,`)en2 2 Cn3 (Kn)with the quadratic compo
sition
n2 n` `+1
(5.8) d(i,`)e 7! ' 'i,n`1i.
Then (5.7) and (5.8) induce a chain map
n
(5.9) iA : A1  ! n 2Hom* A , A
representing the A1 algebra structure on A. Dually, if (A, _n)n 1is an A1 coa*
*lge
bra with quadratic relations as in (5.5), the associations
n2 `+1 n`
en2 7! _n and d(i,`)e 7! _i,n`1i_
induce a chain map
n
(5.10) ,A : A1  ! n 2Hom* A, A
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 25
representing the A1 coalgebra structure on A. The definition of the tensor pro*
*duct
is now immediate:
Definition 19. Let A and B be A1 algebras with structural representations iA a*
*nd
iB . The tensor product A B is the A1 algebra whose structural representation
iA B is the sum of the compositions
C*(Kn) iAB! Hom((A B) n , A B)
K # " (oen)*
C*(Kn) C*(Kn) i! Hom(A n , A) Hom (B n , B),
A iB
where (oen)*= Hom(oen, A B), n 2; the operations on A B are
n2 * n2
iA B e = (oen)(iA iB )K e n 2 .
Similarly, let A and B be A1 coalgebras with structural representations ,A and
,B . The tensor product A B is the A1 coalgebra whose structural representat*
*ion
,A B is the sum of the compositions
C*(Kn) ,AB! Hom(A B, (A B) n )
K # " (oe1n)*
C*(Kn) C*(Kn) ,! Hom(A, A n ) Hom (B, B n ),
A ,B
where oe1n*= Hom A B, oe1n, n 2; the operations on A B are
n2 1 n2
,A B e = oen *(,A ,B )K e n 2 .
Example 9. Let (A, _n)n 1be an A1 coalgebra. The following operations appear
on A A:
_1A A= _1 1 + 1 _1
_2A A= oe2 _2 _2 ,
_3A A= oe3 _20_20 _3 + _3 _21_20,
_4A A= oe4 _20_20_20 _4 + _4 _22_21_20+ _30_20 _21_30
+_30_20 _31_20+ _21_30 _31_20 _20_30 _22_30
.. .
. ..
Whereas K is homotopy coassociative, the tensor product only iterates up to
homotopy. Furthermore, given an arbitrary family of operations {'n 2 Hom(A n ,
A)}, one can form the quadratic compositions in (5.8) and make the same formal
identifications with the codimension 1 faces of the associahedra that one would
make if they were A1 algebra operations. Since Definition 19 makes sense wheth*
*er
or not the quadratic relations inn(5.3) hold,iwe may apply Definition 19 to the*
* 'n's
n jo
and obtain iterated operations n 2 Hom A k , A k . The n's define an
26 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
A1 algebra structure on A k whenever d2~BA k= 0. We make extensive use of this
fact in the sequel [16].
6. Permutahedral Sets
This section introduces the notion of permutahedral sets, which are combina
torial objects generated by permutahedra and equipped with the appropriate face
and degeneracy operators. Naturally occurring examples include the double cobar
construction, i.e., the cobar construction on Adams' cobar construction [1] with
coassociative coproduct [2], [3], [10] (see Subsection 6.5 below). Permutahedra*
*l sets
are similar in many ways to simplicial or cubical sets with one crucial differe*
*nce:
Whereas structure relations in simplicial or cubical sets are strictly quadrati*
*c, per
mutahedral sets have higher order structure relations. We note that the exposit*
*ion
on polyhedral sets by D.W. Jones [9] makes no mention of structure relations.
6.1. Singular Permutahedral Sets.
To motivate the notion of a permutahedral set, we begin with a construction
of our universal example~singular permutahedral sets. For 1 p n, let p_=
{1, . .,.p}and _p= {n  p + 1, . .,.n}, i.e., the first p and last p elements_o*
*f n_,
respectively. Note that _p= {q, . .,.n}when p + q = n + 1. Define 0_= 0= ?. If M
is a nonempty set, let @M denote its cardinality and define @? = 0. The induct*
*ive
procedure for labeling the (n  1)faces of Pn+1 given in Section 2 is convenie*
*ntly
expressed in the following settheoretic terms:
_Face_of_Pn+1_Label________

en1n,0 n_n + 1

en1n,1 n + 1n_

AB x I0,@B AB [ {n + 1}

AB x I@B,1 A [ {n + 1}B.

For 1 p < n, let
Qp(n) = partitionsAB ofn_ p_ A orp_ B
Qp(n) = {partitionsAB ofn_ _p A or_p B},
Qqp(n)= Qp(n) [ Qq(n), where p + q = n + 1,
For 1 r n and r + s = n + 1, define canonical projections
r,s: Pn ! Pr x Ps,
mapping each face AB 2 Qsr(n) homeomorphically onto the (n  2)product cell
æ _____ _____ _
A \ s  1 B \ s  1x sAB 2 Qs(n),
r_x A \ r__1_ B \ r__1_AB 2 Qr(n),
and each face AB 62 Qsr(n) onto the (n  3)product cell
_____ _____
A \ s  1 B \ s  1x A \ r__1_ B \ r__1_,
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 27
_____ _____
where A \ s  1 B \ s  1is a particular partition of r_and A \ r__1_ B \ r_*
*_1_is
a particular partition of _s(see Figures 7 and 8).
312 12 x 32
_____________oo o_____________o
132   231  
   
  2,2  
o 123 o ________ 12x 23  12 x 23  21x 23
   
   
123   213  
_____________oo o_____________o
123 12 x 23
Figure 7: A canonical projection on P3.
o________________o o_______________o
QQ Q QQ Q
 Q o  Q Qo  Q  Q Q
o____QQ__________o Q  Q Q  Q
  Q o_______________oQQ  Qo________________oQQ
o oQ  o oQ  o_______  ______o 
QQ Q  QQ  Q     
 Q o Q o  Q o Qo    
         
  ________________  _________________
________o_____ o ________ o______ o
oQ   oQ   oQ  oQ 
Q   Q   Q  Q 
Qo  Qo  Q  Q 
Q  Q  Q  Q 
QQo_______________oQQ QQo________________oQQ
2,3
1234 ______________ 12 x 234
 
3,2  1 x 2,2
 
? ?
123 x 34 ______________ 12 x 23 x 34
2,2x 1
o________________o o_______________o
QQ Q Q Q
 Q o  Q Qo  Q Q  Q Q
 QQ  Q  Q  Q
  Q o_______________oQQ  QQo________________oQQ
         
         
         
         
         
______________   ________  ______ 
oQ   oQ   oQ  oQ 
Q   Q   Q  Q 
Qo  Qo  Q  Q 
Q  Q  Q  Q 
QQo_______________oQQ QQo________________oQQ
Figure 8: Some canonical projections on P4.
28 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
Given an (n  1)face of AB Pn+1, choose a homeomorphism hAB : PrxPs !
AB. The singular coface operator associated with AB
ffiAB : Pn ! Pn+1
is the composition hAB O r,s: Pn ! Pr x Ps ! AB. Unlike the simplicial or
cubical case, ffiAB is not an inclusion in general. There are two kinds of sin*
*gular
codegeneracy operators
ffi, fij : Pn ! Pn1;
ffiis the cellular projection that identifies the faces i_n_\i_and n_\i_i_, 1*
* i n1;
and fij is the cellular projection that identifies the faces jn_\j and n_\jj,*
* 1 j n.
Note that ff1 = fi1 and ffn1 = fin; the projections fij were first defined by *
*R.J.
Milgram in [15] and denoted by Dj.
Definition 20. Let Y be a topological space. The singular permutahedral set of Y
is a tuple (SingP*Y, dAB, %i, &j) in which
SingPn+1Y = {continuous mapsPn+1 ! Y }, n 0,
singular face operators
dAB : SingPn+1Y ! SingPnY
are defined by
dAB(f) = f O ffiAB
for each AB Pn+1 and singular degeneracy operators
%i, &j : SingPnY ! SingPn+1Y
are defined by
%i(f) = f O fii and&j(f) = f O ffj
for each 1 i n and 1 j n  1.
Pn1 _____Pr x P_____Pns
P P P 
P P P  f
dAB(f) P PPq ?
Y
Figure 9: A singular face operator
Although coface operators ffiAB : Pn ! Pn+1 need not be inclusions, the top *
*cell
of Pn is always nondegenerate under ffiAB (c.f. Definition 9). However, the t*
*op cell
may degenerate under compositions of coface operators ffiABffiCD : Pn1 ! Pn+*
*1.
For example, ffi1234ffi132: P2 ! P4 is a constant map, since ffi1234: P3 ! *
*P2 x
P2 ! P4 sends the 1face 132 to a vertex.
Definition 21. A quadratic composition of face operators dCDdAB acts on Pn+1
if the top cell of Pn1 is nondegenerate under the composition
ffiABffiCD : Pn1 ! Pn+1.
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 29
For comparison, compositions @i@j of face operators in a simplicial set always *
*act
on the nsimplex n and compositions dfflidffljof face operators in a cubical s*
*et always
act on the ncube In. When dCDdAB acts on Pn+1, assign the label dCDdAB to
the n  2 face ffiABffiCD (Pn1)(see Figure 10).
d21d132= d12d312 d312 d21d231= d21d312
_____________oo
d132  d231
 
 
d12d132= d21d12o3 123 o d21d213= d12d231
 
 
d123  d213
_____________oo
d12d123= d12d123 d123 d12d213= d21d123
Figure 10: Codimension 2 relations on P3.
It is interesting to note that singular permutahedral sets have higher order st*
*ructure
relations, an example of which appears in Figure 11 below. This rich structure
distinguishes permutahedral sets from simplicial or cubical sets whose structure
relations are strictly quadratic.
P2 x P1
i ii1 P P P
2,1 ii i P P Ph132
i i i P P P
i i i 1,1 h21 1,2 PPq
P2 _____P1 _____P1 x P1 _____P2 _____ P1 x P2 _____P3P3
ff1 h123
 H H J 
 H H d21d123d1234(fJd123d1234(f))  2,2
 H H J ?
 H H H J P2 x P2
&1d21d123d1234(f) = H H J 
 H H JJ^ d1234(f)  h1234
 d132d1234(f) H HHj ?
___________________________________________Y __________oeP4
f
Figure 11: The quartic relation &1d21d123d1234= d132d1234.
Now SingP Y determines the singular (co)homology of Y in the following way:
Form the ``chain complex'' (C*(SingP Y ), d) of SingP Y with
X
d = (1)rsgn(AB) dAB,
AB2Pr,s(n+1)
where sgn(AB) denotes the sign of the shuffle (A and B are ordered). Note that*
* if
f 2 C*(SingP4Y ) and d132d1234(f)6= 0, the component d132d1234(f)of d2(f) 2
C*(SingP2Y ) is not cancelled and d2 6= 0 (see Figure 11). Thus d is not a diff*
*erential
30 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
and (C*(SingP Y ), d) is not a complex in the classical sense. So form the quot*
*ient
P
C}*(Y ) = C* Sing Y =DGN,
where DGN is the submodule generated by the degeneracies; then C}*(Y ), dis the
complex of singular permutahedral chains on Y. The sequence of canonical cellul*
*ar
projections
Pn+1 ! In ! n
induces a sequence of homomorphisms
C*(SingY ) ! C*(SingIY ) ! C*(SingP Y ) ! C}*(Y )
whose composition is a chain map that induces a natural isomorphism
H*(Y ) H}*(Y ) = H*(C}*(Y ), d).
Although the first two terms in the sequence above are nonnormalized chain com
plexes of singular simplicial and cubical sets, the map between them is not a c*
*hain
map. In general, a cellular projection between polytopes induces a chain map be
tween corresponding singular complexes if one uses normalized chains in the tar*
*get.
This does not cause a problem here, however, since df = fd and d2 = 0 are indep*
*en
dent. Finally, we note that SingP Y also determines the singular cohomology ring
of Y since the diagonal on the permutahedra and the AlexanderWhitney diagonal
on the standard simplex commute with projections.
6.2. Abstract Permutahedral Sets.
We begin by identifying each (n  k)face A1 . ..Ak+1 of Pn+1 with a compos*
*i
tion of face operators dM2k1M2k. .d.M1M2acting on Pn+1. First make the ident*
*i
fications AB $ dAB (see Figure 10), where AB ranges over the (n  1)faces of
Pn+1 (see Section 2). Motivated by Definition 21, the conditions under which a *
*qua
dratic composition dCDdAB acts on Pn+1 can be stated in terms of set operatio*
*ns,
which we now define. Given a nonempty ordered set M = {m1 < . .<.mk} Z,
let IM : M ! @M__be the index map mi7! i; for z 2 Z let M +z = {m1+z < . .<.
mk + z} with the understanding that addition takes preference over set operatio*
*ns.
Now think of Pn+1 as the ordered set n_+_1_= {1 < . .<.n + 1}.
Definition 22. Given nonempty disjoint subsets A, B n_, define the lower and
upper disjoint unions
æ
At_B = In_ØA(B)I+ @A  1 [ @A_,ifminB = min(n_ØA)
n_ØA(B) + @A i1,fminB > min(n_ØA);
and æ ___
A__tB = In_ØB(A)I[ @B  1,ifmax A = max (n_ØB)
n_ØB(A), ifmax A < max (n_ØB).
If either A or B is empty, define At_B = A__tB = A [ B.
In particular, if AB is a partition of n_, then
At_B = A__tB = n__1_.
Given a partition A1 . ..Ak+1 of n_+_1_, define A(0)= A[k+2]= ?; inductively,
given A(j), 0 j k, let
A(j+1)= A(j)t_Aj+1;
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 31
and given A[j], 2 j k + 2, let
A[j1]= Aj1__tA[j].
And finally, for 1 j k + 1, let
A(j)= A1 [ . .[.Aj.
Now to a given (n  k)face A1 . ..Ak+1 of Pn+1, assign the compositions of f*
*ace
operators
dA(k)A(k1)t_(n+1_\A(k)).d.A.(1)A(0)t_(n+1_\A(1))
(6.1) = dA(1)_tA[3]A[2].d.A.(k)_tA[k+2]A[k+1]
and denote either composition by dA1...Ak+1.
Note that both sides of relation (6.1) are identical when k = 1, reflecting t*
*he
fact that each (n  1)face is a boundary component of exactly one higher dimen
sional face (the top cell of Pn+1). On the other hand, each (n  2)face ABC *
*is
a boundary component shared by exactly two (n  1)faces. Consequently, ABC
can be realized as a quadratic composition of face operators in two different w*
*ays
given by (6.1) with k = 2:
(6.2) dAt_BAt_CdAB[C = dA__tCB__tCdA[BC.
Example 10. In P8, the 5face ABC_= 12345678_= 12345678\12345678. Since
At_B = {1234}, At_C = {567}, At C = {12} and Bt C = {34567}, we obtain the
following quadratic relation on 12345678 :
d1234567d12345678= d1234567d12345678;
similarly, on 34512678 we have
d1234567d34512678= d3456712d12345678.
Similar relations on the six vertices of P3 appear in Figure 10 above.
GivenPa sequence of (not necessarily distinct) positive integers {nj}1 j ksuch *
*that
n = nj, let
Pn1,...,nk(n) = {partitionsA1 . ..Ak ofn_ @Aj = nj}.
Theorem 3. Let AB 2 Pp,q(n + 1)and CD 2 P**(n). Then dCDdAB denotes
an (n  2)face of Pn+1 if and only if CD 2 Qqp(n).
Proof.If dCDdAB denotes an (n  2)face, say XY Z, then according to relati*
*on
(6.2) we have either
AB = X Y [Z and CD = Xt_Y Xt_Z
or __ __
AB = X [ Y Zand CD = Xt Z Y tZ.
Hence there are two cases.
Case_1:_AB = XY [ Z. If min Y = min Y [ Z, then p_ Xt_Y ; otherwise
minY [ Z = minZ and p_ Xt_Z. In either case, CD= Xt_Y Xt_Z 2 Qp(n).
Case_2:_AB = X [ Y Z. If max X = max X_[_Y, then _q X__tZ; otherwise
max (X [ Y ) = max Y and _q Y tZ. In either case, CD=
32 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
X__tZY __tZ 2 Qq(n).
Conversely, given AB 2 Pp,q(n + 1) and CD 2 Qqp(n), let
8
< AS (C)S (D), CD 2 Qp(n)
[AB; CD] = :
T (C)T (D)B, CD 2 Qq(n),
where
S (X)= I1B q_\ X  p + 1and T (X) = I1A p_\ X .
A straightforward calculation shows that
[XY [ Z; Xt_Y Xt_Z]= XY Z = [X [ Y Z; X__tZ Y __tZ].
Consequently, if XY Z = [AB; CD], either
AB = X Y [ Z andCD = Xt_Y Xt_Z
when CD 2 Qp(n) or
AB = X [ Y Zand CD = X__tZ Y __tZ
when CD 2 Qq(n).
On the other hand, if CD 62 Qqp(n), higher order structure relations involving*
* both
face and degeneracy operators appear.
We are ready to define the notion of an abstract permutahedral set (c.f. [9]*
*).
The relations in an abstract permutahedral set are settheoretic analogues of t*
*hose
in the singular case. For purposes of applications, only relation (6.3) is esse*
*ntial;
the other relations may be assumed modulo degeneracies.
Definition 23. Let Z = {Zn+1}n 0 be a graded set together with face operators
dAB : Zn+1 ! Zn
for each AB 2 P**(n + 1)and degeneracy operators
%i, &j : Zn ! Zn+1
for each 1 i n + 1, 1 j n such that %1 = &1 and %n+1 = &n. Then
Z, dAB, %i, &jis a permutahedral set if the following structure relations hol*
*d:
For all ABC 2 P***(n + 1)
(6.3) dAt_BAt_CdAB[C = dA__tCB__tCdA[BC.
For all AB 2 Pr,s(n + 1)and CD 2 P**(n)\ Qsr(n)
(6.4) dCDdAB = &jdMN dKLdAB where
8
>>>KL = n_Ø (r_\ D)r_\ D,
>>>MN = C__t(r_\ D) (DØ (r_\ D))_t(r_\ D),
>> or
>>>KL = r_\ Cn_Ø (r_\ C),
>>>
>: MN = (r_\ C)t_(CØ (r_\ C)) (r_\ C)t_D,
j = @ (r_\ C)when r 2 D.
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 33
For all AB 2 P**(n + 1)and 1 < j < n (for j = 1, n see (6.6) below)
(6.5) 8
>><1, ifA = j_orB = j_,
&jdjn_Øj, ifAB 2 Qj(n + 1), A 6= j_orB 6= j_,
dAB&j = > _ _ n+1j
>:&j1dj1_n_Øj1_,ifAB 2 Q (n + 1), A 6= j_orB 6= j_,
&j&jdMN dKL, ifAB =2Qn+1jj(n + 1)where
8 __ __
>>>KL = At j_\ B  BØ j_\ B t j_\ B ,
>>>MN = @ j \ A n__1_Ø@ j \ A ,
>> or
>>>KL = j\ A t j\ B  j \ A tB,
>>> _ __ _ _ __
>:MN = j__1_n__1_Øj__1_,
when j 2 B.
For all AB 2 P**(n + 1)and 1 i n + 1
æ
(6.6) dAB%i= 1,% ifA = {i}or B = {i},
jdCD,where
8
>>>CD = In+2_Øi(AØi)In+2_Øi(B),
> or
>>>CD = In+2Øi(A) In+2Øi(BØi) ,
: j = I ___ ___
B (i)+ @A when {i}$ B.
For all i j
%i%j = %j+1%i,
(6.7) &i&j&= &j+1&i,
i%j = %j+1&i,
%i&j = &j+1%i.
6.3. The Cartesian product of permutahedral sets.
Let Z0 = {Z0r, d0AB, &0i, %0j} and Z00= {Z00s, d00AB, &00i, %00j} be permut*
*ahedral sets
and let ( ) ,
[
Z0x Z00= (Z0x Z00)n = Z0rx Z00s ~ ,
r+s=n+1 n 1
where (a, b)~ (c, d)if and only if a = &0r(c) and d = &001(b), i.e.,
(&0r(c), b) = (c, &001(b)) for all(c, b) 2 Z0rx Z00s.
Definition 24. The product of Z0and Z00, denoted by Z0xZ00, is the permutahedral
set
Z0x Z00, dAB, &i, %j
with face and degeneracy operators defined by
8 i j
>>< d0r (a), b, ifAB 2 Qs(n),
i _\Ar_\B j
(6.8) dAB(a, b) = > a, d00 (b),ifAB 2 Qr(n),
>: s_\(An+s) s_\(Bn+s)
&idMN dKL (a, b), otherwise, where
34 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
8
>>>KL = r_\ A (r_\ B)[ s__1_+ r
>>>MN = (r_\ A)t_(BØ (r_\ B)) (r_\ A)t_B
>> or
>>>KL = A [ (BØ (r_\ B))r_\ B
>>> __ __
>:MN = At (r_\ B) (BØ (r_\ B))t(r_\ B)
i = @A + @ (r_\ B) 1 when r 2 A;
æ 0
(6.9) &i(a, b)= (&i(a),ab),, &010 i < r,
, ir+1(b)r i n;
æ 0
(6.10) %j(a, b)= %j(a),ab,, %001 j r,
jr+1(b),r < j n + 1.
Remark 1. Note that the righthand side of the third equality in (6.8) reduces *
*to
the first two; indeed, if r 2 B, then KL 2 Qs(n) and MN 2 Qr(n); if r 2 A,
KL 2 Qs(n) and MN 2 Qr(n) if m2_+ r  1 A \ (r__1_\ A), m2 = @(r_\ B),
while for m2_+ r  1 6 A \ (r__1_\ A) one has KL 2 Qs(n), MN 62 Qr(n) and
r  1 2 L.
Example 11. The canonical map ' : SingP X x SingP Y ! SingP (X x Y ) defined
for (f, g) 2 SingPrX x SingPsY by
'(f, g) = (f x g) O r,s
is a map of permutahedral sets. Consequently, if X is a topological monoid, the
singular permutahedral complex SingP X inherits a canonical monoidal structure.
6.4. The diagonal on a permutahedral set.
Let Z = (Zn+1, dAB, &i, %i) be a permutahedral set. The explicit diagonal
: C*(Z) ! C*(Z) C*(Z)
defined for a Zn+1 is given by the formula
X
(6.11) (a) = ffl . du(a) dv(a),
u v2 p,q
p+q=n+2
where the sign ffl is defined as follows: For an (nm)face u = A1 . ..Am+1 *
* Pn+1,
define Y (i)
sgn u = (1)@A sgn(A(i)A(i1)t_(n_+_1_\ Ai)).
1 i m
If u v is a complementary pair, consider the related strong complementary pair
ux vx, where x is the vertex of Pn+1 defined by max ux = x = minvx. The cellular
projection OE : Pn+1 ! Kn+2 ! In, i.e., Tonks' projection followed by the ``hea*
*ling
map,'' preserves diagonals in the following way: For a vertex x 2 Pn+1, define *
*a func
tion g : {vertices ofPn+1}! {vertices ofPn+1 that coincide with thoseIofn}by
g(x) = minIn(x),
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 35
where In(x) In denotes the minimal n(x)dimensional face of In containing x, i*
*.e.,
if x = a1 . ..an+1 then g(x) can be obtained from x as the composition gn . .*
*g.2(x)
where 8
< b1 . ..^bn+2j . ..bi+1bn+2jbi . ..bn+1,
gj(b1 . ..bn+1) = : ifbn+1j, bn+3j, . .,.bi+1< bn+2j < bi
1, otherwise.
Assign ffl0 to the vertex y of Pn+1 that coincides with the vertex of In determ*
*ined
by
ffl0(y) = sgn(u0y) . sgn( OE(u0y), OE(vy). sgn(vy),
where u0y vy is a CP related to the SCP uy vy at vertex y, i.e., max uy = y =
minvy, u0y= RMp1 . .R.M1(uy) where each Mj has maximal possible cardinality,
and sgn(OE(u0y), OE(vy)) is the sign of the shuffle, i.e., the sign of the orth*
*ogonal pair
OE(u0y) OE(vy) in the Serre diagonal on the cube. Define
(6.12) ffl = sgn u . ffl0(g(x)) . sgn v.
Remark 2. The components of (OE(u0y), OE(vy)) are nondegenerate under Tonks'
projection ` : Pn+1 ! Kn+2. Furthermore, the sign ffl defined above is compati
ble with the Serre diagonal on In since the components of (u, v) = (u0y, vy) are
nondegenerate under OE; thus ffl = sgn(u0y) . sgn(u0y) . sgn( OE(u0y), OE(vy).*
* sgn(vy) .
sgn(vy) = sgn( OE(u0y), OE(vy). Finally, while the sign ffl for P is geometric*
*ally
motivated, we leave the proof of this fact to the interested reader.
Remark 3. The composition of cellular maps
(1 x 2,2) . .(.1 x 2,n1) 2,n: Pn+1 ! In
is compatible with diagonals but does not factor through Kn+2; hence this compo*
*si
tion differs from OE.
6.5. The double cobarconstruction 2C*(X).
For a simplicial, cubical or a permutahedral set W, let C*(W ) denote the quo*
*tient
C*(W )=C>0(*), where * is a base point of W, and recall that a simplicial or cu*
*bical
set W is said to be kreduced if W has exactly one element in each dimension *
*k.
Let C denote the cobar construction on a 1reduced dg coalgebra C. In [10] and
[11], Kadeishvili and Saneblidze construct a functor from the category of 1red*
*uced
simplicial sets to the category of cubical sets and a functor from the category*
* of
1reduced cubical sets to the category of permutahedral sets for which the foll*
*owing
statements hold (c.f. [3], [2]):
Theorem 4. [10] Given a 1reduced simplicial set X, there is a canonical identi*
*fi
cation isomorphism
C*(X) C* ( X).
Theorem 5. [11] Given a 1reduced cubical set Q, there is a canonical identific*
*ation
isomorphism
C* (Q) C}*( Q).
For completeness, definitions of these two functors appear in the appendix.
Since the chain complex of any cubical set Q is a dg coalgebra with strict co*
*as
sociative coproduct, setting Q = X in the second theorem immediately gives:
36 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
Theorem 6. For a 2reduced simplicial set X there is a canonical identification
isomorphism
2C*(X) C}*( 2 X).
If X = Sing1Y, then C*(X) is Adams' cobar construction for the space Y [1].
Consequently, there is a canonical (geometric) coproduct on 2C*(Sing1Y ). In t*
*he
sequel [16] we show that this coproduct extends to an A1 Hopf algebra structur*
*e.
7.Appendix
For completeness, we review the definition of the functor from the category of
1reduced simplicial sets to the category of cubical sets and the definition of*
* the
functor from the category of 1reduced cubical sets to the category of permutah*
*edral
sets given by Kadeishvili and Saneblidze in [10], [11].
7.1. The cubical set functor X. Given a 1reduced simplicial set X = {Xn, @i,
si}n 0, define the graded set X as follows: Let Xc be the graded set of formal
expressions
Xcn+k= {jik. .j.i1ji0(x)  x 2 Xn}n 0;k 0,
where
ji0= 1, i1 . . .ik, 1 ij n + j  1, 1 j k,
and let X~c = s1(Xc>0) be the desuspension of Xc. Define 0X to be the free
graded monoid generated by X~cand denote elements of 0X by ~x1. .~.xk, where
xj 2 Xj, 1 j k. Define the (strictly associative) product of two elements
~x1. .~.xkand ~y1.y.~.`by concatenation ~x1. .~.xk~y1.~.y.`(there are no other *
*relations
whatsoever between these expressions). The total degree of an element ~x1. .~.x*
*kis
the sum m(k)= m1+. .+.mk, where mj = ~xj, and we write ~x1. .~.xk2 ( 0X)m(k).
Let X be the monoid obtained from 0X via
X = 0X/ ~ ,
_______ _____ _____
where jp+1(x). ~y~ ~x. j1(y)for x, y 2 Xc, x = p + 1, and jn(~x) ~ sn(x)for
x 2 X>0. Clearly, there is an inclusion of graded modules MX 0X, where MX
denotes the free monoid generated by ~X= s1(X>0).
Apparently 0X canonically admits the structure of a cubical set. Denote the
components of AlexanderWhitney diagonal by
i: Xn ! Xix Xni,
where i(x) = @i+1. .@.n(x) x @0. .@.i1(x), 0 i n, and let xn denote an
nsimplex simplex, i.e. xn 2 Xn. Then
i(xn) = ((x0)i, (x00)ni) 2 Xix Xni
for all n >_0._Define face_operators_d0i, d1i: ( X)n1 ! ( X)n2 on a (monoidal)
generator xn 2 (X~)n1 (Xc )n1 by
___ ____ _______
d0i(xn)= (x0)i. (x00)ni,1 i n  1
___ ______
d1i(xn)= @i(xn), 1 i n  1;
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 37
and extend to elements ~x1. .~.xk2 MX by
_____ ___________ __
d0i(_x1._._.xk)= __x1.(.x.0q)jq. (x00q)mqjq+1.x.k.,
_______ __
d1i(_x1._._.xk)= __x1.@.j.q(xq).x.k.,
where m(q1)< i m(q), jq = i  m(q1), 1 q k, 1 i n  1. Then the
defining identities for a cubical set that involve d0iand d1ican easily be chec*
*ked
on MX. In particular, the simplicial relations between the @i's imply the cubic*
*al
relations between d1i's; the associativity relations between i's imply the cub*
*ical
relations between d0i's, and the commutativity relations between @i's and j's *
*imply
the cubical relations between d1i's and d0j's. Next,_define_a degeneracy opera*
*tor
ji: ( X)n1 ! ( X)n on a (monoidal) generator __x2 (Xc )n1 by
_____
ji(__x) = ji(x);
and extend to elements ~x1. .~.xk2 X by
ji(__x1._._.xk)= __x1.j.j.q(__xq) . ._.xk,
jn (_x1._._.xk)= __x1._._.xmk1. jmk+1 (__xk),
where m(q1)< i m(q), jq = i  m(q1), 1 q k, 1 i n  1. Finally,
inductively extend the face operators on these degenerate elements so that the
defining identities of a cubical set are satisfied. Then in particular, we hav*
*e the
following identities for all xn 2 Xn:
___ _____ _______ _______ _______ ______
d01(xn)= (x0)1. (x00)n1= e . (x00)n1= (x00)n1= @0(xn),
___ _______ _____ _______ _______ _______
d0n1(xn)= (x0)n1. (x00)1= (x00)n1. e = (x0)n1= @n (xn).
It is easy to see that the cubical set { X, d0i, d1i, ji} depends functorially *
*on X.
7.2. The permutahedral set functor Q.
Let Q = (Qn, d0i, d1i, ji)n 0 be a 1reduced cubical set. Recall that the dia*
*gonal
: C*(Q) ! C*(Q) C*(Q)
on C*(Q) is defined on a 2 Qn by
(a) = (1)ffld0B(a) d1A(a),
where d0B= d0j1. .d.0jq, d1A= d1i1. .d.1ip, summation is over all shuffles {A, *
*B} =
{i1 < . .<.iq, j1 < . .<.jp} of n_and ffl is the sign of the shuffle. The primi*
*tive
components of the diagonal are given by the extreme cases A = ? and B = ?.
Define the graded set Q as follows: Let Qc*be the graded set of formal expre*
*s
sions
Qcn+k= {&ik. .&.i1&i0(a) a 2 Qn}n 0;k 0,
38 SAMSON SANEBLIDZE1 AND RONALD UMBLE2
where
&i0= 1, i1 . . .ik, 1 ij n + j  1, 1 j k,
and let ~Qc= s1(Qc>0) denote the desuspension of Qc. Define 0Q to be the free
graded monoid generated by ~Qc. Let Q be the monoid obtained from 0Q via
Q = 0Q/ ~ ,
_______ ____
where &p+1(a). ~b~ ~a. &1(b)for a, b 2 Qc, a = p + 1. Clearly, there is an in*
*clusion
of graded monoids MQ Q, where MQ denotes the free monoid generated by
~Q= s1(Q>0).
Then Q is canonically a permutahedral set in the following way: First,_for_a
monoidal generator ~a2 ~Q, define_the_degeneracy operator &iby &i(~a) = &i(a); *
*next,
for ~a2 ~Q ~Qcdefine %j(~a) = jj(a); and finally, if ~ais any other element of*
* Q~c
define its degeneracy accordingly to (6.7 ). Use formulas (6.9 ) and (6.10) to *
*extend
both degeneracy operators on decomposables. Now for ~a2 ~Qn+1 Q~cn+1, define
the face operator dAB by
_____ _____
dAB(~a) = d0B(a). d1A(a), AB 2 P*,*(n + 1),
while for other elements of Q~cand for decomposables in 0Q use formulas (6.4
)(6.6) and (6.8 ) to define dAB by induction on grading. In particular, we ha*
*ve
the following identities:
_____
din+1_\i(_a)= d1i(a),1 i n,
_____
dn+1_\ii(_a)= d0i(a),1 i n.
It is easy to see that ( Q, dAB, &i, %j) a permutahedral set, which depends fu*
*nc
torially on Q.
Remark 4. Note that the definition of Q uses all cubical degeneracies. This is
justified geometrically by the fact that a degenerate singular ncube in the ba*
*se of
a path space fibration lifts to a singular (n  1)permutahedron in the fibre, *
*which
is degenerate with respect to Milgram's projections. We must formally adjoin the
other degeneracies to achieve relations (6.4) (c.f., the definition of the cubi*
*cal set
X on a simplicial set X).
References
[1]J. F. Adams, On the cobar construction, Proc. Nat. Acad. Sci. (USA), 42 (19*
*56), 409412.
[2]H. J. Baues, The Cobar Construction as a Hopf Algebra, Invent. Math., 132 (*
*1998), 467489.
[3]G. Carlsson and R. J. Milgram, Stable homotopy and iterated loop spaces, Ha*
*ndbook of
Algebraic Topology (Edited by I. M. James), NorthHolland (1995), 505583.
[4]F. Chapoton, Algèbres de Hopf des permutahèdres, associahèdres et hypercube*
*s, Adv. in
Math. 150, No. 2, (2000), 264275.
[5]````````````, Bigèbres différentielles graduées associées aux permutoèdres,*
* associaè
dres et hypercubes, preprint.
[6]H.S.M. Coxeter, W.O.J. Moser, Generators and relations for discrete groups,*
* SpringerVerlag,
1972.
[7]Matthias R. Gaberdiel and Barton Zwiebach, Tensor Constructions of Open Str*
*ing Theories
I: Foundations, Nucl.Phys. B505 (1997), 569624.
[8]N. Iwase and M. Mimura, Higher homotopy associativity, Lecture Notes in Mat*
*h., 1370
(1986), 193220.
DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 39
[9]D. W. Jones, A general theory of polyhedral sets and corresponding Tcomple*
*xes, Disserta
tiones Mathematicae, CCLXYI, Warszava (1988).
[10]T. Kadeishvili and S. Saneblidze, A cubical model of a fibration, preprint,*
* AT/0210006.
[11]~~~~~~~, The twisted Cartesian model for the double path space fibration, p*
*reprint,
AT/0210224.
[12]T. Lada and M. Markl, Strongly homotopy Lie algebras, Communications in Alg*
*ebra 23
(1995), 21472161.
[13]J.L. Loday and M. Ronco, Hopf algebra of the planar binary trees, Adv. in *
*Math. 139, No.
2 (1998), 293309.
[14]S. Mac Lane, ``Homology,'' SpringerVerlag, Berlin/New York, 1967.
[15]R. J. Milgram, Iterated loop spaces, Ann. of Math., 84 (1966), 386403.
[16]S. Saneblidze and R. Umble, The biderivative and A1 Hopf algebras, preprin*
*t.
[17]J. R. Smith, ``Iterating the cobar construction,'' Memiors of the Amer. Mat*
*h. Soc. 109,
Number 524, Providence, RI, 1994.
[18]J. D. Stasheff, Homotopy associativity of Hspaces I, II, Trans. Amer. Math*
*. Soc., 108
(1963), 275312.
[19]A. Tonks, Relating the associahedron and the permutohedron, In ``Operads: P*
*roceedings of
the Renaissance Conferences (Hartford CT / Luminy Fr 1995)'' Contemporary Ma*
*thematics,
202 (1997), pp.3336
A. Razmadze Mathematical Institute, Georgian Academy of Sciences, M. Aleksidze
st., 1, 380093 Tbilisi, Georgia
Email address: sane@rmi.acnet.ge
Department of Mathematics, Millersville University of Pennsylvania, Millersvi*
*lle,
PA. 17551
Email address: Ron.Umble@Millersville.edu