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 (non-quadratic) 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 long-standing 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 point-of-view. 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. GM1-2083 of the U.S. Civilian* * Research and Development Foundation for the Independent States of the Former Soviet Union (C* *RDF) and by Award No. 99-00817 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 Jean-Louis 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 n-dimensional 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 j-level 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 n-s+3 Thus, Kn+2 is an n-dimensional convex polytope. | @ | | @ | @@ @ | | @ | @ ||o2| o 56 ! 256|1|34 @ |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 r-variables (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 [1|3|2, 13|2, 3|1|2] to the vertex on K4 represented by the parenthesization ((oo)(oo)). The permuta- tions 1|3|2 = d(1,1)d(0,1)and 3|1|2 = d(0,1)d(2,1)insert inner parentheses in t* *he oppo- site order; the partition 13|2 = 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: [12|4|3, 124|3, 4|12|3]= ((o o o)(oo)) [1|3|24, 13|24, 3|1|24]= ((oo)(oo)o) [1|4|23, 14|23, 4|1|23]= ((oo)o (oo)) [2|4|13, 24|13, 4|2|13]= (o (oo)(oo)) [1|34|2, 134|2, 34|1|2]= ((oo)(o o o)) [1|3|2|4, 13|2|4, 3|1|2|4]= (((oo)(oo))o) [2|4|3|1, 24|3|1, 4|2|3|1]= (o ((oo)(oo))) [1|2|4|3, 1|24|3, 1|4|2|3, 14|2|3,=4|1|2|3](((oo)o)(oo)) [1|3|4|2, 13|4|2, 3|1|4|2, 3|14|2,=3|4|1|2]((oo)((oo)o)) [1|4|3|2, 14|3|2, 4|1|3|2, 4|13|2,=4|3|1|2]((oo)(o)(oo)) [2|1|4|3, 2|14|3, 2|4|1|3, 24|1|3,=4|2|1|3]((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 (inner-most) parentheses as indicated by the 1-level m* *eets in M1; second, simultaneously insert all level 2 parentheses as indicated by the 2-level 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 k-fold 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 (non-nested) 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 256|1|34 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 one-to-one 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 n-cube. 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 en-1i,ffldenote* * the (n - 1)-face (x1, . .,.xi-1, ffl, xi+1, . .,.xn) In. For 0 i j 1, let I* *i,j= 1 - 2-i, 1 - 2-j I, where 2-1 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_________________________ | en-1n,0 |d(0,n) | en-1n,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),1||d(i1,`1)...(ik,`k)(n,1),ik + `k < n d(i|1,`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(0|o,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 o|Q |Q | |oQ |Q | | Q | Q | | Q | Q | | Q|o Q |o | Qo| Q|o | | | | | | | | | | | | | | |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 r-varia* *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_________L|abel__________________________ en-1n,0 |d(0,n) | en-1n,1 |d(n,1) | d(0,`1)...(ik,`k)x I0,n-kd|(0,`1)...(ik,`k) æ | d(0,`1)...(ik,`k)x In-k,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 left-most 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 left-most 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 p-leveled trees* * with n + 2 nodes whose p-level 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_________________ | en-1`,0 |d(0,`), 1 ` n | en-1n,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_____________o||1)(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,1|o) |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* *on-zero entries form a ``staircase path'' connecting the lower-left and upper-right cor* *ners; entries decrease when reading upward along a ``riser'' and increase when reading from left-to-right 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) ei-1,j-1= ei+1,j+1= 0 and either ei-1,j= 0 or ei,j+1= 0, exclu- sively. (b) If ei,j= ek,`then i = k and j = `. (c) If ei-1,j= 0 then ei,j< ei,j+1. (d) If ei,j+1= 0 then ei-1,j< ei,j. Definition 3. A partition A1| . .|.Ap of n_is increasing (resp. decreasing) if * *minAj < max Aj+1 (resp. max Aj-1 > 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 an1-1,1, and so on. Inductively, if the (j - 1)stcolumn has been filled wi* *th minAj-1 in row k, fill in the jth column from row k upward, beginning with anj,j first, then anj-1,j, and so on. This process terminates after p steps with the * *q x p step tableau E. For 1 i q, let Bi= {non-zero 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= {non-zero 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 one-to-one correspondence {Step tableaux}$ {Strong complementary pairings}. Example 3. The (4, 6)-SCP 179|3|48|256 9|7|138|46|5|2 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 right-shift ope* *rations on a and left-shift 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 non-empty subsets such that minM > max Ai+1 and max Bj-1 < minN. Define RiM(a)= A1| . .|.Ai\ M|Ai+1[ M| . .|.Ap DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 11 and LjN(b)= B1| . .|.Bj-1[ N|Bj\ 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 non-empty, 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 Rp-1Mp-1.R.1.M1and L2* *N2. . . LqNqsuch that u = Rp-1Mp-1.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 Rp-1Mp-1.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 {non-zero 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 = RMp-1 . .R.M1E. Now continue the induction as follows: For 1 k q - 1, assume that Ep+k-1 has been obtained. Since LkNkis defined, Nk Bq-k+1 = {non-zero entries in row k of Ep+k-1} and either minNk > max{row k + 1 of Ep+k-1} or Nk = ?. Define Ep+k = LNkEp+k-1 to be the tableau obtained from Ep+k-1 by shifting Nk down to row k + 1. The induction terminates with the tableau LNq-1. .L.N1RMp-1 . .R.M1E, referred to as a q x p derived tableau, and determines a (p, q)-CP with one of * *the following forms: RMp-1 . .R.M1(a) LN2 . .L.Nq(b),Mi6= ? and Nj 6= ? for some i, j RMp-1 . .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 one-to-one 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,n-p+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_|_| $ 14|25|3 4|15|23 |_4_|_|__| _________ |___|2_|3_| L? L? R{5}R? E = |_1_|_|5_| $ 14|2|35 4|15|23 |_4_|_|__| _________ |___|2_|3_| L{5}L? R? R? E = |_1_|_|__| $ 14|25|3 45|1|23 |_4_|5_|_| _________ |___|2_|3_| L{5}L? R{5}R? E = |_1_|_|__| $ 14|2|35 45|1|23 |_4_|_|5_| Up to sign, four components of P (5_)arise from E, namely, (14|2|35 + 14|25|3) (4|15|23 + 45|1|23). 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_)= 1|2|3 123+ 123 3|2|1 + 1|23 13|2+ 2|13 23|1 + 13|2 3|12+ 12|3 2|13 + 1|23 3|12+ 12|3 23|1. Note that each component in the right-hand column is the transpose of the compo- nent to its left. Example 6. Up to sign, P (4_) = 1234 4|3|2|1 +123|4 (3|2|14 + 3|24|1 + 34|2|1) +12|34 (2|14|3 + 24|1|3) +1|234 14|3|2 +23|14 (3|24|1 + 34|2|1) +13|24 (3|14|2 + 34|1|2) + (13|24 + 1|234 + 14|23 + 134|2) 4|3|12 + (12|34 + 124|3) (4|2|13 + 4|23|1) +3|124 34|2|1 +2|134 (24|3|1 + 4|23|1) +24|13 4|23|1 + (1|234 + 14|23) 4|13|2 +(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 non-empty subset M Ak, define a face operator dkM: Cn-p+1 (Pn+1)! Cn-p (Pn+1)by dkM(A1| . .|.Ap)= A1| . .|.Ak-1|M|Ak \ M| . .|.Ap; then (up to sign) the cellular boundary @ : Cn-p+1 (Pn+1)! Cn-p (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)= S1|S2, where S2 = n_+_1_\ S1Pand ranges over all non-emptyPproper subsetsPof n_+_1_. Thus, P @ (n_+_1)= P (S1)| P (S2)= (ui vj)| uk v` = ui|uk vj|v`, where ui vj and uk v` range over all CP's of partitions of S1 and S2, respectively. Note that although ui|uk vj|v`* * 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 one-to-one 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 vj|v` * *of partitions of n_+_1_. Hence 1 k ` k ` diUiU1| . .|.Ui[ U | . .|.U vj|v = ui|u vj|v 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 ui|uk V1| . .|.Vj [ V 1| . .|.V* * `of partitions of n_+_1_. Again, 1 ` k ` ui|uk djVjV1| . .|.Vj[ V | . .|.V= ui|u vj|v is a component of (1 @ + @ 1) P (n_+_1_)and the conclusion follows. 16 SAMSON SANEBLIDZE1 AND RONALD UMBLE2 Lemma 2. Each non-vanishing 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 = Rp-1Mp-1.R.1.M1(a)and let M be a proper non-empty 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 non-vanishing 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[ Mi-1)\Mifor 1 i p. Under the conditions above, dkM(u) v is a component of P (A1 [ . .[.Ak-1 [ M|(Ak \ M) [ Ak+1 [ . .[.Ap). In particular, a b = ap1|ap2 bq1|bq2where ap1= A1| . .|.Ak-2|Ak-1 [ (Ak \ M) and ap2= Ak\M|Ak+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 Mk-1 \ Mk and Mk Ak [ Mk-1 \ M. Let ~u= U1| . .|.Uk-1 [ M|Uk \ M| . .|.Up; then dk-1Uk-1(~u) = dkM(u). Furthermore, since min(Mk-1 \ M) minMk-1 > max Ak, we may replace Rk-1Mk-1 with Rk-1Mk-1\Mand obtain ~u= Rp-1Mp-1.R.k.MkRk-1Mk-1\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| . .|.Uk-1|M| (Uk \ M)[ Uk+1|Uk+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= Rp-1Mp-1.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 [ Mk-1) \ 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 Ai-1> 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| . .|.Ai-1[ 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 Ak-1 < max Ak = max (Ak \ M) and ~a= A1| . .|.Ai-1[ Ai\ ~|Ai+1| . .|.Ak \ M| (Ak \ M)[ ~|Ak+1| . .|.Ap is increasing and uniquely determines a SCP ~a ~b. Let ~u= U1| . .|.Ui-1[ Ui|Ui+1| . .|.M|Uk \ M|Uk+1| . .|.Up; note that ~ =2M [ Mj and ~ 2 Ms for i s j - 1. Thus u~= Rp-1Mp-1.R.k.MkRk-1Mk-1\~\MRk-2Mk-1\~.R.i.-1Mi\~Ri-2Mi-2.R.1.M1(~a) and ~u v is a CP related to ~a ~b. Finally, dkM(u)= di-1Ui-1(~u) so that (u - ~u) v 2 ker(@ 1 + 1 @) P . On the other hand, if 1 < i = k, s* *et ~a= A1| . .|.Ak-1 [ (Ak \ M)|Ak \ M|Ak+1| . .|.Ap and ~up= U1| . .|.Uk-1 [ M|Uk \ M|Uk+1| . .|.Up. Subcase_3A2_: Assume min Ai-1< max (Ai\ ~)with 1 i k. Again, first consider 1 i < k. Let ~a= A1|...|Ai-1|Ai\ ~|Ai+1|...|Ak \ M|(Ak \ M) [ ~|Ak+1|...|Ap and ~u= dkM(u) = U1| . .|.M|Uk \ M|Uk+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 minMk-1 = minMk-1\M = ~ > max Ak, both Rk-1Mk-1\~ and Rk(Mk-1\~)\Mare defined and we have ~u= Rp-1Mp-1.R.k.+1MkRk(Mk-1\~)\MRk-1Mk-1\~.R.i.Mi\~Ri-1Mi-1.R.1.M1(~a). Choose r such that ~ 2 Br and let ~v= V1| . .|.Vr-1|Vr [ Vr+1|Vr+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 \ M|Ak \ M|Ak+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 Ak-1 < 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, minAk-1 < 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| . .|.Ak-1|Ak \ Dk|Dk|Ak+1| . .|.Ap. Then ~ais increasing and uniquely determines a SCP ~a ~b. Since min{[(Ak \ Dk)[ Mk-1 \ M]} > ~ = max Dk, the operator Rk((Ak\Dk)[Mk-1)\Mis defined and we have RpMp-1. .R.k+1MkRk[(Ak\Dk)[Mk-1]\MRk-1Mk-1.R.1.M1(~a)= dkM(u). Choose r such that ~ 2 Br and let ~v= V1| . .|.Vr-1|Vr [ Vr+1|Vr+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 Ak-1 > max(Ak \ ~), 1 < k p. Let ~u= U1| . .|.Uk-1 [ M|Uk \ M| . .|.Up; then dk-1Uk-1(~u) = dkM(u). Let ~a= A1| . .|.Ak-1 [ (Ak \ M)|Ak \ M|Ak+1| . .|.Ap. DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 19 We have that min(Ak-1 [ (Ak \ M)) = minAk-1 < 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(Mk-1 \ M) minMk-1 > max Ak, the operator Rk-1Mk-1\Mis defined and we obtain ~u= Rp-1Mp-1.R.k.MkRk-1Mk-1\MRk-2Mk-2.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 CW-complexes, let W be a diagonal on C*(W ) and let X(r)denote the r-skeleton of X. A k-cell 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 non-degenerate 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(ip-11,`p-11)...(ip-1sp-1,`p-1sp-1).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 13|24 is exceptional; the face e of P4 corresponding to 13|24 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 non-degenerate 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 non-degenerate 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 non-degenerate under ` if and only if u v is associated with a SCP a b such that b is non-degenerate and u = Rp-1Mp-1.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(ip-1,`p-1).d.(.i1,`1) d(i0q-1,`0q-1).d.(.i01,`01)(e* *n, en) 0 p p+q=n+2 where p-1X q-1X ffl = ij(`j+ 1) + (i0k+ k + q)`0k, j=1 k=1 and lower indices (i1, `1), . .,.(ip-1, `p-1); (i01,,`01).,.i.0q-1,r`0q-1ange * *over all solutions of the following system of inequalities: DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 21 8 9 >>>1 i0j< i0j-1 n + 1 (1)>> >>> >>> >< 1 `0j n + 1 - i0j- `0(j-1) (2)>>= (4.2) > 0 >>>0 ik 0min ir, itk- `(o0(tk))(3)>>> >>> o (tk)>> : 1 `k = fflk - ik - ` >; (k-1), (4) 11k p-1j q-1 where {ffl1 < . .<.fflq-1}= {1, . .,.n}\ i01, . .,.i0q-1; 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 non-degenerate in some component u v of P , then so * *is v0, and we immediately obtain inequality (1) of (4.2). Next, each non-degenerat* *e de- creasing b uniquely determines a SCP a b. Although a may be degenerate, there is a unique non-degenerate u = RMp-1 . .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 non-degenerate CP associated with a b in P . As a composition of face operat* *ors, straightforward examination shows that u has form u = d(ip-1,`p-1).d.(.i1,`1)(e* *n) and is related to b = d(i0q-1,`0q-1).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 R-modules V1, . .,.* *Vn and a permutation oe 2 Sn, define the permutation isomorphism oe : V1 . . .Vn ! Voe-1(1) . . .Voe-1(n)by oe(x1. .x.n) = xoe-1(1).x.o.e-1(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,n-p-i= 1 i f 1 n-p-i : V n ! V n-p+q, where 0 i n - p. The abbreviations dgm, dga,and dgc stand for differential graded R-module, dg R-algebra and dg R-coalgebra, respectively. We begin with a review of A1 -(co)algebras paying particular attention to the signs. Let A be a connected R-module equipped with operations {'k 2 Homk-2 A k, A }k 1. For each k and n 1, linearly extend 'k to A n via n-kX 'ki,n-k-i: A n ! A n-k+1 , i=0 and consider the induced map of degree -1 given by n-kX __ n __ n-k+1 " 'k # ki,n-k-i: Ä ! Ä . i=0 __ Let eBA = T c Ä and define a map dBeA: eBA ! eBA of degree -1 by X (5.1) dBeA= " 'k # ki,n-k-i. 1 k n 0 i n-k The identities (-1)[n=2]" n # n = 1 n and [n=2]+[(n + k)=2] nk +[k=2](mod 2) imply that X [(n-k)=2]+i(k+1) (5.2) dBeA= (-1) " n-k+1 'ki,n-k-i# n . 1 k n 0 i n-k 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-`-1-i= 0. 0 ` n-1 0 i n-`-1 Proof.For n 1, X [(n-k)=2]+i(k+1) 0= (-1) " 'n-k+1 # n-k+1 " n-k+1 'ki,n-k-i# n 1 k n 0 i n-k X n-k+i(k+1) = (-1) 'n-k-1'ki,n-k-i 1 k n 0 i n-k X `(i+1) = - (-1)n (-1) 'n-`'`+1i,n-`-1-i. 0 ` n-1 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 Homk-1 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 Homk-2 A, A k }k 1. For each k and n 1, linearly extend each _k to A n via n-1X _ki,n-1-i: A n ! A n+k-1 , i=0 and consider the induced map of degree -1 given by n-1X __ n __ n+k-1 # k _k "i,n-1-i: # 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,n-1-i, n,k 1 0 i n-1 which can be rewritten as X [n=2]+i(k+1)+k(n+1) (5.4) deA = (-1) # n+k-1 _ki,n-1-i" n . n,k 1 0 i n-1 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-`-1-i_n-` = 0. 0 ` n-1 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 Homk-1 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)[(n-1)=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 en-2 2 Cn-2 (Kn)with the opera* *tion 'n via (5.7) en-2 7! (-1)n'n and each codimension 1 face d(i,`)en-2 2 Cn-3 (Kn)with the quadratic compo- sition n-2 n-` `+1 (5.8) d(i,`)e 7! ' 'i,n-`-1-i. 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 n-2 `+1 n-` en-2 7! _n and d(i,`)e 7! _i,n-`-1-i_ 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) iA-B! 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 n-2 * n-2 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) ,A-B! Hom(A B, (A B) n ) K # " (oe-1n)* C*(Kn) C*(Kn) ,-! Hom(A, A n ) Hom (B, B n ), A ,B where oe-1n*= Hom A B, oe-1n, n 2; the operations on A B are n-2 -1 n-2 ,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 non-empty 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 set-theoretic terms: _Face_of_Pn+1_|Label________ | en-1n,0 |n_|n + 1 | en-1n,1 |n + 1|n_ | A|B x I0,@B |A|B [ {n + 1} | A|B x I@B,1 |A [ {n + 1}|B. | For 1 p < n, let Qp(n) = partitionsA|B ofn_| p_ A orp_ B Qp(n) = {partitionsA|B 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 A|B 2 Qsr(n) homeomorphically onto the (n - 2)-product cell æ _____ _____ _ A \ s - 1| B \ s - 1x sA|B 2 Qs(n), r_x A \ r_-_1_| B \ r_-_1_A|B 2 Qr(n), and each face A|B 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). 3|12 12 x 3|2 _____________||oo o_____________||o 13|2 | | 23|1 | | | | | | | | 2,2 | | |o 123 o| ________- 1|2x 23 | 12 x 23 | 2|1x 23 | | | | | | | | 1|23 | | 2|13 | | _____________||oo o____________|_|o 12|3 12 x 2|3 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______________|_o||QQ || Q|o_______________|_o|QQ o| |oQ | |o |oQ | |o_______ | ______|o | |QQ |Q | |QQ | Q | | | | | | Q |o Q |o | Q |o Q|o | | | | | | | | | | | | | | | | |_______________|_|| | |________________|_| |____|____|o_____| |o |________ |o______| o| oQ | | oQ | | oQ | oQ | Q | | Q | | Q | Q | Q|o | Q|o | Q | Q | Q | Q | Q | Q | QQ|o_______________|oQQ QQ|o________________|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 | Q|Q | |Q | Q | Q || | Q |o______________|_o||QQ || QQ|o_______________|_o|QQ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |____|____|______| | | |________ | ______| | oQ | | oQ | | oQ | oQ | Q | | Q | | Q | Q | Q|o | Q|o | Q | Q | Q | Q | Q | Q | QQ|o_______________|oQQ QQ|o________________|oQQ Figure 8: Some canonical projections on P4. 28 SAMSON SANEBLIDZE1 AND RONALD UMBLE2 Given an (n - 1)-face of A|B Pn+1, choose a homeomorphism hA|B : PrxPs ! A|B. The singular coface operator associated with A|B ffiA|B : Pn ! Pn+1 is the composition hA|B O r,s: Pn -! Pr x Ps -! A|B. Unlike the simplicial or cubical case, ffiA|B is not an inclusion in general. There are two kinds of sin* *gular codegeneracy operators ffi, fij : Pn ! Pn-1; ffiis the cellular projection that identifies the faces i_|n_\i_and n_\i_|i_, 1* * i n-1; and fij is the cellular projection that identifies the faces j|n_\j and n_\j|j,* * 1 j n. Note that ff1 = fi1 and ffn-1 = 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, dA|B, %i, &j) in which SingPn+1Y = {continuous mapsPn+1 ! Y }, n 0, singular face operators dA|B : SingPn+1Y ! SingPnY are defined by dA|B(f) = f O ffiA|B for each A|B 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. Pn-1 _____-Pr x P_____-Pns P P P | P P P | f dA|B(f) P PPq |? Y Figure 9: A singular face operator Although coface operators ffiA|B : Pn ! Pn+1 need not be inclusions, the top * *cell of Pn is always non-degenerate under ffiA|B (c.f. Definition 9). However, the t* *op cell may degenerate under compositions of coface operators ffiA|BffiC|D : Pn-1 ! Pn+* *1. For example, ffi12|34ffi13|2: P2 ! P4 is a constant map, since ffi12|34: P3 -! * *P2 x P2 -! P4 sends the 1-face 13|2 to a vertex. Definition 21. A quadratic composition of face operators dC|DdA|B acts on Pn+1 if the top cell of Pn-1 is non-degenerate under the composition ffiA|BffiC|D : Pn-1 ! 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 n-simplex n and compositions dfflidffljof face operators in a cubical s* *et always act on the n-cube In. When dC|DdA|B acts on Pn+1, assign the label dC|DdA|B to the n - 2 face ffiA|BffiC|D (Pn-1)(see Figure 10). d2|1d13|2= d1|2d3|12 d3|12 d2|1d23|1= d2|1d3|12 _____________||oo d13|2| | d23|1 | | | | d1|2d13|2= d2|1d1|2|o3 123 |o d2|1d2|13= d1|2d23|1 | | | | d1|23| | d2|13 _____________||oo d1|2d12|3= d1|2d1|23 d12|3 d1|2d2|13= d2|1d12|3 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 Ph13|2 i i i P P P i i i 1,1 h2|1 1,2 PPq P2 _____-P1 _____-P1 x P1 _____-P2 _____- P1 x P2 _____-P3P3 ff1 h1|23 || H H J | | H H d2|1d1|23d12|34(fJd1|23d12|34(f)) | 2,2 | H H J |? || H H H J P2 x P2 ||&1d2|1d1|23d12|34(f) = H H J | | H H JJ^ d12|34(f) | h12|34 | d13|2d12|34(f) H HHj |? ___________________________________________-|Y __________oeP4 f Figure 11: The quartic relation &1d2|1d1|23d12|34= d13|2d12|34. 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(A|B) dA|B, A|B2Pr,s(n+1) where sgn(A|B) denotes the sign of the shuffle (A and B are ordered). Note that* * if f 2 C*(SingP4Y ) and d13|2d12|34(f)6= 0, the component d13|2d12|34(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 non-normalized 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 Alexander-Whitney 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 dM2k-1|M2k. .d.M1|M2acting on Pn+1. First make the ident* *i- fications A|B $ dA|B (see Figure 10), where A|B ranges over the (n - 1)-faces of Pn+1 (see Section 2). Motivated by Definition 21, the conditions under which a * *qua- dratic composition dC|DdA|B acts on Pn+1 can be stated in terms of set operatio* *ns, which we now define. Given a non-empty 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 non-empty 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 A|B 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[j-1]= Aj-1__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(k-1)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 A|B|C * *is a boundary component shared by exactly two (n - 1)-faces. Consequently, A|B|C 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_B|At_CdA|B[C = dA__tC|B__tCdA[B|C. Example 10. In P8, the 5-face A|B|C_= 12|345|678_= 12|345678\12345|678. Since At_B = {1234}, At_C = {567}, At C = {12} and Bt C = {34567}, we obtain the following quadratic relation on 12|345|678 : d1234|567d12|345678= d12|34567d12345|678; similarly, on 345|12|678 we have d1234|567d345|12678= d34567|12d12345|678. 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 A|B 2 Pp,q(n + 1)and C|D 2 P**(n). Then dC|DdA|B denotes an (n - 2)-face of Pn+1 if and only if C|D 2 Qqp(n). Proof.If dC|DdA|B denotes an (n - 2)-face, say X|Y |Z, then according to relati* *on (6.2) we have either A|B = X| Y [Z and C|D = Xt_Y |Xt_Z or __ __ A|B = X [ Y |Zand C|D = Xt Z| Y tZ. Hence there are two cases. Case_1:_A|B = X|Y [ Z. If min Y = min Y [ Z, then p_ Xt_Y ; otherwise minY [ Z = minZ and p_ Xt_Z. In either case, C|D= Xt_Y |Xt_Z 2 Qp(n). Case_2:_A|B = 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, C|D= 32 SAMSON SANEBLIDZE1 AND RONALD UMBLE2 X__tZ|Y __tZ 2 Qq(n). Conversely, given A|B 2 Pp,q(n + 1) and C|D 2 Qqp(n), let 8 < A|S (C)|S (D), C|D 2 Qp(n) [A|B; C|D] = : T (C)|T (D)|B, C|D 2 Qq(n), where S (X)= I-1B q_\ X - p + 1and T (X) = I-1A p_\ X . A straightforward calculation shows that [X|Y [ Z; Xt_Y |Xt_Z]= X|Y |Z = [X [ Y |Z; X__tZ| Y __tZ]. Consequently, if X|Y |Z = [A|B; C|D], either A|B = X| Y [ Z andC|D = Xt_Y |Xt_Z when C|D 2 Qp(n) or A|B = X [ Y |Zand C|D = X__tZ| Y __tZ when C|D 2 Qq(n). On the other hand, if C|D 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 set-theoretic 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 dA|B : Zn+1 ! Zn for each A|B 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, dA|B, %i, &jis a permutahedral set if the following structure relations hol* *d: For all A|B|C 2 P***(n + 1) (6.3) dAt_B|At_CdA|B[C = dA__tC|B__tCdA[B|C. For all A|B 2 Pr,s(n + 1)and C|D 2 P**(n)\ Qsr(n) (6.4) dC|DdA|B = &jdM|N dK|LdA|B where 8 >>>K|L = n_Ø (r_\ D)|r_\ D, >>>M|N = C__t(r_\ D)| (DØ (r_\ D))_t(r_\ D), >> or >>>K|L = r_\ C|n_Ø (r_\ C), >>> >: M|N = (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 A|B 2 P**(n + 1)and 1 < j < n (for j = 1, n see (6.6) below) (6.5) 8 >><1, ifA = j_orB = j_, &jdj|n_Øj, ifA|B 2 Qj(n + 1), A 6= j_orB 6= j_, dA|B&j = > _ _ n+1-j >:&j-1dj-1_|n_Øj-1_,ifA|B 2 Q (n + 1), A 6= j_orB 6= j_, &j&jdM|N dK|L, ifA|B =2Qn+1-jj(n + 1)where 8 __ __ >>>K|L = At j_\ B | BØ j_\ B t j_\ B , >>>M|N = @ j \ A |n_-_1_Ø@ j \ A , >> or >>>K|L = j\ A t j\ B | j \ A tB, >>> _ __ _ _ __ >:M|N = j_-_1_|n_-_1_Øj_-_1_, when j 2 B. For all A|B 2 P**(n + 1)and 1 i n + 1 æ (6.6) dA|B%i= 1,% ifA = {i}or B = {i}, jdC|D,where 8 >>>C|D = In+2_Øi(AØi)|In+2_Øi(B), > or >>>C|D = 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, d0A|B, &0i, %0j} and Z00= {Z00s, d00A|B, &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, dA|B, &i, %j with face and degeneracy operators defined by 8 i j >>< d0r (a), b, ifA|B 2 Qs(n), i _\A|r_\B j (6.8) dA|B(a, b) = > a, d00 (b),ifA|B 2 Qr(n), >: s_\(A-n+s)| s_\(B-n+s) &idM|N dK|L (a, b), otherwise, where 34 SAMSON SANEBLIDZE1 AND RONALD UMBLE2 8 >>>K|L = r_\ A| (r_\ B)[ s_-_1_+ r >>>M|N = (r_\ A)t_(BØ (r_\ B))| (r_\ A)t_B >> or >>>K|L = A [ (BØ (r_\ B))|r_\ B >>> __ __ >:M|N = 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, , i-r+1(b)r i n; æ 0 (6.10) %j(a, b)= %j(a),ab,, %001 j r, j-r+1(b),r < j n + 1. Remark 1. Note that the right-hand side of the third equality in (6.8) reduces * *to the first two; indeed, if r 2 B, then K|L 2 Qs(n) and M|N 2 Qr(n); if r 2 A, K|L 2 Qs(n) and M|N 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 K|L 2 Qs(n), M|N 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, dA|B, &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 (n-m)-face u = A1| . .|.Am+1 * * Pn+1, define Y (i) sgn u = (-1)@A sgn(A(i)|A(i-1)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+2-j| . .|.bi+1|bn+2-j|bi| . .|.bn+1, gj(b1| . .|.bn+1) = : ifbn+1-j, bn+3-j, . .,.bi+1< bn+2-j < 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= RMp-1 . .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 non-degenerate 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 non-degenerate 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,n-1) 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 cobar-construction 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 k-reduced if W has exactly one element in each dimension * *k. Let C denote the cobar construction on a 1-reduced dg coalgebra C. In [10] and [11], Kadeishvili and Saneblidze construct a functor from the category of 1-red* *uced simplicial sets to the category of cubical sets and a functor from the category* * of 1-reduced cubical sets to the category of permutahedral sets for which the foll* *owing statements hold (c.f. [3], [2]): Theorem 4. [10] Given a 1-reduced simplicial set X, there is a canonical identi* *fi- cation isomorphism C*(X) C* ( X). Theorem 5. [11] Given a 1-reduced 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 2-reduced 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 1-reduced simplicial sets to the category of cubical sets and the definition of* * the functor from the category of 1-reduced 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 1-reduced 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 = s-1(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= s-1(X>0). Apparently 0X canonically admits the structure of a cubical set. Denote the components of Alexander-Whitney diagonal by i: Xn ! Xix Xn-i, where i(x) = @i+1. .@.n(x) x @0. .@.i-1(x), 0 i n, and let xn denote an n-simplex simplex, i.e. xn 2 Xn. Then i(xn) = ((x0)i, (x00)n-i) 2 Xix Xn-i for all n >_0._Define face_operators_d0i, d1i: ( X)n-1 ! ( X)n-2 on a (monoidal) generator xn 2 (X~)n-1 (Xc )n-1 by ___ ____ _______ d0i(xn)= (x0)i. (x00)n-i,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)mq-jq+1.x.k., _______ __ d1i(_x1._._.xk)= __x1.@.j.q(xq).x.k., where m(q-1)< i m(q), jq = i - m(q-1), 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)n-1 ! ( X)n on a (monoidal) generator __x2 (Xc )n-1 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._._.xmk-1. jmk+1 (__xk), where m(q-1)< i m(q), jq = i - m(q-1), 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)n-1= e . (x00)n-1= (x00)n-1= @0(xn), ___ _______ _____ _______ _______ _______ d0n-1(xn)= (x0)n-1. (x00)1= (x00)n-1. e = (x0)n-1= @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 1-reduced 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= s-1(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= s-1(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 dA|B by _____ _____ dA|B(~a) = d0B(a). d1A(a), A|B 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 dA|B by induction on grading. In particular, we ha* *ve the following identities: _____ di|n+1_\i(_a)= d1i(a),1 i n, _____ dn+1_\i|i(_a)= d0i(a),1 i n. It is easy to see that ( Q, dA|B, &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 n-cube 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), 409-412. [2]H. J. Baues, The Cobar Construction as a Hopf Algebra, Invent. Math., 132 (* *1998), 467-489. [3]G. Carlsson and R. J. Milgram, Stable homotopy and iterated loop spaces, Ha* *ndbook of Algebraic Topology (Edited by I. M. James), North-Holland (1995), 505-583. [4]F. Chapoton, Algèbres de Hopf des permutahèdres, associahèdres et hypercube* *s, Adv. in Math. 150, No. 2, (2000), 264-275. [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,* * Springer-Verlag, 1972. [7]Matthias R. Gaberdiel and Barton Zwiebach, Tensor Constructions of Open Str* *ing Theories I: Foundations, Nucl.Phys. B505 (1997), 569-624. [8]N. Iwase and M. Mimura, Higher homotopy associativity, Lecture Notes in Mat* *h., 1370 (1986), 193-220. DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA 39 [9]D. W. Jones, A general theory of polyhedral sets and corresponding T-comple* *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), 2147-2161. [13]J.-L. Loday and M. Ronco, Hopf algebra of the planar binary trees, Adv. in * *Math. 139, No. 2 (1998), 293-309. [14]S. Mac Lane, ``Homology,'' Springer-Verlag, Berlin/New York, 1967. [15]R. J. Milgram, Iterated loop spaces, Ann. of Math., 84 (1966), 386-403. [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 H-spaces I, II, Trans. Amer. Math* *. Soc., 108 (1963), 275-312. [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.33-36 A. Razmadze Mathematical Institute, Georgian Academy of Sciences, M. Aleksidze st., 1, 380093 Tbilisi, Georgia E-mail address: sane@rmi.acnet.ge Department of Mathematics, Millersville University of Pennsylvania, Millersvi* *lle, PA. 17551 E-mail address: Ron.Umble@Millersville.edu