Homology, Homotopy and Applications, vol.6(1), 2004, pp.363–411

DIAGONALS ON THE PERMUTAHEDRA, MULTIPLIHEDRA AND ASSOCIAHEDRA

SAMSON SANEBLIDZE and RONALD UMBLE

(communicated by Ross Street)

Abstract We construct an explicit diagonal Δ_{P} on the permutahedra P. Related diagonals on the multiplihedra J and the associahedra K are induced by Tonks’ projection P → K [19] and its factorization through J. We introduce the notion of a permutahedral set Z and lift Δ_{P} to a diagonal on Z. We show that the double cobar construction Ω^{2}C_{∗}(X) is a permutahedral set; consequently Δ_{P} lifts to a diagonal on Ω^{2}C_{∗}(X). Finally, we apply the diagonal on K to define the tensor product of A_{∞}-(co)algebras in maximal generality.

1. Introduction

A permutahedral set is a combinatorial object generated by permutahedra P 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 notion of a permutahedral set and observe that the double cobar construction Ω^{2}C_{∗} (X) is a naturally occurring example. We construct an explicit diagonal Δ_{P} : C_{∗}(P) → C_{∗}(P) ⊗ C_{∗}(P) on the cellular chains of permutahedra and show how to lift Δ_{P} to a diagonal on any permutahedral set. We factor Tonks’ projection θ : P → K through the multiplihedron J and obtain diagonals Δ_{J} on C_{∗}(J) and Δ_{K} on C_{∗}(K). We apply Δ_{K} to define the tensor product of A_{∞}-(co)algebras in maximal generality; this resolves a long-standing problem in the theory of operads. Gaberdiel and Zwiebach’s open string field theory [5] provides a setting in which this tensor product can be applied.

The paper is organized as follows: Sections 2 and 5 review the families of polytopes we consider. The diagonal Δ_{P} is defined in Section 3 and lifted to general permutahedral sets in Section 4. The related diagonals Δ_{J} and Δ_{K} are obtained in Section 6 and applied in Section 7 to define the tensor product of A_{∞}-(co)algebras in maximal generality. Sections 5 through 7 do not depend on Section 4.

This 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 (CRDF) and by Award No. 99-00817 of INTAS This research was funded in part by a Millersville University faculty research grant. Received November 22, 2002, revised June 7, 2004; published on September 29, 2004. 2000 Mathematics Subject Classification: Primary 55U05, 52B05, 05A18, 05A19; Secondary 55P35. Key words and phrases: Diagonal, permutahedron, multiplihedron, associahedron. \begin{matrix}c \\ ◯ \end{matrix} 2004, Samson Saneblidze and Ronald Umble. Permission to copy for private use granted.

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 generous financial support and the University of North Carolina at Chapel Hill for its kind hospitality during work on parts of this project.

2. The Permutahedra

Let S_{n} be the symmetric group on \underline{n} = \{1, 2, …, n\} . Recall that the permutahedron P_{n} is the convex hull of n! vertices (σ(1), …, σ(n)) ∈ ℝ^{n}, σ ∈ S_{n} [4], [14], [20]. As a cellular complex, P_{n} is an (n − 1)-dimensional convex polytope whose (n − p)-faces are indexed by (ordered) partitions U_{1}| ⋯ |U_{p} of \underline{n}. We shall define the permutahedra inductively as subdivisions of the standard n-cube I^{n}. With this representation the combinatorial connection between faces and partitions is immediately clear.

Assign the label \underline{1} to the single point P_{1}. If P_{n−1} has been constructed and u = U_{1}| ⋯ |U_{p} is one of its faces, form the sequence u_{∗} = {u_{0} = 0, u_{1}, …, u_{p−1}, u_{p} = ∞} where u_{j} = # (U_{p−j+1} ∪ ⋯ ∪ U_{p}) , 1 ⩽ j ⩽ p − 1 and # denotes cardinality. Define the subdivision of I relative to u to be

I/u_{∗} = I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{p},

where I_{j} = [1 − \frac{1}{2^{u_{j−1}}} , 1 − \frac{1}{2^{u_{j}}} ] and \frac{1}{2^{∞}} = 0. Then

P_{n} = ⋃_{u∈P_{n−1}} u × I/u_{∗}

with faces labeled as follows (see Figures 1 and 2):

Face of u × I/u_{∗}  Partition of \underline{n}

u × 0  U_{1}| ⋯ |U_{p}|n
u × (I_{j} ∩ I_{j+1}) U_{1}| ⋯ |U_{p−j}|n|U_{p−j+1}| ⋯ |U_{p}, 1 ⩽ j ⩽ p − 1
u × 1  n|U_{1}| ⋯ |U_{p}
u × I_{j}  U_{1}| ⋯ |U_{p−j+1} ∪ n| ⋯ |U_{p}.

A cubical vertex of P_{n} is a vertex common to both P_{n} and I^{n−1}. Note that u is a cubical vertex of P_{n−1} if and only if u|n and n|u are cubical vertices of P_{n}. Thus the cubical vertices of P_{3} are 1|2|3, 2|1|3, 3|1|2 and 3|2|1 since 1|2 and 2|1 are cubical vertices of P_{2}.

• • •  • • • 123 1|2|3 1|3|2 3|1|2  2|1|3 2|3|1 3|2|1 1|23  3|12 13|2  23|1 2|13 12|3
Figure 1: P_{3} as a subdivision of P_{2} × I.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; (0, 1, 0); (1, 1, 1); (1, 0, 0); (0, 0, 0)]

Figure 2a: P_{4} as a subdivision of P_{3} × I.

•  •  • •  •  •  •  •  •  • •  •  •  • •  •  •  •  • •  •  •  •  • •  •  •  •  •  •  • •  •  •(1, 1, 1) (0, 0, 0) 124|3 12|34  24|13 2|134 4|123 123|4 234|1 23|14  34|12 3|124  134|2 13|24 14|23 1|234

Figure 2b: The 2-faces of P_{4}.

3. A Diagonal on the Permutahedra

In this section we construct a combinatorial diagonal on the cellular chains of the permutahedron P_{n+1}. Given a polytope X, let (C_{∗} (X) , ∂) denote the cellular chains on X with boundary ∂.

Definition 1. A map Δ_{X} : C_{∗}(X) → C_{∗}(X) ⊗ C_{∗}(X) is a \underline{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. In general, the DG coalgebra (C_{∗} (X) , Δ_{X}, ∂) is non-coassociative, non-cocommuta-tive and non-counital; thus the statement (2) in Definition 1 is equivalent to stating that Δ_{X} is a chain map. We remark that a diagonal Δ_{P} on C_{∗} (P_{n+1}) is unique if the following two additional properties hold:

1. The canonical cellular projection ρ_{n+1} : P_{n+1} → I^{n} induces a DG coalgebra map C_{∗} (P_{n+1}) → C_{∗} (I^{n}) (see Section 4, Figures 3 and 4) and

2. There is a minimal number of components a ⊗ b in Δ_{P} (C_{k} (P_{n+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.

Definition 2. A partition A_{1}| ⋯ |A_{p} is \underline{step increasing} iff A_{p}| ⋯ |A_{1} is \underline{step decreas-} \underline{ing} iff min A_{j} < max A_{j+1} for all j ⩽ p−1. A \underline{step} partition is either step increasing or step decreasing.

Think of σ ∈ S_{p+q−1} as an ordered sequence of positive integers; let \overleftarrow{σ}_{j} and \overrightarrow{σ}_{q−i+1} denote its j^{th} decreasing and i^{th} increasing subsequence of maximal length. Then \overleftarrow{σ}_{1}| ⋯ |\overleftarrow{σ}_{p} and \overrightarrow{σ}_{q}| ⋯ |\overrightarrow{σ}_{1} are step increasing and step decreasing partitions of \underline{p + q − 1}, respectively (see Example 1 below).

Definition 3. A pairing of partitions A_{1}| ⋯ |A_{p}⊗B_{q}| ⋯ |B_{1} is a \underline{strong complemen-} \underline{tary pair}(SCP) if there exists σ ∈ S_{p+q−1} such that A_{j} = \overleftarrow{σ}_{j} and B_{i} = \overrightarrow{σ}_{i} as unordered sets for all i, j.

SCP’s have a natural matrix representation.

Definition 4. A q × p matrix O = (o_{ij}) is \underline{ordered} if:

1. {o_{i,j}} = {0, 1, …, p + q − 1};

2. Each row and column of O is non-zero;

3. Non-zero entries in O are distinct and increase in each row and column.

Let O denote the set of ordered matrices. Note that the rows and columns of an ordered matrix O^{q×p} form a partition of \underline{p + q − 1}.

Definition 5. Given O ∈ O^{q×p}, let V_{i} = row_{i} (O)∩ℤ^{+} for i ⩽ q and U_{j} = col_{j} (O)∩ ℤ^{+} for j ⩽ p. The \underline{row face of O} is the face r (O) = V_{q}| ⋯ |V_{1} ⊂ P_{p+q−1}; the \underline{column face of O} is the face c (O) = U_{1}| ⋯ |U_{p} ⊂ P_{p+q−1}.

Definition 6. An ordered matrix E is a \underline{step matrix} if:

1. Non-zero entries in each row of E appear in consecutive columns;

2. Non-zero entries in each column of E appear in consecutive rows;

3. The sub, main and super diagonals of E contain a single non-zero entry.

Let E denote the set of step matrices. If E = (e_{i,j}) ∈ E^{q×p}, condition (1) in Definition 6 groups the non-zero entries in each row together in a horizontal block, condition (2) groups the non-zero entries in each column together in a vertical block and condition (3) links horizontal and vertical blocks to produce a “staircase path” of non-zero entries connecting the lower-left and upper-right entries e_{q,1} and e_{1,p} (see Example 1 below). Clearly, c (E) ⊗ r (E) = \overleftarrow{σ}_{1}| ⋯ |\overleftarrow{σ}_{p} ⊗ \overrightarrow{σ}_{q}| ⋯ |\overrightarrow{σ}_{1} for some σ ∈ S_{p+q−1}, so c (E) ⊗ r (E) is an SCP. Furthermore, one can recover E from σ = (x_{1} x_{2} ⋯ x_{n+1}) in the following way: Set e_{q,1} = x_{1}. Inductively, assume e_{i,j} = x_{k−1}; if x_{k−1} < x_{k}, set e_{i,j+1} = x_{k}; otherwise, set e_{i−1,j} = x_{k}. Let E_{σ} denote the step matrix given by σ ∈ S = lim_{→} S_{n+1}. We have proved:

Proposition 1. There exist one-to-one correspondences

E ↔ S ↔ {Step increasing partitions} ↔ {Step decreasing partitions} ↔ {SCP’s}

E_{σ} ↔ σ ↔ \overleftarrow{σ}_{1}| ⋯ |\overleftarrow{σ}_{p} ↔ \overrightarrow{σ}_{q}| ⋯ |\overrightarrow{σ}_{1} ↔ \overleftarrow{σ}_{1}| ⋯ |\overleftarrow{σ}_{p} ⊗ \overrightarrow{σ}_{q}| ⋯ |\overrightarrow{σ}_{1}.

Example 1. The permutation

σ = (9 7 1 3 8 4 6 5 2)

corresponds to step matrix

E_{σ} = 2 5 4 6 1 3 8 7 9 .

and the SCP

c (E_{σ}) ⊗ r (E_{σ}) = 971|3|84|652 ⊗ 9|7|138|46|5|2.

We now introduce matrix transformations that operate like the vertical and horizontal shifts one performs in a tableau puzzle. For (i, j) ∈ ℤ^{+} × ℤ^{+}, define the down-shift and right-shift operators D_{i,j}, R_{i,j} : O → O on O^{q×p} = (o_{i,j}) by

1. D_{i,j}O = O unless i ⩽ q−1, o_{i+1,j} = 0, o_{i,j}o_{i,k} > 0 for some k ≠ j, o_{i,j} > o_{i+1,ℓ} for 1 ⩽ ℓ < j, and o_{i+1,ℓ} > o_{i,j} whenever o_{i+1,ℓ} > 0 and j < ℓ ⩽ p, in which case D_{i,j}O is obtained from O by transposing o_{i,j} and o_{i+1,j};

2. R_{i,j}O = O unless j ⩽ p−1, o_{i,j+1} = 0, o_{i,j}o_{k,j} > 0 for some k ≠ i, o_{i,j} > o_{ℓ,j+1} for 1 ⩽ ℓ < i, and o_{ℓ,j+1} > o_{i,j} whenever o_{ℓ,j+1} > 0 and j < ℓ ⩽ q, in which case R_{i,j}O is obtained from O by transposing o_{i,j} and o_{i,j+1}.

Definition 7. A matrix F ∈ O is a \underline{configuration matrix} if there is a step matrix E and a sequence of shift operators G_{1}, …, G_{m} such that

1. F = G_{m} ⋯ G_{1}E;

2. If G_{m} ⋯ G_{1} = ⋯ D_{i_{2},j_{2}} ⋯ D_{i_{1},j_{1}} ⋯, then i_{1} ⩽ i_{2};

3. If G_{m} ⋯ G_{1} = ⋯ R_{k_{2},ℓ_{2}} ⋯ R_{k_{1},ℓ_{1}} ⋯, then ℓ_{1} ⩽ ℓ_{2}. When this occurs, we say that F is \underline{derived from} E and refer to the pairing c (F) ⊗ r (F) as a \underline{complementary pair (CP) related to} c (E) ⊗ r (E).

Let C denote the set of configuration matrices. For F = (f_{i,j}) ∈ C with column face U_{1}| ⋯ |U_{p} and row face V_{q}| ⋯ |V_{1}, choose proper subsets N_{i} = {f_{i,n_{1}} < ⋯ < f_{i,n_{k}}| max V_{i+1} < f_{i,n_{1}}} ⊂ V_{i} and M_{j} = {f_{m_{1},j} < ⋯ < f_{m_{ℓ},j} |max U_{j+1} < f_{m_{1},j} } ⊂ U_{j} and define

D_{N_{i}}^{i}F = D_{i,n_{k}} ⋯ D_{i,n_{1}}F and R_{M_{j}}^{j}F = R_{m_{ℓ},j} ⋯ R_{m_{1},j}F.

We often suppress the superscript when it is clear from context. The fact that D_{i,j+1}R_{i,j}F = R_{i+1,j}D_{i,j}F wherever both maps in the composition act non-trivially, gives the following useful reformulation of Definition 7:

Proposition 2. A matrix F ∈ O with c (F) = U_{1}| ⋯ |U_{p} and r (F) = V_{q}| ⋯ |V_{1} is a configuration matrix if and only if there exists E ∈ E and proper subsets M_{j} ⊂ U_{j} and N_{i} ⊂ V_{i} such that

F = D_{N_{q−1}} ⋯ D_{N_{1}}R_{M_{p−1}} ⋯ R_{M_{1}}E.

Example 2. Four configuration matrices F can be derived from the step matrix

E = 2 3 1 5 4  :

D_{∅}D_{∅}R_{∅}R_{∅}E = 2 3 1 5 4  ↔ 14|25|3 ⊗ 4|15|23,

D_{∅}D_{∅}R_{5}R_{∅}E = 2 3 1  5 4  ↔ 14|2|35 ⊗ 4|15|23,

D_{5}D_{∅}R_{∅}R_{∅}E = 2 3 1 4 5  ↔ 14|25|3 ⊗ 45|1|23,

D_{5}D_{∅}R_{5}R_{∅}E = 2 3 1 4  5  ↔ 14|2|35 ⊗ 45|1|23.

Up to sign, the CP’s

c (F) ⊗ r (F) = (14|2|35 + 14|25|3) ⊗ (4|15|23 + 45|1|23)

are components of Δ_{P} (\underline{5}).

Let us associate formal “configuration signs” to configuration matrices. The signs we introduce here can be derived by induction on dimension given that P_{2} = I and Δ_{P} is a chain map. Henceforth we assume that all blocks in a partition are increasingly ordered. First note that a face u = U_{1}| ⋯ |U_{p} ⊂ P_{n+1} is an (n − p + 1)- face of p − 1 faces in dimension n − p + 2. Thus there are (p − 1)! ways to produce u by successively inserting bars into \underline{n + 1}, each of which has an associated sign. Of these, we need the right-most and left-most insertion procedures.

When each x ∈ \underline{n + 1} has degree 1, the sign of a permutation σ ∈ S_{n+1} is the Koszul sign that arises from the action of σ. Thus, if σ transposes adjacent subsets U, V ⊂ \underline{n + 1} for example, then sgn (σ) = (−1)^{#U#V} . For u = U_{1}| ⋯ |U_{p} ⊂ P_{n+1}, denote the sign of the permutation \underline{n + 1} → U_{1} ∪ ⋯ ∪ U_{p} by psgn (u); note that σ is an unshuffle of \underline{n} when p = 2, in which case we denote psgn (u) = shuff (U_{1}; U_{2}). Let m_{i} = #U_{i} − 1 and identify u with the Cartesian product P_{m_{1}+1} × ⋯ × P_{m_{p}+1}; then

C_{n−p+1} (u) = C_{m_{1}} (U_{1}) ⊗ ⋯ ⊗ C_{m_{p}} (U_{p}) .

Finally, think of the symbol | as an operator with degree −1 that acts by sliding in from the left; then

|(U ⊗ V) = (−1)^{#U} U|V.

Definition 8. Given a partition M|N of \underline{n + 1}, define \underline{face operators with respect to} \underline{M and N}, d_{M}, d^{N} : C_{n} (P_{n+1}) → C_{n−1} (P_{n+1}) by

d_{M} (\underline{n + 1}) = d^{N} (\underline{n + 1}) = (−1)^{#M} shuff (M; N) M|N.

For u = U_{1}| ⋯ |U_{p} ⊂ P_{n+1} and non-empty M ⊂ U_{k}, define the \underline{face operator with} \underline{respect to M}, d_{M}^{k} : C_{n−p+1} (u) → C_{n−p} (u) , by

d_{M}^{k}(u) = (1^{⊗k−1} ⊗ d_{M} ⊗ 1^{⊗p−k})(u);

for v = V_{q}| ⋯ |V_{1} ⊂ P_{n+1} and non-empty N ⊂ V_{k}, define the \underline{face operator with} \underline{respect to N}, d_{k}^{N} : C_{n−q+1} (v) → C_{n−q} (v) , by

d_{k}^{N}(v) = (1^{⊗q−k} ⊗ d^{N} ⊗ 1^{⊗k−1})(v).

Then

d_{M}^{k} (u) = ϵ (M) U_{1}| ⋯ |M|U_{k} \ M| ⋯ |U_{p},

d_{k}^{N} (v) = ϵ (N) V_{q}| ⋯ |V_{k} \ N|N| ⋯ |V_{1},

where

ϵ (M) = (−1)^{m_{1}+···+m_{k−1}+#M} shuff (M; U_{k} \ M) and m_{i} = #U_{i} − 1,

ϵ (N) = (−1)^{n_{q}+···+n_{k+1}+#(V_{k}\N)} shuff (V_{k} \ N; N) and n_{i} = #V_{i} − 1.

Face operators give rise to boundary operators ∂ : C_{n−p+1} (u) → C_{n−p} (u) and ∂ : C_{n−q+1} (v) → C_{n−q} (v) in the standard way:

∂ (u) = ∑_{\begin{matrix}1⩽k⩽p \\ M⊂U_{k} \end{matrix}} ϵ(M) d_{M}^{k} (U_{1}| ⋯ |U_{p})

and similarly for ∂ (v); in either case,

∂ (\underline{n + 1}) = ∑_{\begin{matrix}M,N⊂\underline{n+1} \\ N=\underline{n+1}\M \end{matrix}} (−1)^{#M} shuff (M; N) M|N.  (3.1)

The sign coefficients in 3.1 were given by R. J. Milgram in [14]. Thus, two types of signs appear when d_{M}^{k} is applied to U_{1}| ⋯ |U_{p} : First, Koszul’s sign appears when d_{M} passes U_{1} ⊗ ⋯ ⊗ U_{k−1} and second, Milgram’s sign appears when d_{M} is applied to U_{k}.

A partitioning procedure is a composition of the form

d_{M_{p−1}}^{k_{p−1}} ⋯ d_{M_{2}}^{k_{2}}d_{M_{1}}.

For example, a partition u = U_{1}| ⋯ |U_{p} of \underline{n + 1} can be obtained from the right-most partitioning procedure by setting M_{0} = \underline{n + 1}, M_{i} = M_{i−1} \ U_{p−i+1} and k_{i} = 1 for 1 ⩽ i ⩽ p − 1; then

d_{M_{p−1}}^{1} ⋯ d_{M_{2}}^{1}d_{M_{1}} (\underline{n + 1}) = sgn_{1} (u) U_{1}| ⋯ |U_{p},

where

sgn_{1} (u) = (−1)^{ϵ_{1}} psgn (u) and ϵ_{1} = ∑_{i=1}^{p−1} i · #U_{p−i}.

Note that when v = V_{q}| ⋯ |V_{1} we have ϵ_{1} = ∑_{i=1}^{q−1} i · #V_{i+1}. Alternatively, u can be obtained from the left-most partitioning procedure by setting M_{i} = U_{i} and k_{i} = i for 1 ⩽ i ⩽ p − 1; then

d_{U_{p−1}}^{p−1} ⋯ d_{U_{2}}^{2}d_{U_{1}} (\underline{n + 1}) = sgn_{2} (u) U_{1}| ⋯ |U_{p},

where

sgn_{2} (u) = (−1)^{ϵ_{2}} psgn (u) and ϵ_{2} = ϵ_{1} + \binom{p−1}{2}.

Let rsgn(U_{i}) denote the sign of the order-reversing permutation on U_{i}, then

rsgn(U_{i}) = (−1)^{^{\frac{1}{2}} (#U_{i})(#U_{i}−1)} ;

define

rsgn(u) = ∏_{i=1}^{p} rsgn(U_{i}) = (−1)^{^{\frac{1}{2}}[(#U_{1})^{2}+···+(#U_{p})^{2}−(n+1)]}.

Definition 9. If F ∈ C^{q×p} is derived from E ∈ E, the \underline{configuration sign of F} is defined to be

csgn(F) = (−1)^{\binom{q}{2}} rsgn(c(E)) · sgn_{1}r(F) · sgn_{2}c(E) · sgn_{2}c(F).

In particular, for F = E ∈ E^{q×p} we have

csgn(E) = (−1)^{\binom{q}{2}} rsgn(c(E)) · sgn_{1}r(E).

Signs that arise from the action of shift operators are now determined. For x ∈ ℤ and Y ⊆ ℤ, denote the lower and upper cuts of Y at x by [Y, x) = {y ∈ Y | y < x} and (x, Y] = {y ∈ Y | y > x} , respectively.

Proposition 3. If F = (f_{i,j}) ∈ C, c (F) = U_{1}| ⋯ |U_{p} and r (F) = V_{q}| ⋯ |V_{1}, then

csgn(D_{i,j}F) · csgn (F) = −(−1)^{#(f′_{i+1,j},V′_{i+1}]∪[V_{i},f_{i,j})},
csgn(R_{i,j}F) · csgn (F) = −(−1)^{#(f_{i,j},U_{j}]∪[U′_{j+1},f′_{i,j+1})},

where F′ = (f′_{i,j}) is the image of F, U′_{1}| ⋯ |U′_{p} = c (F′) and V′_{q}| ⋯ |V′_{1} = r (F′) .

Proof. Note that c (F) = c (D_{i,j}F) and r (F) = r (R_{i,j}F) . Then for example,

csgn(D_{i,j}F) · csgn(F) = (−1)^{\binom{q}{2}} rsgn(c(E))·sgn_{1}r(D_{i,j}F)·sgn_{2}c(E)·sgn_{2}c(D_{i,j}F)
· (−1)^{\binom{q}{2}} rsgn(c(E)) · sgn_{1}r (F) · sgn_{2}c(E) · sgn_{2}c(F)
= sgn_{1}r(F) · sgn_{1}r(D_{i,j}F) · sgn_{2}c(F) · sgn_{2}c(D_{i,j}F)
= psgn (r (F)) · psgn (r (D_{i,j}F)) = −sgn (σ) ,

where σ is the permutation V_{q} ∪ ⋯ ∪ V_{1} ↦ V_{q} ∪ ⋯ V′_{i+1} ∪ V′_{i} ⋯ ∪ V_{1}.

The configuration signs of “edge matrices,” which appear in our subsequent discussion of permutahedral sets, have a particularly nice form.

Definition 10. E ∈ E is an \underline{edge matrix} if e_{1,1} = 1.

Let Γ denote the set of all edge matrices. With one possible exception, all blocks in the column and row face of an edge matrix consist of singleton sets. Thus if E ∈ Γ^{q×p},

c (E) ⊗ r (E) = A|a_{2}| ⋯ |a_{p} ⊗ b_{q}| ⋯ |b_{2}|B,

where A = {1 < b_{2} < ⋯ < b_{q}} and B = {1 < a_{2} < ⋯ < a_{p}} . Since c (E) and r (E) meet at the cubical vertex b_{q}| ⋯ |b_{2}|1|a_{2}| ⋯ |a_{p} of P_{p+q−1}, there is a canonical bijection

Γ ↔ {cubical vertices of P = ⊔P_{n+1}} .

The proof of the following proposition is now immediate:

Proposition 4. If E is an edge matrix and b_{q}| ⋯ |b_{2}|1|a_{2}| ⋯ |a_{p} is the corresponding cubical vertex, then

csgn (E) = shuff (b_{2}, …, b_{q}; a_{2}, …, a_{p}) .

We are ready to define a diagonal on C_{∗} (P_{n+1}) .

Definition 11. For each n ⩾ 0, define Δ_{P} on the top dimensional face \underline{n + 1} ∈ C_{n} (P_{n+1}) by

Δ_{P} (\underline{n + 1}) = ∑_{\begin{matrix}F ∈C^{q×n−q+2} \\ 1⩽q⩽n+1 \end{matrix}} csgn(F) c (F) ⊗ r (F) ;  (3.2)

extend Δ_{P} to proper faces u = U_{1}| ⋯ |U_{p} ∈ C_{n−p+1} (u) = C_{n_{1}} (U_{1})⊗⋯⊗C_{n_{p}} (U_{p}) , n_{i} = #U_{i} − 1, via the standard comultiplicative extension.

Example 3. On P_{3}, all but two configuration matrices are step matrices:

\begin{matrix}1 2 3 & 1 2 3 & 1 2 3 & ⟶ R_{3} ⟶ & 1 2 3 \\ 2 1 3 & 1 2 3 & 1 3 2 & ⟶ D_{3} ⟶ & 1 2 3 \end{matrix}

Consequently,

Δ_{P} (\underline{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.

There is a computational shortcut worth mentioning. Since F ∈ C if and only if F^{T} ∈ C, we only need to derive half of the configuration matrices.

Definition 12. For F ∈ C, define the \underline{transpose} of c (F) ⊗ r (F) to be

[c (F) ⊗ r (F)]^{T} = c (F^{T} ) ⊗ r (F^{T} ) .

Example 4. Refer to Example 3 and note that each component in the right-hand column is the transpose of the component to its left. On P_{4} we have:

Δ_{P} (\underline{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 a proof of the fact that Δ_{P} is a chain map. First note that

Δ_{P} ∂ (\underline{n + 1}) = ∑ ±Δ_{P} (M) |Δ_{P} (N)
= ∑ ± (u_{i} ⊗ v_{j}) | (u^{k} ⊗ v^{ℓ}) = ∑ ±u_{i}|u^{k} ⊗ v_{j}|v^{ℓ},

where u_{i} ⊗ v_{j} = c (F_{j×i}) ⊗ r (F_{j×i}) , u^{k} ⊗ v^{ℓ} = c (F^{ℓ×k}) ⊗ r (F^{ℓ×k}) and F_{j×i} and F^{ℓ×k} range over all configurations matrices with entries from M and N, respectively. Although u_{i}|u^{k} ⊗ v_{j}|v^{ℓ} is not a CP, there is the associated block matrix

\begin{matrix}0 & F^{ℓ×k} \\ F_{j×i} & 0 \end{matrix} .  (3.3)

Thus the components of Δ_{P} ∂ (\underline{n + 1}) lie in one-to-one correspondence with all such block matrices. Let a_{i} ⊗ b_{j} = A_{1}| ⋯ |A_{i} ⊗ B_{j}| ⋯ |B_{1} and a^{k} ⊗ b^{ℓ} = A^{1}| ⋯ |A^{k} ⊗ B^{ℓ}| ⋯ |B^{1} be the SCP’s related to u_{i} ⊗ v_{j} and u^{k} ⊗ v^{ℓ}. Denoting a column (or row) by its set of non-zero entries, the step matrices

A_{1} ⋯ A_{i} = B_{1} ; ⋮ ; B_{j} and A^{1} ⋯ A^{k} = B^{1} ; ⋮ ; B^{ℓ}

involve elements of M and N, respectively, and the block matrix associated with the pairing a_{i}|a^{k} ⊗ b_{j}|b^{ℓ} is

\begin{aligned}& 0 & & A^{1} & ⋯ & A^{k} \\ A_{1} & ⋯ & A_{i} & & 0 \end{aligned} = B^{1} ; 0  ⋮ ; B^{ℓ} ; B_{1} ; ⋮  0 ; B_{j} .

Our main result combines the statements in Lemmas 1 and 2 below:

Theorem 1. The cellular boundary map ∂ : C_{∗} (P_{n+1}) → C_{∗} (P_{n+1}) is a Δ_{P} - coderivation for all n ⩾ 1.

Corollary 1. (C_{∗} (P_{n+1}) , Δ_{P} , ∂) is a DG coalgebra and the cellular projection ρ_{n+1} : P_{n+1} → I^{n} induces a DG coalgebra map

(ρ_{n+1})_{∗} : C_{∗}(P_{n+1}) → C_{∗}(I^{n}).

Lemma 1. Each non-zero component (u_{i} ⊗ v_{j}) | (u^{k} ⊗ v^{ℓ}) of Δ_{P} ∂ (\underline{n + 1}) is a nonzero component of (1 ⊗ ∂ + ∂ ⊗ 1) Δ_{P} (\underline{n + 1}) .

Proof. Consider a component (u_{i} ⊗ v_{j}) | (u^{k} ⊗ v^{ℓ}) of Δ_{P} ∂ (\underline{n + 1}) , where u_{i} ⊗ v_{j} = U_{1}| ⋯ |U_{i} ⊗ V_{j}| ⋯ |V_{1} is a CP of partitions of M = U_{1} ∪ ⋯ ∪ U_{i} and u^{k} ⊗ v^{ℓ} = U^{1}| ⋯ |U^{k} ⊗ V^{ℓ}| ⋯ |V^{1} is a CP of partitions of N = \underline{n + 1}⧹M. The related SCP’s a_{i} ⊗ b_{j} = A_{1}| ⋯ |A_{i} ⊗ B_{j}| ⋯ |B_{1} and a^{k} ⊗ b^{ℓ} = A^{1}| ⋯ |A^{k} ⊗ B^{ℓ}| ⋯ |B^{1} give the component (a_{i} ⊗ b_{j}) | (a^{k} ⊗ b^{ℓ}) of Δ_{P} ∂ (\underline{n + 1}) . Let E = (e_{i,j}) be the block matrix associated with a_{i}|a^{k} ⊗ b_{j}|b^{ℓ}. There are two cases:

\underline{Case 1} : e_{ℓ+1,i} > e_{ℓ,i+1}.

Then min U_{i} = min A_{i} > max A^{1} ⩾ max U^{1} and the CP

u ⊗ v = U_{1}| ⋯ |U_{i−1}|U^{1} ∪ U_{i}|U^{2}| ⋯ |U^{k} ⊗ v_{j}|v^{ℓ}

is a component of Δ_{P} (\underline{n + 1}) with associated configuration matrix

F = \begin{aligned}& 0 & & U^{1} & ⋯ & & U^{k} \\ U_{1} & & ⋯ & U_{i} & & 0 \end{aligned} = v^{ℓ} ; v_{j} .

It follows that u_{i}|u^{k} ⊗v = d_{U_{i}}^{i} (u)⊗v is a component of (1 ⊗ ∂ + ∂ ⊗ 1) Δ_{P} (\underline{n + 1}) . To check signs, we verify that the product of expressions (I) through (VI) below is 1. Let V′_{q}|...|V′_{1} = v_{j}|v^{ℓ} and note that u ⊗ v = c (F) ⊗ r (F) is related to the SCP a ⊗ b = A_{1}| ⋯ |A_{i−1}|A^{1} ∪ A_{i}|A^{2}| ⋯ |A^{k} ⊗ b_{j}|b^{ℓ} = c (E) ⊗ r (E) .

I. csgn(F) = I_{1} · I_{2} · I_{3} · I_{4} · I_{5} = (−1)^{\binom{q}{2}} · [sgn_{2}u · sgn_{2}a] · rsgn(a) · (−1)^{ϵ′_{1}} · psgn(v), where ϵ′_{1} = ∑_{i=1}^{q−1} i · #V′_{i+1}.

II. sgn(d_{U_{i}}^{i} (u)) = II_{1} · II_{2} = (−1)^{#M+i+1} · (−1)^{#U_{i}#U^{1}}, where the shuffle sign II_{2} follows by assumption.

III. sgn (d_{M} (\underline{n + 1})) = III_{1} · III_{2} = (−1)^{#M} · shuff(M; N).

IV. csgn(F_{j×i}) = IV_{1} · IV_{2} · IV_{3} · IV_{4} · IV_{5} = (−1)^{\binom{j}{2}} ·[sgn_{2}u_{i} ·sgn_{2}a_{i}]·rsgn(a_{i})· (−1)^{ϵ_{1}} · psgn(v_{j}), where ϵ_{1} = ∑_{i=1}^{j−1} i · #V_{i+1}.

V. csgn(F^{ℓ×k}) = V_{1} · V_{2} · V_{3} · V_{4} · V_{5} = (−1)^{\binom{ℓ}{2}} · [sgn_{2}u^{k} · sgn_{2}a^{k}] · rsgn(a^{k}) · (−1)^{ϵ^{1}} · psgn(v^{ℓ}), where ϵ^{1} = ∑_{i=1}^{ℓ−1} i · #V^{i+1}.

VI. (−1)^{dim u^{k} dim v_{j}} = (−1)^{(ℓ−1)(i−1)} (u_{i} ⊗ v_{j} is a component of Δ_{P} (M) ; hence dim (u_{i} ⊗ v_{j}) = #M − 1 and dim v_{j} = #M − 1 − dim u_{i} = i − 1).

Then by straightforward calculation,

(1) I_{5} · III_{2} · IV_{5} · V_{5} = 1;

(2) I_{2} · IV_{2} · V_{2} = I_{3} · II_{2} · IV_{3} · V_{3} = (−1)^{#A_{i}#A^{1}+#U_{i}#U^{1}} ;

(3) I_{1} · IV_{1} · V_{1} = (I_{4} · IV_{4} · V_{4}) · (II_{1} · III_{1}) · VI = (−1)^{jℓ}

(#M = i + j − 1 since v_{j} = r (F_{j×i})). \underline{Case 2} : e_{ℓ+1,i} < e_{ℓ,i+1}.

Then max (V_{1}) ⩽ max (B_{1}) < min (B^{ℓ}) = min (V^{ℓ}) and the CP

u ⊗ v = u_{i}|u^{k} ⊗ V_{j}| ⋯ |V_{1} ∪ V^{ℓ}| ⋯ |V^{1}

is a component of Δ_{P} (\underline{n + 1}) with associated configuration matrix

F = V^{1} ; 0  ⋮ ; V_{1}  V^{ℓ} ; ⋮  0 ; V_{j} = u_{i}  u^{k}

It follows that u_{i}|u^{k}⊗v_{j}|v^{ℓ} = u⊗d_{ℓ}^{V_{1}} (v) is a component of (1 ⊗ ∂ + ∂ ⊗ 1) Δ_{P} (\underline{n + 1}). The sign check is similar to the one in Case 1 above and is left to the reader.

Lemma 2. Each non-zero component d_{M}^{k}(u) ⊗ v or u ⊗ d_{ℓ}^{N} (v) of (1 ⊗ ∂ + ∂ ⊗ 1) Δ_{P} (\underline{n + 1}) is a non-zero component of Δ_{P} ∂ (\underline{n + 1}) .

Proof. For simplicity we work with ℤ_{2} coefficients; sign checks with ℤ coefficients are straightforward calculations and left to the reader. Given an SCP a⊗b = c (E)⊗ r (E) = A_{1}| ⋯ A_{p} ⊗ B_{q}| ⋯ |B_{1} of partitions of \underline{n + 1}, let u ⊗ v = c (F) ⊗ r (F) = U_{1}| ⋯ |U_{p} ⊗ V_{q}| ⋯ |V_{1} be a related CP. Then there exist M_{j} ⊂ A_{j} and N_{i} ⊂ B_{i} with min M_{j} > max A_{j+1} and min N_{i} > max B_{i+1} such that

F = D_{N_{q−1}} ⋯ D_{N_{1}}R_{M_{p−1}} ⋯ R_{M_{1}}E.  (3.4)

Then u ⊗ v is a non-zero component of Δ_{P} (\underline{n + 1}) . For each proper M ⊂ U_{k}, we prove that the component d_{M}^{k}(u) ⊗ v of (1 ⊗ ∂ + ∂ ⊗ 1) Δ_{P} (\underline{n + 1}) is a non-zero component of Δ_{P} ∂ (\underline{n + 1}) if and only if the following conditions hold:

(1) m = min M ∈ A_{k}; (2) (m, M] = (m, A_{k} ∪ M_{k−1}] ;

(3) m ∈ B_{r} implies N_{r−1} = ∅.

The dual statement for u ⊗ d_{ℓ}^{N} (v) with N ⊂ V_{ℓ} and is also true; the proof follows by ”mirror symmetry.” Suppose conditions (1) - (3) hold. Set M_{0} = M_{p} = ∅; then clearly, U_{i} = (A_{i} ∪ M_{i−1}) \ M_{i} for 1 ⩽ i ⩽ p, and M_{k−1} ⊆ M by conditions (1) and (2). Thus U_{1} ∪ ⋯ ∪ U_{k−1} ∪ M = A_{1} ∪ ⋯ ∪ A_{k−1} ∪ M and it follows that d_{M}^{k}(u) ⊗ v is the non-zero component

Δ_{P} (A_{1} ∪ ⋯ ∪ A_{k−1} ∪ M | A_{k} \ M ∪ A_{k+1} ∪ ⋯ ∪ A_{p})

of Δ_{P} ∂ (\underline{n + 1}) . Conversely, if conditions (1) - (3) fail to hold, we prove that there exists a unique CP ū ⊗ v̄ ≠ u ⊗ v such that u ⊗ v + ū ⊗ v̄ ∈ ker (∂ ⊗ 1 + 1 ⊗ ∂) .

For existence, we consider all possible cases.

\underline{Case 1} : Assume (1)′ : m ∉ A_{k}.

Let

ū = U_{1}| ⋯ |U_{k−1} ∪ M|U_{k} \ M| ⋯ |U_{p};

then

d_{U_{k−1}}^{k−1}(ū) ⊗ v = d_{M}^{k}(u) ⊗ v.

Now M ⊂ M_{k−1} since m ∈ M_{k−1}; hence ū ⊗ v may be obtained by replacing R_{M_{k−1}} with R_{M_{k−1}\M} in (3.4) and ū ⊗ v is a CP related to a ⊗ b.

\underline{Case 2} : Assume (1) ∧ (2)′ : m ∈ A_{k} and (m, M] ⊂ (m, A_{k} ∪ M_{k−1}] .

Let

μ = min (m, A_{k} ∪ M_{k−1}] \ M and L = [A_{k}, m) ∪ μ.

Note that μ ∈ A_{i} for some 1 ⩽ i ⩽ k.

\underline{Subcase 2A}: Assume min L > max A_{k+1}, k < p.

Let

ū = U_{1}| ⋯ |M| (U_{k} \ M) ∪ U_{k+1}| ⋯ |U_{p};

then

d_{U_{k}\M}^{k+1} \binom{}{ū} ⊗ v = d_{M}^{k} (u) ⊗ v.

Note that min A_{k} = m since min L > max A_{k+1} > min A_{k}. Thus L = μ. Now, min M_{k} > max A_{k+1} by (3.4) and min U_{k} \ M = min [(A_{k} ∪ M_{k−1}) \ M_{k}] \ M ⩾ min (A_{k} ∪ M_{k−1}) \ M = min (m, A_{k} ∪ M_{k−1}] \ M = μ = min L > max A_{k+1} so that min M_{k} ∪ (U_{k} \ M) > max A_{k+1}. Hence ū ⊗ v can be obtained by replacing R_{M_{k}} with R_{M_{k}∪(U_{k}\M)} in (3.4) and ū ⊗ v is a CP related to a ⊗ b.

\underline{Subcase 2B}: min L < max A_{k+1} with k ⩽ p.

\underline{Subcase 2B1} : Assume min A_{i−1} > max A_{i} \ μ with μ ∈ A_{i} and 1 < i ⩽ k.

When i = k let

ū = U_{1}| ⋯ |U_{k−1} ∪ M|U_{k} \ M| ⋯ |U_{p};

and when 1 < i < k, let

ū = U_{1}| ⋯ |U_{i−1} ∪ U_{i}| ⋯ |M|U_{k} \ M| ⋯ |U_{p}.

Then for all i ⩽ k,

d_{M}^{k} (u) ⊗ v = d_{U_{i−1}}^{i−1} \binom{}{ū} ⊗ v.

When i = k, min A_{k−1} ∪ (A_{k} ∩ M) ⩽ min A_{k} ∩ M < μ = max A_{k} = max A_{k} \ M so that

ā ⊗ b̄ = A_{1}| ⋯ |A_{k−1} ∪ (A_{k} ∩ M)|A_{k} \ M| ⋯ |A_{p} ⊗ b

is an SCP; let Ē be the associated step matrix and let

F̄ = D_{N_{q−1}} ⋯ D_{N_{1}}R_{M_{p−1}} ⋯ R_{M_{k}}R_{M_{k−1}\M} ⋯ R_{M_{1}} Ē.

When i < k, we have μ = max A_{i} > max A_{k} ⩾ max A_{k} ∩ M so that min A_{k} ∩ M < max L; furthermore, max A_{k} = max A_{k} ∩ M by the minimality of μ so that min A_{k−1} < max A_{k} ∩ M. And finally, min L < max A_{k+1} by assumption 2B. Thus

ā ⊗ b̄ = A_{1}| ⋯ |A_{i−1} ∪ A_{i} \ μ| ⋯ |A_{k} ∩ M|L| ⋯ |A_{p}
⊗ B_{q}| ⋯ |B_{r+1}|B_{r−1}| ⋯ |B_{j} ∪ μ| ⋯ |B_{1}

is an SCP; let Ē be the associated step matrix. Note that U_{i−1} ∪ U_{i} = (A_{i−1} ∪ M_{i−2} ∪ A_{i} \ μ) \ (M_{i} \ μ) and μ ∈ M_{j} for i ⩽ j ⩽ k − 1. Let

F̄ = D_{N_{q−1}} ⋯ D_{N_{r−1}∪μ} ⋯ D_{N_{j}∪μ} ⋯ D_{N_{1}}
R_{M_{p−1}} ⋯ R_{M_{k}}R_{(M_{k−1}\μ)\M}^{k−1}R_{M_{k−1}\μ}^{k−2} ⋯ R_{M_{i}\μ}^{i−1} ⋯ R_{M_{1}} Ē,

where μ ∈ B_{r}, B̄_{j}. Then for all i ⩽ k, ū ⊗ v = c \binom{}{F̄} ⊗ r \binom{}{F̄} is a CP related to ā ⊗ b̄.

\underline{Subcase 2B2} : Assume min A_{i−1} < max A_{i} \ μ with μ ∈ A_{i} and 1 < i ⩽ k.

Let

ū ⊗ v̄ = U_{1}| ⋯ |M|U_{k} \ M| ⋯ |U_{p} ⊗ V_{q}| ⋯ |V_{r} ∪ V_{r−1}| ⋯ |V_{1},

where μ ∈ B_{r}, B̄_{j}. Then

d_{M}^{k}(u) ⊗ v = ū ⊗ d_{r−1}^{V_{r−1}}(v̄).

When i = k, max L = μ ∈ A_{k} so that min A_{k−1} < max A_{k} \ μ = max A_{k} \ L. Furthermore, min A_{k} \ L = m < μ = max L; and finally, min L < max A_{k+1} by assumption 2B. Thus

ā ⊗ b̄ = A_{1}| ⋯ |M|L| ⋯ |A_{p} ⊗ B_{q}| ⋯ |B_{r+1}|B_{r−1}| ⋯ |B_{j} ∪ μ| ⋯ |B_{1}

is an SCP; let Ē be the associated step matrix. Since min (μ, A_{k} ∪ M_{k−1}]\M > μ = max L, the operator R_{(μ,A_{k}∪M_{k−1}]\M}^{k} is defined. Note that M_{k} ⊂ L∪(μ, A_{k} ∪ M_{k−1}]\ M and let

F̄ = D_{N_{q−1}}^{q−2} ⋯ D_{N_{r}}^{r−1}D_{N_{r−2}∪μ} ⋯ D_{N_{j}∪μ} ⋯ D_{N_{1}}
R_{M_{p−1}}^{p} ⋯ R_{M_{k}}^{k+1}R_{(μ,A_{k}∪M_{k−1}]\M}^{k} ⋯ R_{M_{1}} Ē.

When 1 < i < k we have min A_{i−1} < max A_{i}\μ by assumption 2B2, and min A_{i}\μ < max A_{i+1} since μ ∈ A_{i} ∩ M_{k−1} implies μ > min A_{i}. Next, min A_{k−1} < max A_{k} = max A_{k} ∩ M since max A_{k} < μ ∈ A_{i}, and min A_{k} ∩ M < μ = max L. Finally, min L < max A_{k+1} by assumption 2B. Thus

ā ⊗ b̄ = A_{1}| ⋯ |A_{i} \ μ| ⋯ |A_{k} ∩ M|L| ⋯ |A_{p}
⊗ B_{q}| ⋯ |B_{r+1}|B_{r−1}| ⋯ |B_{j} ∪ μ| ⋯ |B_{1}

is an SCP; let Ē be the associated step matrix. Since min M_{k−1} = min M_{k−1} \ M = μ > max A_{k}, both R_{M_{k−1}\μ} and R_{(M_{k−1}\μ)\M} are defined, so let

F̄ = D_{N_{q−1}}^{q−2} ⋯ D_{N_{r}}^{r−1}D_{N_{r−2}∪μ} ⋯ D_{N_{j}∪μ} ⋯ D_{N_{1}}
R_{M_{p−1}}^{p} ⋯ R_{M_{k}}^{k+1}R_{(M_{k−1}\μ)\M}^{k}R_{M_{k−1}\μ} ⋯ R_{M_{i}\μ} ⋯ R_{M_{1}} Ē.

Then for all i ⩽ k, ū ⊗ v = c \binom{}{F̄} ⊗ r \binom{}{F̄} is a CP related to ā ⊗ b̄.

\underline{Case 3} : Assume (1) ∧ (2) ∧ (3)′ : m ∈ A_{k} ∩ B_{r}, (m, M] = (m, A_{k} ∪ M_{k−1}] and N_{r−1} ≠ ∅.

Note that M_{k} ⊂ (A_{k} ∪ M_{k−1}) \ M = [A_{k}, m) by conditions (1) and (2) so that U_{k} \ M = [A_{k}, m) \ M_{k}. Let ν = min N_{r−1}; then ν ∈ B_{i} ∩ A_{j} for some 1 ⩽ i ⩽ r − 1 and

j = k + #[B_{i}, ν) + ∑_{s=i+1}^{r−1} (#B_{s} − 1) .

\underline{Subcase 3A}: Assume A_{j} = ν.

In subcases 3A1 and 3A2, ū is defined so that

d_{[A_{k},m)}^{k+1}(ū) ⊗ v = d_{M}^{k}(u) ⊗ v.

\underline{Subcase 3A1} : j = k + 1.

Let

ū = U_{1}| ⋯ |M| (U_{k} \ M) ∪ U_{k+1}|U_{k+2}| ⋯ |U_{p}.

But ν > m since ν ∈ A_{k+1} ∩ N_{r−1}, consequently M_{k} = ∅ so that U_{k} \ M = [A_{k}, m) and U_{k+1} = A_{k+1} = ν; thus M_{k+1} = ∅. Clearly

ā ⊗ b̄ = A_{1}| ⋯ |A_{k} ∩ M| [A_{k}, m) ∪ ν|A_{k+2}| ⋯ |A_{p}
⊗ B_{q}| ⋯ |B_{r} ∪ ν| ⋯ |B_{i} \ ν| ⋯ |B_{1}

is an SCP; let Ē be the associated step matrix and let

F̄ = D_{N_{q−1}} ⋯ D_{N_{r−1}\ν} ⋯ D_{N_{i}\ν} ⋯ D_{N_{1}}R_{M_{p−1}} ⋯ R_{∅}^{k+1}R_{∅}^{k} ⋯ R_{M_{1}} Ē;

then ū ⊗ v = c \binom{}{F̄} ⊗ r \binom{}{F̄} is a CP related to ā ⊗ b̄.

\underline{Subcase 3A2} : j > k + 1.

Let

ū = U_{1}| ⋯ |M|U_{k} \ M| ⋯ |U_{j−1} ∪ U_{j}|U_{j+1}| ⋯ |U_{p}.

Again, ν > m implies that M_{j−1} = ∅ and U_{j} = A_{j} = ν. Clearly

ā ⊗ b̄ = A_{1}| ⋯ |A_{k} ∩ M| [A_{k}, m) ∪ ν| ⋯ |A_{j−1}|A_{j+1}| ⋯ |A_{p}
⊗ B_{q}| ⋯ |B_{r} ∪ ν| ⋯ |B_{i} \ ν| ⋯ |B_{1}

is an SCP; let Ē be the associated step matrix and let

F̄ = D_{N_{q−1}} ⋯ D_{N_{r−1}\ν} ⋯ D_{N_{i}\ν} ⋯ D_{N_{1}}
R_{M_{p−1}} ⋯ R_{∅}^{j}R_{M_{j−2}∪ν}^{j−1} ⋯ R_{M_{k+1}∪ν}^{k+2}R_{M_{k}∪ν}^{k+1}R_{∅}^{k} ⋯ R_{M_{1}} Ē;

then ū ⊗ v = c \binom{}{F̄} ⊗ r \binom{}{F̄} is a CP related to ā ⊗ b̄.

\underline{Subcase 3B}: Assume A_{j} ≠ ν.

Note that i > 1 by assumption and let

ū ⊗ v̄ = U_{1}| ⋯ |M|U_{k} \ M| ⋯ |U_{p} ⊗ V_{q}| ⋯ |V_{i} ∪ V_{i−1}| ⋯ |V_{1};

then

d_{M}^{k}(u) ⊗ v = ū ⊗ d_{i−1}^{V_{i−1}} \binom{}{v̄} .

Note that ν > m implies M_{j−1} = ∅ and U_{j} = A_{j} \ M_{j}. Clearly

ā ⊗ b̄ = A_{1}| ⋯ |A_{k} ∩ M| [A_{k}, m) ∪ ν| ⋯ |A_{j−1}|A_{j} \ ν|A_{j+1}| ⋯ |A_{p}
⊗ B_{q}| ⋯ |B_{r} ∪ ν| ⋯ |(B_{i} ∪ B_{i−1}) \ ν| ⋯ |B_{1}

is a SCP; let Ē be the associated step matrix and let

F̄ = D_{N_{q−1}} ⋯ D_{N_{r−1}\ν} ⋯ D_{N_{i}\ν} ⋯ D_{N_{1}}
R_{M_{p−1}}^{p} ⋯ R_{M_{j}}^{j+1}R_{M_{j−1}∪ν}^{j} ⋯ R_{M_{k}∪ν}^{k+1}R_{∅}^{k} ⋯ R_{M_{1}} Ē;

then ū ⊗ v̄ = c \binom{}{F̄} ⊗ r \binom{}{F̄} is a CP related to ā ⊗ b̄.

For uniqueness of each pair ū ⊗ v̄ constructed above, note the transformations R and D fix minimal elements, i.e., if ū ⊗ v̄ = R(ā) ⊗ D(b̄), then necessarily min Ū_{i} = min Ā_{i} and min V̄_{i} = min B̄_{i} for all i; in particular, if R(ā) = R̃(a′) or D(b̄) = D̃(b′) then min Ā_{i} = min A′_{i} or min B̄_{i} = min B′_{i}. Consequently, for d_{M}^{k}(u)⊗v or u⊗d_{ℓ}^{N}(v) in the cases above, there is exactly one way to construct a step matrix Ē so that ā is step increasing and b̄ is step decreasing (it is straightforward to check that a construction with distinct u ⊗ v, ū ⊗ v̄, and u′ ⊗ v′ would contradict the necessary condition above either for a and a′ or for b and b′). This completes the proof.

4. Permutahedral Sets

This section introduces the notion of a permutahedral set Z, which is a combinatorial object generated by permutahedra and equipped with appropriate face and degeneracy operators. We construct the generating category P and show how to lift the diagonal on the permutahedra P constructed above to a diagonal on Z. Naturally occurring examples of permutahedral sets include the double cobar construction, i.e., Adams’ cobar construction [1] on the cobar with coassociative coproduct [2], [3], [8] (see Subsection 4.5 below). Permutahedral sets are distinguished from simplicial or cubical sets by their higher order structure relations. While our construction of P follows the analogous (but not equivalent) construction for polyhedral sets given by D.W. Jones in [7], there is no mention of structure relations in [7].

4.1. Singular Permutahedral Sets

By way of motivation we begin with constructions of two singular permutahedral sets–our universal examples. Whereas the first emphasizes coface and codegeneracy operators, the second emphasizes cellular chains and is appropriate for homology theory. We begin by constructing the various maps we need to define singular coface and codegeneracy operators.

Fix a positive integer n. For 0 ⩽ p ⩽ n, let

\underline{p} = \{ \begin{matrix}∅, & p = 0 \\ \{1, …, p\} , & 1 ⩽ p ⩽ n \end{matrix} and \overline{p} = \{ \begin{matrix}∅, & p = 0 \\ \{n − p + 1, …, n\} , & 1 ⩽ p ⩽ n; \end{matrix}

then \underline{p} and \overline{p} contain the first and last p elements of \underline{n}, respectively; note that \underline{p} ∩ \overline{q} = \{p\} whenever p + q = n + 1. Given integers r, s ∈ \underline{n} such that r + s = n + 1, there is a canonical projection Δ_{r,s} : P_{n} → P_{r} × P_{s} whose restriction to a vertex v = a_{1}| ⋯ |a_{n} ∈ P_{n} is given by

Δ_{r,s}(v) = b_{1}| ⋯ |b_{r} × c_{1}| ⋯ |c_{s},

where (b_{1}, …, b_{r}; c_{1}, …, c_{k−1}, c_{k+1}, …, c_{s}) is the unshuffle of (a_{1}, …, a_{n}) with b_{i} ∈ \underline{r}, c_{j} ∈ \overline{s}, c_{k} = r. For example, Δ_{2,3}(2|4|1|3) = 2|1 × 2|4|3 and Δ_{3,2}(2|4|1|3) = 2|1|3 × 4|3. Since the image of the vertices of a cell of P_{n} uniquely determines a cell in P_{r} × P_{s} the map Δ_{r,s} is well-defined and cellular. Furthermore, the restriction of Δ_{r,s} to an (n − k)-cell A_{1}| ⋯ |A_{k} ⊂ P_{n} is given by

Δ_{r,s} (A_{1}| ⋯ |A_{k}) = \{ \begin{matrix}\underline{r} × (A_{1}| ⋯ |A_{i} \ \underline{r − 1} | ⋯ |A_{k}) , & if \underline{r} ⊆ A_{i}, some i, \\ (A_{1}| ⋯ |A_{j} \ \overline{s − 1} | ⋯ |A_{k}) × \overline{s}, & if \overline{s} ⊆ A_{j}, some j, \\ \begin{matrix}(A_{1} \ \overline{s − 1} | ⋯ |A_{k} \ \overline{s − 1}) \\ × (A_{1} \ \underline{r − 1} | ⋯ |A_{k} \ \underline{r − 1}) , \end{matrix} & otherwise. \end{matrix}

Note that Δ_{r,s} acts homeomorphically in the first two cases and degeneratively in the third when 1 < k < n. When n = 3 for example, Δ_{2,2} maps the edge 1|23 onto the edge 1|2 × 23 and the edge 13|2 onto the vertex 1|2 × 3|2 (see Figure 3).

• • •  • • • 123 1|23  3|12 13|2  23|1 2|13 12|3  Δ_{2,2}\overline{}1|2 × 23  2|1 × 23 12 × 3|2 12 × 2|3 • •  • • 12 × 23

Figure 3: The projection Δ_{2,2} : P_{3} → I^{2}.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; Δ_{3,2}; 1234; 123 × 34; 12 × 234; 12 × 23 × 34; 1 × Δ_{2,2}; Δ_{2,2} × 1; Δ_{2,3}]

Figure 4: The projection ρ_{4} : P_{4} → I^{3}.

Now identify the set U = {u_{1} < ⋯ < u_{n}} with P_{n} and the ordered partitions of U with the faces of P_{n} in the obvious way. Then (Δ_{r,s} × 1)∘Δ_{r+s−1,t} = (1 × Δ_{s,t})∘ Δ_{r,s+t−1} whenever r + s + t = n + 2 so that Δ_{∗,∗} acts coassociatively with respect to Cartesian product. It follows that each k-tuple (n_{1}, …, n_{k}) ∈ ℕ^{k} with k ⩾ 2 and n_{1} + ⋯ + n_{k} = n + k − 1 uniquely determines a cellular projection Δ_{n_{1}···n_{k}} : P_{n} → P_{n_{1}} × ⋯ × P_{n_{k}} given by the composition

Δ_{n_{1}···n_{k}} = (Δ_{n_{1},n_{2}} × 1^{×k−2}) ∘ ⋯ ∘ (Δ_{n_{(k−2)}−k+3,n_{k−1}} × 1) ∘ Δ_{n_{(k−1)}−k+2,n_{k}}, where n_{(q)} = n_{1} + ⋯ + n_{q}; and in particular,

Δ_{n_{1}···n_{k}} (\underline{n}) = \underline{n_{1}} × \underline{n_{(2)} − 1} \ \underline{n_{1} − 1} × ⋯ × \underline{n_{(k)} − (k − 1)} \ \underline{n_{(k−1)} − (k − 1)}. (4.1)

Note that formula 4.1 with k = n − 1 and n_{i} = 2 for all i defines a projection ρ_{n} : P_{n} → I^{n−1}

ρ_{n} (\underline{n}) = Δ_{2···2} (\underline{n}) = 12 × 23 × ⋯ × \{n − 1, n\}

(see Figure 4) acting on a vertex u = u_{1}| ⋯ |u_{n} as follows: For each i ∈ \underline{n − 1}, let {u_{j}, u_{k} | j < k} = {u_{1}, …, u_{n}} ∩ {i, i + 1} and set v_{i} = u_{j}, v_{i+1} = u_{k}; then ρ_{n}(u) = v_{1}|v_{2} × ⋯ × v_{n−1}|v_{n}.

Now choose a (non-cellular) homeomorphism γ_{n} : I^{n−1} → P_{n} whose restriction to a vertex v = v_{1}|v_{2} × ⋯ × v_{n−1}|v_{n} can be expressed inductively as follows: Set A_{2} = v_{1}|v_{2}; if A_{k−1} has been obtained from v_{1}|v_{2} × ⋯ × v_{k−2}|v_{k−1}, set

A_{k} = \{ \begin{matrix}A_{k−1}|k, & if v_{k} = k, \\ k|A_{k−1}, & otherwise. \end{matrix}

For example, γ_{4} (2|1 × 3|2 × 3|4) = 3|2|1|4. Then γ_{n} sends the vertices of I^{n−1} to cubical vertices of P_{n} and the vertices of P_{n} fixed by γ_{n}ρ_{n} are exactly its cubical vertices. Given a codimension 1 face A|B ⊂ P_{n}, index the elements of A and B as follows: If n ∈ A, write A = {a_{1} < ⋯ < a_{m}} and B = {b_{1} < ⋯ < b_{ℓ}}; if n ∈ B, write A = {a_{1} < ⋯ < a_{ℓ}} and B = {b_{1} < ⋯ < b_{m}} . Then A|B uniquely embeds in P_{n} as the subcomplex

P_{ℓ} × P_{m} = \{ \begin{matrix}a_{1}| ⋯ |a_{m}|B × A|b_{1}| ⋯ |b_{ℓ}, & if n ∈ A \\ A|b_{1}| ⋯ |b_{m} × a_{1}| ⋯ |a_{ℓ}|B, & if n ∈ B. \end{matrix}

For example, 14|23 embeds in P_{4} as 1|4|23 × 14|2|3. Let ι_{A|B} : A|B ↪ P_{ℓ} × P_{m} denote this embedding and let h_{A|B} = ι_{A|B}^{−1}; then h_{A|B} : P_{ℓ} × P_{m} → A|B is an orientation preserving homeomorphism. Also define the cellular projection

ϕ_{A|B} : P_{n} → P_{ℓ} × P_{m} = \{ \begin{matrix}b_{1} ⋯ b_{ℓ} × a_{1} ⋯ a_{m}, & if n ∈ A \\ a_{1} ⋯ a_{ℓ} × b_{1} ⋯ b_{m}, & if n ∈ B \end{matrix}

on a vertex c = c_{1}| ⋯ |c_{n} by ϕ_{A|B} (c) = u_{1}| ⋯ |u_{ℓ} × v_{1}| ⋯ |v_{m}, where (u_{1}, …, u_{ℓ}; v_{1}, …, v_{m}) is the unshuffle of (c_{1}, …, c_{n}) with u_{i} ∈ B, v_{j} ∈ A when n ∈ A or with u_{i} ∈ A, v_{j} ∈ B when n ∈ B. Note that unlike Δ_{r,s}, the projection ϕ_{A|B} always degenerates on the top cell; furthermore, ϕ_{A|B} ∘ h_{A|B} = ϕ_{B|A} ∘ h_{A|B} = 1. We note that when A or B is a singleton set, the projection ϕ_{A|B} was defined by R.J. Milgram in [14].

The singular codegeneracy operator associated with A|B is the map β_{A|B} : P_{n} → P_{n−1} given by the composition

P_{n} ⟶^{ϕ_{A|B}} P_{ℓ} × P_{m} ⟶^{ρ_{ℓ}×ρ_{m}} I^{ℓ−1} × I^{m−1} = I^{n−2} ⟶^{γ_{n−1}} P_{n−1};

the singular coface operator associated with A|B is the map δ_{A|B} : P_{n−1} → P_{n} given by the composition

P_{n−1} ⟶^{ρ_{n−1}} I^{n−2} = I^{ℓ−1} × I^{m−1} ⟶^{γ_{ℓ}×γ_{m}} P_{ℓ} × P_{m} ⟶^{h_{A|B}} A|B ↪^{i} P_{n}.

Unlike the simplicial or cubical case, δ_{A|B} need not be injective. We shall often abuse notation and write h_{A|B} : P_{ℓ} × P_{m} → P_{n} when we mean i ∘ h_{A|B}.

We are ready to define our first universal example. For future reference and to emphasize the fact that our definition depends only on positive integers, let (n_{1}, …, n_{k}) ∈ ℕ^{k} such that n_{(k)} = n and denote

P_{n_{1}···n_{k}} (n) = \{Partitions A_{1}| ⋯ |A_{k} of \underline{n} | #A_{i} = n_{i}\}.

Definition 13. Let Y be a topological space. The \underline{singular permutahedral set of Y} consists of the singular set

Sing_{∗}^{P} Y = ⋃_{n⩾1} [Sing_{n}^{P} Y = {Continuous maps P_{n}→Y }]

together with singular face and degeneracy operators

d_{A|B} : Sing_{n}^{P} Y → Sing_{n−1}^{P}Y and ϱ_{A|B} : Sing_{n−1}^{P}Y → Sing_{n}^{P} Y

defined respectively for each n ⩾ 2 and A|B ∈ P_{∗∗} (n) as the pullback along δ_{A|B} and β_{A|B}, i.e., for f ∈ Sing_{n}^{P} Y and g ∈ Sing_{n−1}^{P}Y,

d_{A|B}(f) = f ∘ δ_{A|B} and ϱ_{A|B}(g) = g ∘ β_{A|B}.

[figure: δ_{A|B} : P_{n−1} → I^{n−1} → P_{ℓ} × P_{m} → A|B ↪ P_{n}; Y; f; d_{A|B}(f)]

Figure 5: The singular face operator associated with A|B.

Although coface operators δ_{A|B} : P_{n−1} → P_{n} need not be inclusions, the top cell of P_{n−1} is always non-degenerate (c.f. Definition 20); however, the top cell of P_{n−2} may degenerate under quadratic compositions δ_{A|B}δ_{C|D} : P_{n−2} → P_{n} . For example, δ_{12|34}δ_{13|2} : P_{2} → P_{4} is a constant map, since δ_{12|34} : P_{3} → P_{2} × P_{2} ↪ P_{4} sends the edge 13|2 to the vertex 1|2 × 3|2.

Definition 14. A quadratic composition of face operators d_{C|D}d_{A|B} \underline{acts on P_{n}} if the top cell of P_{n−2} is non-degenerate under the composition

δ_{A|B}δ_{C|D} : P_{n−2} → P_{n}.

Theorem 3 below gives the conditions under which a quadratic composition acts on P_{n}. For comparison, quadratic compositions of simplicial or cubical face operators always act on the simplex or cube. When d_{C|D}d_{A|B} acts on P_{n}, we assign the label d_{C|D}d_{A|B} to the codimension 2 face δ_{A|B}δ_{C|D} (\underline{n}). The various paths of descent from the top cell to a cell in codimension 2 gives rise to relations among compositions of face and degeneracy operators (see Figure 6).

• • •  • • • 123 d_{1|2}d_{12|3} = d_{1|2}d_{1|23} d_{1|2}d_{13|2} = d_{2|1}d_{1|23} d_{2|1}d_{13|2} = d_{1|2}d_{3|12}  d_{1|2}d_{2|13} = d_{2|1}d_{12|3} d_{2|1}d_{2|13} = d_{1|2}d_{23|1} d_{2|1}d_{23|1} = d_{2|1}d_{3|12} d_{1|23}  d_{3|12} d_{13|2}  d_{23|1} d_{2|13} d_{12|3}

Figure 6: Quadratic relations on the vertices of P_{3}.

It is interesting to note that singular permutahedral sets have higher order structure relations, an example of which appears below in Figure 7 (see also (4.4)). This distinguishes permutahedral sets from simplicial or cubical sets in which relations are strictly quadratic. Our second universal example, called a “singular multipermutahedral set,” specifies a singular permutahedral set by restricting to maps f = f̄∘ Δ_{n_{1}···n_{k}} for some continuous f̄: P_{n_{1}} × ⋯ × P_{n_{k}} → Y. Face and degeneracy operators satisfy those relations above in which Δ_{n_{1}···n_{k}} plays no essential role.

[figure: P_{2}; P_{1}; δ_{1|2}; P_{2}; δ_{1|23}; P_{3}; δ_{13|2}; P_{3}; δ_{12|34}; P_{4}; Y; β_{2|1}; f; d_{1|23}d_{12|34}(f); d_{2|1}d_{1|23}d_{12|34}(f); d_{12|34}(f); ϱ_{2|1}d_{2|1}d_{1|23}d_{12|34}(f) = d_{13|2}d_{12|34}(f)]

Figure 7: A quartic relation in Sing_{∗}^{P} Y.

Once again, fix a positive integer n, but this time consider (n_{1}, …, n_{k}) ∈ (ℕ ∪ 0)^{k} with n_{(k)} = n − 1 and the projection Δ_{n_{1}+1···n_{k}+1} : P_{n} → P_{n_{1}+1} × ⋯ × P_{n_{k}+1} with Δ_{n} : P_{n} → P_{n} defined to be the identity. Given a topological space Y, let

Sing^{n_{1}···n_{k}}Y = {f̄∘ Δ_{n_{1}+1···n_{k}+1} : P_{n} → Y | f̄ is continuous};

define f, f′ ∈ Sing^{n_{1}···n_{k}}Y to be equivalent if there exists g : P_{n_{1}+1} ×⋯×P_{n_{i−1}+1} × P_{1} × P_{n_{i+1}+1} × ⋯ × P_{n_{k}+1} → Y for some i < k such that

f = g ∘ (1^{×i−1} × ϕ_{\underline{n_{i}+1}|n_{i}+1} × 1^{×k−i−1}) ∘ Δ_{n_{1}+1···n_{i−1}+1,n_{i}+2,n_{i+2}+1···n_{k}+1}

and

f′ = g ∘ (1^{×i} × ϕ_{1|\underline{n_{i+2}+1}\1} × 1^{×k−i−2}) ∘ Δ_{n_{1}+1···n_{i}+1,n_{i+2}+2,n_{i+3}+1···n_{k}+1},

in which case we write f ∼ f′. The geometry of the cube motivates this equivalence; the degeneracies in the product of cubical sets implies the identification (c.f. [10] or the definition of the cubical set functor ΩX in the Appendix).

Define the singular set

Sing_{n}^{M}Y = ⋃_{\begin{matrix}(n_{1},...,n_{k})∈(ℕ∪0)^{k} \\ n_{(k)}=n−1 \end{matrix}} Sing^{n_{1}···n_{k}}Y / ∼ .

Singular face and degeneracy operators

d_{A|B} : Sing_{n}^{M}Y → Sing_{n−1}^{M}Y and ϱ_{A|B} : Sing_{n−1}^{M}Y → Sing_{n}^{M}Y

are defined piece-wise for each n ⩾ 2 and A|B ∈ P_{∗,∗} (n) , depending on the form of A|B. More precisely, for each pair of integers (p_{i}, q_{i}) , 1 ⩽ i ⩽ k, with

p_{i} = 1 + ∑_{j=1}^{i−1} n_{j} and q_{i} = 1 + ∑_{j=i+1}^{k} n_{j}, let

Q_{p_{i},q_{i}} (n) = \{U|V ∈ P_{∗,∗} (n) | (\underline{p_{i}} ⊆ U or \underline{p_{i}} ⊆ V ) and (\overline{q_{i}} ⊆ U or \overline{q_{i}} ⊆ V)\};

in particular, when r + s = n + 1, set k = 2, p_{1} = q_{2} = 1, p_{2} = r and q_{1} = s, then

Q_{r,1} (n) = \{U|V ∈ P_{∗,∗} (n) | \underline{r} ⊆ U or \underline{r} ⊆ V \} and
Q_{1,s} (n) = \{U|V ∈ P_{∗,∗} (n) | \overline{s} ⊆ U or \overline{s} ⊆ V \} .

Since we identify \underline{r}|\overline{s} ⊂ P_{n+1} with P_{r} × P_{s} = Δ_{r,s} (P_{n}) , it follows that A|B ∈ Q_{p_{i},q_{i}} (n) for some i if and only if δ_{A|B}δ_{\underline{r}|\overline{s}} : P_{n−1} → P_{n+1} is non-degenerate; consequently we consider cases A|B ∈ Q_{p_{i},q_{i}} (n) for some i and A|B ∉ Q_{p_{i},q_{i}} (n) for all i.

Since our definitions of d_{A|B} and ϱ_{A|B} are independent in the first case and interdependent in the second, we define both operators simultaneously. But first we need some notation: Given an increasingly ordered set M = {m_{1} < ⋯ < m_{k}} ⊂ ℕ, let I_{M} : M → \underline{#M} denote the indexing map m_{i} ↦ i and let M +z = \{m_{i}+z\} denote translation by z ∈ ℤ. Of course, M − z and M + z are left and right translations when z > 0; we adopt the convention that translation takes preference over set operations.

Assume A|B ∈ Q_{p_{i},q_{i}}(n) for some i, and let

C_{i} = {p_{i}, p_{i} + 1, ..., p_{i} + n_{i}};
A_{i} = (C_{i} ∩ A) − n_{(i−1)}, B_{i} = (C_{i} ∩ B) − n_{(i−1)};
n′_{i} = #(A ∩ C_{i}) − 1, n′′_{i} = #(B ∩ C_{i}) − 1.  (4.2)

For example, n = 6, n_{1} = 3 and n_{2} = 2 determines the projection Δ_{4,3} : P_{6} → 1234 × 456 and pairs (p_{1}, q_{1}) = (1, 3) and (p_{2}, q_{2}) = (4, 1) . Thus A|B = 1234|56 ∈ Q_{3,2}(6) and the composition δ_{\underline{4}|\overline{3}}δ_{A|B} : P_{5} → P_{7} is non-degenerate. Furthermore, C_{2} = 456, A_{2} = (456 ∩ 1234) − 3 = 1, B_{2} = 23, n′_{i} = 0, n′′_{i} = 1 and we may think of d_{A|B} acting on 1234 × 456 as 1 × d_{1|23}.

[figure: P_{n−1}; P_{n}; Δ_{n′_{1}+1,n{′′ \atop 1}+1,n_{2}+1}; h_{A_{1}|B_{1}} ×1; P_{n′_{1}+1}×P_{n{′′ \atop 1}+1}×P_{n_{2}+1}; P_{n_{1}+1}×P_{n_{2}+1}; Y; Δ_{n_{1}+1,n_{2}+1}; f̄; f; d_{A|B}(f); f̃; P_{n}; P_{n−1}; Δ_{n′_{1}+1,n{′′ \atop 1}+1,n_{2}+1}; ϕ_{A_{1}|B_{1}} ×1; P_{n′_{1}+1}×P_{n{′′ \atop 1}+1}×P_{n_{2}+1}; P_{n_{1}+1}×P_{n_{2}+1}; Δ_{n_{1}+1,n_{2}+1}; g̃; g; ϱ_{A|B}(g); ḡ]

Figure 8: Face and degeneracy operators when i = 1 and k = 2.

For f = f̄ ∘ Δ_{n_{1}+1···n_{k}+1} ∈ Sing_{n}^{M}Y, let f̃ = f̄ ∘ (1^{×i−1} × h_{A_{i}|B_{i}} × 1^{×k−i}) and define

d_{A|B}(f) = f̃∘ Δ_{n_{1}+1···n′_{i}+1,n′′_{i}+1···n_{k}+1}.

Dually, note that n′_{i}+n′′_{i} = n_{i}−1 implies the sum of coordinates (n_{1}, …, n_{i−1}, n′_{i}, n′′_{i}, n_{i+1}, …, n_{k}) ∈ (ℕ ∪ 0)^{k+1} is n − 2. So for g = ḡ ∘ Δ_{n_{1}+1···n′_{i}+1,n′′_{i}+1···n_{k}+1} ∈ Sing_{n−1}^{M}Y, let g̃ = ḡ ∘ (1^{×i−1} × ϕ_{A_{i}|B_{i}} × 1^{×k−i}) and define

ϱ_{A|B}(g) = g̃ ∘ Δ_{n_{1}+1···n_{k}+1}

(see Figure 8).

On the other hand, assume that A|B ∉ Q_{p_{i},q_{i}}(n) for all i and define d_{A|B} inductively as follows: When k = 2, set r = n_{1} + 1, s = n_{2} + 1 and let

\begin{matrix}K|L = & \{ \begin{matrix}(\underline{r} ∩ A) ∪ \overline{s} | \underline{r} ∩ B, & r ∈ A \\ \underline{r} ∩ A | (\underline{r} ∩ B) ∪ \overline{s}, & r ∈ B \end{matrix} \\ M|N = & \{ \begin{matrix}(\overline{s} ∩ A) − 1 | \underline{n − 1} \ (\overline{s} ∩ A) − 1, & r ∈ B \\ \underline{n − 1} \ (\overline{s} ∩ B) − #L | (\overline{s} ∩ B) − #L, & r ∈ A, & n ∈ A \\ I_{\underline{n}\L}(A) | \underline{n − 1} \ I_{\underline{n}\L}(A), & r ∈ A, & n ∈ B \end{matrix} \\ C|D = & \{ \begin{matrix}I_{\underline{n}\B}(\underline{r} ∩ A) | \underline{n − 1} \ I_{\underline{n}\B}(\underline{r} ∩ A), & r ∈ B, & n ∈ B \\ I_{\underline{n}\A}(\overline{s} ∩ B) | \underline{n − 1} \ I_{\underline{n}\A}(\overline{s} ∩ B), & r ∈ A, & n ∈ B \\ \underline{n − 1} \ I_{\underline{n}\B}(\overline{s} ∩ A) | I_{\underline{n}\B}(\overline{s} ∩ A), & r ∈ B, & n ∈ A \\ \underline{n − 1} \ I_{\underline{n}\A}(\underline{r} ∩ B) | I_{\underline{n}\A}(\underline{r} ∩ B), & r ∈ A, & n ∈ A. \end{matrix} \end{matrix}

Then define

d_{A|B} = ϱ_{C|D}d_{M|N}d_{K|L}.  (4.3)

Remark 1. This definition makes sense since K|L ∈ Q_{p_{1},q_{1}}(n), M|N ∈ Q_{p_{3},q_{3}}(n− 1), C|D ∈ Q_{p_{1},q_{1}}(n−1) with either r, n ∈ B or r, n ∈ A and C|D ∈ Q_{p_{3},q_{3}}(n−1) with either r ∈ B, n ∈ A or r ∈ A, n ∈ B. Of course, Q_{∗∗}(n−1) is considered with respect to the decomposition n − 2 = m_{1} + m_{2} + m_{3} fixed after the action of d_{K|L}(\underline{r} × \underline{s}).

If k = 3, consider the pair (r, s) = (n_{1} + 1, n − n_{1}), then (r_{1}, s_{1}) = (n_{2} + 1, n − n_{1} − n_{2} − 1) for A_{1}|B_{1} = I_{\underline{n}\\underline{r}}(\overline{s} ∩ A)|I_{\underline{n}\\underline{r}}(\overline{s} ∩ B) ∈ P_{p_{1},q_{1}}(n − r), and so on. Now dualize and use the same formulas above to define the degeneracy operator ϱ_{A|B}.

Definition 15. Let Y be a topological space. The \underline{singular multipermutahedral set} \underline{of Y} consists of the singular set Sing_{∗}^{M}Y together with the singular face and degeneracy operators

d_{A|B} : Sing_{n}^{M}Y → Sing_{n−1}^{M}Y and ϱ_{A|B} : Sing_{n−1}^{M}Y → Sing_{n}^{M}Y

defined respectively for each n ⩾ 2 and A|B ∈ P_{∗∗} (n).

Remark 2. The operator d_{A|B} defined in (4.3) applied to d_{U|V} for some U|V ∈ P_{r,s}(n + 1) yields the higher order structural relation

d_{A|B}d_{U|V} = ϱ_{C|D}d_{M|N}d_{K|L}d_{U|V}  (4.4)

discussed in our first universal example.

Now Sing_{∗}^{M}Y determines the singular (co)homology of a space Y in the following way: Let R be a commutative ring with identity. For n ⩾ 1, let C_{n−1}(Sing^{M}Y) denote the R-module generated by Sing_{n}^{M}Y and form the “chain complex”

(C_{∗}(Sing^{M}Y), d) = ⨁_{\begin{matrix}n_{(k)}=n−1 \\ n⩾1 \end{matrix}}(C_{n−1}(Sing^{n_{1}···n_{k}}Y), d_{n_{1}···n_{k}}),

where

d_{n_{1}···n_{k}} = \begin{matrix}∑ \\ A|B∈⋃_{i=1}^{k} Q_{p_{i},q_{i}} (n) \end{matrix} −(−1)^{n_{(i−1)}+n′_{i}} shuff (C_{i} ∩ A; C_{i} ∩ B) d_{A|B}.

Refer to the example in Figure 7 and note that for f ∈ C_{4}(Sing^{M}Y) with d_{13|2}d_{12|34} (f) ≠ 0, the component d_{13|2}d_{12|34} (f) of d^{2} (f) ∈ C_{2}(Sing^{M}Y) is not cancelled and d^{2} ≠ 0. Hence d is not a differential. To remedy this, form the quotient

C_{∗}^{♢}(Y) = C_{∗} (Sing^{M}Y ) /DGN,

where DGN is the submodule generated by the degeneracies, and obtain the singular permutahedral chain complex (C_{∗}^{♢}(Y), d). Because the signs in d are determined by the index i, which is missing in our first universal example, we are unable to use our first example to define a chain complex with signs. However, we could use it to define a unoriented theory with ℤ_{2}-coefficients.

The singular homology of Y is recovered from the composition

C_{∗}(SingY) → C_{∗}(Sing^{I}Y) → C_{∗}(Sing^{M}Y) → C_{∗}^{♢}(Y)

arising from the canonical cellular projections

P_{n+1} → I^{n} → Δ^{n}.

Since this composition is a chain map, there is a natural isomorphism

H_{∗}(Y) ≈ H_{∗}^{♢}(Y) = H_{∗}(C_{∗}^{♢}(Y), d).

The fact that our diagonal on P and the A-W diagonal on simplices commute with projections allows us to recover the singular cohomology ring of Y as well. Finally, we remark that a cellular projection f between polytopes induces a chain map between corresponding singular chain complexes whenever chains on the target are normalized. Here C_{∗}(SingY) and C_{∗}(Sing^{I}Y) are non-normalized and the induced map f^{∗} is not a chain map; but fortunately d^{2} = 0 does not depend df^{∗} = f^{∗}d.

4.2. Abstract Permutahedral Sets

We begin by constructing a generating category P for permutahedral sets similar to that of finite ordered sets and monotonic maps for simplicial sets. The objects of P are the sets n! = S_{n} of permutations of \underline{n}, n ⩾ 1. But before we can define the morphisms we need some preliminaries. First note that when P_{n} is identified with its vertices n!, the maps ρ_{n} and γ_{n} defined above become

ρ_{n} : n! → 2!^{n−1} and γ_{n} : 2!^{n−1} → n!.

Given a non-empty increasingly ordered set M = {m_{1} < ⋯ < m_{k}} ⊂ ℕ, let M! denote the set of all permutations of M and let J_{M} : M! → k! be the map defined for a = (m_{σ(1)}, ..., m_{σ(k)}) ∈ M! by J_{M}(a) = σ. For n, m ∈ ℕ and partitions A_{1}| ⋯ |A_{k} ∈ P_{n_{1}···n_{k}}(n) and B_{1}| ⋯ |B_{ℓ} ∈ P_{m_{1}···m_{ℓ}}(m) with n − k = m − ℓ = κ, define the morphism

f_{A_{1}|···|A_{k}}^{B_{1}|···|B_{ℓ}} : m! → n!

by the composition

m! →^{sh_{B}} ∏_{j=1}^{ℓ} B_{j} →^{σ_{max}} ∏_{r=1}^{ℓ} B_{j_{r}} →^{J_{B}} ∏_{j=r}^{ℓ} m_{j_{r}}! →^{ρ_{∗}} 2!^{κ} →^{γ_{∗}} ∏_{s=1}^{k} n_{i_{s}}! →^{J_{A}^{−1}} ∏_{s=1}^{k} A_{i_{s}} →^{σ_{max}^{−1}} ∏_{i=1}^{k} A_{i} →^{ι_{A}} n!

where sh_{B} is a surjection defined for b = {b_{1}, ..., b_{m}} ∈ m! by

sh_{B}(b) = (b_{1,1}, .., b_{m_{1},1}; ...; b_{1,ℓ}, .., b_{m_{ℓ},ℓ}),

in which the right-hand side is the unshuffle of b with b_{r,t} ∈ B_{t}, 1 ⩽ r ⩽ m_{t}, 1 ⩽ t ⩽ ℓ; σ_{max} ∈ S_{ℓ} is a permutation defined by j_{r} = σ_{max}(r), max B_{j_{r}} = max(B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{j_{r}}); J_{B} = ∏_{r=1}^{ℓ} J_{B_{jr}}; ρ_{∗} = ∏_{r=1}^{ℓ} ρ_{j_{r}} and γ_{∗} = ∏_{s=1}^{k} γ_{i_{s}}; finally, ι_{A} is the inclusion. It is easy to see that

f_{A_{1}|···|A_{k}}^{B_{1}|···|B_{ℓ}} = f\underline{κ+1} ; A_{1}|···|A_{k} ∘ f B_{1}|···|B_{ℓ} ; \underline{κ+1} and f\underline{n} ; \underline{n} = γ_{n} ∘ ρ_{n}.

In particular, the maps f\underline{n−1} ; A|B : (n − 1)! → n! and f A|B ; \underline{n−1} : n! → (n − 1)! are generator morphisms denoted by δ_{A|B} and β_{A|B}, respectively (see Theorem 2 below, the statement of which requires some new set operations).

Definition 16. Given non-empty disjoint subsets A, B, U ⊂ \underline{n + 1} with A ∪ B ⊆ U, define the \underline{lower and upper disjoint unions} (with respect to U) by

A\underline{⊔}B = \{ \begin{matrix}I_{U⧹A} (B) + #A − 1, & if min B > min (U⧹A) \\ I_{U⧹A} (B) + #A − 1 ∪ \underline{#A}, & if min B = min (U⧹A) \end{matrix}

and

A\overline{⊔}B = \{ \begin{matrix}I_{U⧹B} (A) , & if max A < max (U⧹B) \\ I_{U⧹B} (A) ∪ \overline{#B} − 1, & if max A = max (U⧹B) . \end{matrix}

If either A or B is empty, define A\underline{⊔}B = A\overline{⊔}B = A ∪ B. Furthermore, given nonempty disjoint subsets A, B_{1}, …, B_{k} ⊂ \underline{n + 1} with k ⩾ 1, set U = A ∪ B_{1} ∪ ⋯ ∪ B_{k} and define

A□(B_{1}| ⋯ |B_{k}) = (B_{1}| ⋯ |B_{k})□A = \{ \begin{matrix}A\underline{⊔}B_{1}| ⋯ |A\underline{⊔}B_{k}, & if max A < max U \\ B_{1}\overline{⊔}A| ⋯ |B_{k}\overline{⊔}A, & if max A = max U. \end{matrix}

Note that if A|B is a partition of \underline{n + 1}, then

A\underline{⊔}B = A\overline{⊔}B = \underline{n}.

Given a partition A_{1}| ⋯ |A_{k+1} of \underline{n}, define A_{1}^{1}| ⋯ |A_{k+1}^{1} = A_{1}^{1}| ⋯ |A_{1}^{k+1} = A_{1}| ⋯ |A_{k+1}; inductively, given A_{1}^{i}| ⋯ |A_{k−i+2}^{i} the partition of \underline{n − i + 1}, 1 ⩽ i < k, let

A_{1}^{i+1}| ⋯ |A_{k−i+1}^{i+1} = A_{1}^{i}□(A_{2}^{i}| ⋯ |A_{k−i+2}^{i})

be the partition of \underline{n − i}; and given A_{i}^{1}| ⋯ |A_{i}^{k−i+2} the partition of \underline{n − i + 1}, 1 ⩽ i < k, let

A_{i+1}^{1}| ⋯ |A_{i+1}^{k−i+1} = (A_{i}^{1}| ⋯ |A_{i}^{k−i+1})□A_{i}^{k−i+2}

be the partition of \underline{n − i}.

Theorem 2. For A_{1}| ⋯ |A_{k+1} ∈ P_{n_{1}···n_{k+1}}(n), 2 ⩽ k ⩽ n, the map f\underline{n−k} ; A_{1}|···|A_{k+1} :

(n − k)! → n! can be expressed as a composition of δ’s two ways:

f\underline{n−k} ; A_{1}|···|A_{k+1} = δ_{A_{1}^{1} | A_{2}^{1}∪···∪A_{k+1}^{1}} ⋯ δ_{A_{1}^{k} | A_{2}^{k}} = δ_{A_{1}^{1}∪···∪A_{1}^{k} | A_{1}^{k+1}} ⋯ δ_{A_{k}^{1} | A_{k}^{2}}.

Proof. The proof is straightforward and omitted.

There is also the dual set of relations among the β’s.

Example 5. Theorem 2 defines structure relations among the δ’s, the first of which is

δ_{A|B∪C} δ_{A□(B|C)} = δ_{A∪B|C} δ_{(A|B)□C}  (4.5)

when k = 2. In particular, let A|B|C = 12|345|678. Since A\underline{⊔}B = \{1234\}, A\underline{⊔}C = \{567\} , A\overline{⊔}C = \{12\} and B\overline{⊔}C = \{34567\} , we obtain the following quadratic relation on 12|345|678:

δ_{12|345678}δ_{1234|567} = δ_{12345|678}δ_{12|34567};

Homology, Homotopy and Applications, vol. 6(1), 2004 390 similarly, on 345|12|678 we have

δ_{345|12678}δ_{1234|567} = δ_{12345|678}δ_{34567|12}.

Theorem 3. Let A|B ∈ P_{p,q} (n + 1) and C|D ∈ P_{∗∗} (n) . Then δ_{A|B}δ_{C|D} coincides with a map f\underline{n−1} ; X|Y |Z : (n − 1)! → (n + 1)! if and only if

C|D ∈ \{ \begin{matrix}Q_{q,1}(n) ∪ Q_{1,p} (n) , & if n + 1 ∈ A \\ Q_{p,1}(n) ∪ Q_{1,q}(n), & if n + 1 ∈ B. \end{matrix}  (4.6)

Proof. If δ_{A|B}δ_{C|D} coincides with f\underline{n−1} ; X|Y |Z, then according to relation (4.7) we have either

A|B = X|Y ∪Z and C|D = X□(Y |Z)

or

A|B = X ∪ Y |Z and C|D = (X|Y)□Z.

Hence there are two cases. \underline{Case 1:} A|B = X|Y ∪ Z. \underline{Subcase 1a:} Assume n + 1 ∈ A. If max Y = max(Y ∪ Z), then \overline{p} ⊆ Y \overline{⊔}X; otherwise max (Y ∪ Z) = max Z and \overline{p} ⊆ Z\overline{⊔}X. In either case, C|D = Y \overline{⊔}X|Z\overline{⊔}X ∈ Q_{1,p} (n). \underline{Subcase 1b:} Assume n + 1 ∈ B. If min Y = min(Y ∪ Z), then \underline{p} ⊆ X\underline{⊔}Y; otherwise min(Y ∪ Z) = min Z and \underline{p} ⊆ X\underline{⊔}Z. In either case, C|D =X\underline{⊔}Y |X\underline{⊔}Z ∈ Q_{p,1} (n) . \underline{Case 2:} A|B = X ∪ Y |Z. \underline{Subcase 2a:} Assume n + 1 ∈ A. If min X = min(X ∪ Y), then \underline{q} ⊆ Z\underline{⊔}X; otherwise min(X ∪ Y) = min Y and \underline{q} ⊆ Z\underline{⊔}Y. In either case, C|D =Z\underline{⊔}X|Z\underline{⊔}Y ∈ Q_{q,1} (n) . \underline{Subcase 2b:} Assume n + 1 ∈ B. If max X = max(X ∪ Y), then \overline{q} ⊆ X\overline{⊔}Z; otherwise max (X ∪ Y) = max Y and \overline{q} ⊆ Y \overline{⊔}Z. In either case, C|D = X\overline{⊔}Z|Y \overline{⊔}Z ∈ Q_{1,q} (n). Conversely, given A|B ∈ P_{p,q}(n + 1) and C|D satisfying conditions (4.6) above, let

[A|B; C|D] = \{ \begin{matrix}A | I_{B}^{−1} (\overline{q} ∩ C − p + 1) | I_{B}^{−1} (\overline{q} ∩ D − p + 1) , & C|D ∈ Q_{p,1} (n) \\ I_{A}^{−1} (\underline{p} ∩ C) | I_{A}^{−1} (\underline{p} ∩ D) | B, & C|D ∈ Q_{1,q} (n) \end{matrix}

and

[A|B; C|D] = \{ \begin{matrix}A | I_{B}^{−1} (\underline{q} ∩ C) | I_{B}^{−1} (\underline{q} ∩ D) , & C|D ∈ Q_{1,p} (n) \\ I_{A}^{−1} (\overline{p} ∩ C − q + 1) | I_{A}^{−1} (\overline{p} ∩ D − q + 1) | B, & C|D ∈ Q_{q,1} (n) . \end{matrix}

A straightforward calculation shows that

[X|Y ∪ Z; X□(Y |Z)] = X|Y |Z = [X ∪ Y |Z; (X|Y)□Z].

Consequently, if X|Y |Z = [A|B; C|D], either A|B = X| Y ∪ Z and C|D = X□(Y |Z) when C|D ∈ Q_{p,1}(n) ∪ Q_{1,p}(n) or

A|B = X ∪ Y |Z and C|D = (X|Y)□Z

when C|D ∈ Q_{q,1}(n) ∪ Q_{1,q}(n).

On the other hand, if C|D ∉ Q_{p,1}(n) ∪ Q_{1,p}(n) ∪ Q_{q,1}(n) ∪ Q_{1,q}(n), higher order structure relations involving both coface and codegeneracy operators appear.

Definition 17. Let C be the category of sets. A \underline{permutahedral set} is a contravariant functor

Z : P → C.

Thus a permutahedral set Z is a graded set Z = {Z_{n}}_{n⩾1} endowed with face and degeneracy operators

d_{A|B} = Z(δ_{A|B}) : Z_{n} → Z_{n−1} and ϱ_{M|N} = Z(β_{M|N}) : Z_{n} → Z_{n+1}

satisfying an appropriate set of relations, which includes quadratic relations such as

d_{A□(B|C)}d_{A|B∪C} = d_{(A|B)□C}d_{A∪B|C}  (4.7)

induced by (4.5) and higher order relations such as

d_{A|B}d_{U|V} = ϱ_{C|D}d_{M|N}d_{K|L}d_{U|V}

discussed in (4.4).

Let us define the abstract analog of a singular multipermutahedral set, which leads to a singular chain complex with arbitrary coefficients.

Definition 18. For n ⩾ 1, let X_{n} = ⋃_{n_{(k)}=n−1, n_{k}⩾0} X^{n_{1}···n_{k}} and X_{n−1} = ⋃_{m_{(ℓ)}=n−2, m_{ℓ}⩾0} X^{m_{1}···m_{ℓ}} be filtered sets; let A|B ∈ Q_{p_{i},q_{i}}(n) for some i. A map g : X_{n} → X_{n−1} acts as an \underline{A|B-formal derivation} if

g|_{X^{n_{1}···n_{k}}} : X^{n_{1}···n_{k}} → X^{n_{1}···n′_{i},n′′_{i}···n_{k}},

where (n′_{i}, n′′_{i}) is given by (4.2).

Let C_{M} denote the category whose objects are positively graded sets X_{∗} filtered by subsets X_{n} = ⋃_{n_{(k)}=n−1, n_{k}⩾0} X^{n_{1}···n_{k}} and whose morphisms are filtration preserving set maps.

Definition 19. A \underline{multipermutahedral set} is a contravariant functor Z : P → C_{M} such that

Z(δ_{A|B}) : Z(n!) → Z((n − 1)!)

acts as an A|B-formal derivation for each A|B ∈ Q_{p_{i},q_{i}}, all i ⩾ 1.

Thus a multipermutahedral set Z is a graded set {Z_{n}}_{n⩾1} with

Z_{n} = ⋃_{\begin{matrix}n_{(k)}=n−1 \\ n_{k}⩾0 \end{matrix}} Z^{n_{1}···n_{k}},

together with face and degeneracy operators

d_{A|B} = Z(δ_{A|B}) : Z_{n} → Z_{n−1} and ϱ_{M|N} = Z(β_{M|N}) : Z_{n} → Z_{n+1}

satisfying the relations of a permutahedral set and the additional requirement that d_{A|B} respect underlying multigrading. This later condition allows us to form the chain complex of Z with signs mimicking the cellular chain complex of permutahedra (see below). Note that the chain complex of a permutahedral set is only defined with ℤ_{2}-coefficients in general.

4.3. The Cartesian product of permutahedral sets The objects and morphisms in the category P × P are the sets and maps

n!! = ⋃_{r+s=n} r! × s! and ⋃_{f,g∈P} f × g : m!! → n!!

all m, n ⩾ 1. There is a functor Δ : P → P × P defined as follows. If A|B ∈ Q_{r,1}(n)∪ Q_{1,s}(n), define Δ_{r,s}(A|B) = A_{1}|B_{1} × A_{2}|B_{2} ∈ r! × s! and define δ_{A|B} : (n − 1)! → n! by

Δ(δ_{A|B}) = δ_{A_{1}|B_{1}} × δ_{A_{2}|B_{2}},

where δ_{A_{i}|B_{i}} = 1 for either i = 1 or i = 2. Define Δ(β_{A|B}) similarly. On the other hand, if A|B ∉ Q_{r,1}(n) ∪ Q_{1,s}(n), define

Δ(δ_{A|B}) = Δ(δ_{K|L})Δ(δ_{M|N})Δ(β_{C|D}),

where K|L, M|N, C|D are given by the formulas in (4.3). Dually, define Δ(β_{M|N}). It is easy to check that Δ is well defined.

Given multipermutahedral sets Z′, Z′′ : P → C_{M}, first define a functor

Z′ ˜×Z′′ : P × P → C_{M}

on an object n!! by

(Z′ ˜×Z′′)(n!!) = ⋃_{r+s=n} Z′(r!) × Z′′(s!)⧸∼,

where (a, b) ∼ (c, e) if and only if a = ϱ′_{\underline{r}|r+1}(c) and e = ϱ′′_{1|\underline{s+1}\\underline{1}}(b). On a map h = ⋃(f × g) : m!! → n!!,

(Z′ ˜×Z′′)(h) : (Z′ ˜×Z′′)(n!!) → (Z′ ˜×Z′′)(m!!)

is the map induced by ⋃(Z′(f) × Z′′(g)). Now define the product Z′ × Z′′ to be the composition of functors

Z′ × Z′′ = Z′ ˜×Z′′ ∘ Δ : P → C_{M}.

The face operator d_{A|B} on Z′ × Z′′ is given by

d_{A|B}(a × b) = \{ \begin{matrix}d′_{\underline{r}∩A|\underline{r}∩B} (a) × b, & if A|B ∈ Q_{1,s} (n) , \\ a × d′′_{(\overline{s}∩A)−r+1 | (\overline{s}∩B)−r+1}(b), & if A|B ∈ Q_{r,1} (n) , \\ ϱ_{C|D}d_{M|N}d_{K|L} (a × b) , & otherwise, \end{matrix}  (4.8)

with M|N, K|L, C|D given by the formulas in (4.3).

Example 6. The canonical map ι : Sing^{P} X × Sing^{P} Y → Sing^{P} (X × Y) defined for (f, g) ∈ Sing_{r}^{P} X × Sing_{s}^{P} Y by

ι(f, g) = (f × g) ∘ Δ_{r,s}

is a map of permutahedral sets. Consequently, if X is a topological monoid, the singular permutahedral complex Sing^{P} X inherits a canonical monoidal structure.

4.4. The diagonal on a permutahedral set

Let Z = (Z_{n}, d_{A|B}, ϱ_{M|N}) be a multipermutahedral set. The chain complex of Z is

C_{∗}^{♢}(Z) = C_{∗}(Z)/DGN,

where DGN is the submodule generated by the degeneracies;

(C_{∗}(Z), d) = ⨁_{\begin{matrix}n_{(k)}+1=n \\ n⩾1 \end{matrix}}(C_{n−1}(Z^{n_{1}···n_{k}}), d_{n_{1}···n_{k}})

and

d_{n_{1}···n_{k}} = \begin{matrix}∑ \\ A|B∈⋃_{i=1}^{k} Q_{p_{i},q_{i}} (n) \end{matrix} −(−1)^{n_{(i−1)}+n′_{i}} shuff (C_{i} ∩ A; C_{i} ∩ B) d_{A|B}.

The explicit diagonal

Δ : C_{∗}^{♢}(Z) → C_{∗}^{♢}(Z) ⊗ C_{∗}^{♢}(Z)

on a ⊂ Z_{n} is given by

Δ(a) = ∑_{\begin{matrix}F ∈C^{q×n−q+2} \\ 0⩽q⩽n \end{matrix}} csgn(F) d_{c(F)}(a) ⊗ d_{r(F)}(a),  (4.9)

where d_{A_{1}|...|A_{k+1}} = Z(f\underline{n−k} ; A_{1}|...|A_{k+1}).

4.5. The double cobar-construction Ω^{2}C_{∗}(X)

Given a simplicial, cubical or a permutahedral set W with base point ∗, let C_{∗}(W) denote the quotient C_{∗}(W)/C_{>0}(∗). Say that W is k-reduced if W_{i} contains exactly one element for each i ⩽ k and let ΩC denote the cobar construction on a 1-reduced DG coalgebra C. In [8] and [9], Kadeishvili and Saneblidze construct functors from the category of 1-reduced simplicial sets to the category of cubical sets and from the category of 1-reduced cubical sets to the category of multipermutahedral sets (denoted by Ω in either case) for which the following statements hold (c.f. [3], [2]):

Theorem 4. [8] Given a 1-reduced simplicial set X, there is a canonical identification isomorphism

ΩC_{∗}(X) ≈ C_{∗}^{□} (ΩX).

Theorem 5. [9] Given a 1-reduced cubical set Q, there is a canonical identification 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 strictly coassociative coproduct, setting Q = ΩX in Theorem 5 immediately gives:

Theorem 6. For a 2-reduced simplicial set X there is a canonical identification isomorphism

Ω^{2}C_{∗}(X) ≈ C_{∗}^{♢}(Ω^{2}X).

Now if X = Sing^{1}Y, then ΩC_{∗}(X) is Adams’ cobar construction for the space Y [1]; consequently, there is a canonical (geometric) coproduct on Ω^{2}C_{∗}(Sing^{1}Y). We shall extend this canonical coproduct to an “A_{∞}-Hopf algebra” structure in the sequel [16].

5. The Multiplihedra and Associahedra

The multiplihedron J_{n} and the associahedron K_{n+1} are cellular projections of P_{n} defined in terms of planar trees. Consequently, we shall need to index the faces of P_{n} four ways: (1) by partitions of \underline{n} (see Section 2), (2) by (planar rooted) p-leveled trees with n+1 leaves (PLT’s), (3) by parenthesized strings of n+1 indeterminants with p − 1 levels of subscripted parentheses and (4) by (p − 1)-fold compositions of face operators acting on n + 1 indeterminants. The second and third serve as transitional intermediaries between the first and fourth.

Define a correspondence between PLT’s and partitions of \underline{n} as follows: Let T_{n+1}^{p} be a PLT with n + 1 leaves, p-levels and root in level p. Number the leaves from left to right and assign the label i to the node at which the branch of leaf i meets the branch of leaf i + 1, 1 ⩽ i ⩽ n (a node may have multiple labels). Let U_{j} = {labels assigned to j-level nodes} and identify T_{n+1}^{p} with the partition U_{1}| ⋯ |U_{p} of \underline{n} (see Figure 9). Thus binary n-leveled trees parametrize the vertices of P_{n}. Loday and Ronco constructed a map from S_{n} to binary n-leveled trees [12]; its extension to faces of P_{n} was given by Tonks [19]. Note that the map from PLT’s to partitions defined above gives an inverse.

[figure: •; •; •; •; 34; 1; 2; 56; ⟷  256|1|34; ⟷  d_{(0,1)}d_{(1,1)(4,2)}; ⟷  ((• (• •)_{1})_{2} • (• • •)_{1})]

Figure 9: Various representations of the face 256|1|34.

To define the correspondence between PLT’s and subscripted parenthesizations of n + 1 indeterminants, begin by identifying the top cell of P_{n} with the (n + 1)-leaf corolla and the (unsubscripted) parenthesized string (x_{1}x_{2} ⋯ x_{n+1}) . Let T_{n+1}^{p} be a PLT with p > 1. If the branches meeting at a level 1 node contain leaves i, …, i+k, enclose the corresponding indeterminants in a pair of parentheses with subscript 1; if the branches meeting at a level 2 node contain leaves i_{1}, …, i_{k}, enclose the corresponding indeterminants in a pair of parentheses with subscript 2; and so on for p − 1 steps (see Example 5).

Compositions of face operators encode this parenthesization procedure. For s ⩾ 1, choose s pairs of indices (i_{1}, ℓ_{1}) ⋯ (i_{s}, ℓ_{s}) such that 0 ⩽ i_{r} < i_{r+1} ⩽ n − 1 and i_{r} + ℓ_{r} + 1 ⩽ i_{r+1}. The face operator

d_{(i_{1},ℓ_{1})···(i_{s},ℓ_{s})} : P_{n} → ∂P_{n}

acts on (x_{1}x_{2} ⋯ x_{n+1}) by simultaneously inserting s disjoint (non-nested) pairs of inner parentheses with subscript 1, the first enclosing x_{i_{1}+1} ⋯ x_{i_{1}+ℓ_{1}+1}, the second enclosing x_{i_{2}+1} ⋯ x_{i_{2}+ℓ_{2}+1}, and so on. Thus,

d_{(i_{1},ℓ_{1})···(i_{s},ℓ_{s})} (x_{1}x_{2} ⋯ x_{n+1}) =

(x_{1} ⋯ (x_{i_{1}+1} ⋯ x_{i_{1}+ℓ_{1}+1})_{1} ⋯ (x_{i_{s}+1} ⋯ x_{i_{s}+ℓ_{s}+1})_{1} ⋯ x_{n+1}) .

A composition of face operators

d_{(i_{1}^{k},ℓ_{1}^{k})···(i_{s_{k}}^{k} ,ℓ_{s_{k}}^{k})} ⋯ d_{(i_{1}^{1},ℓ_{1}^{1})···(i_{s_{1}}^{1} ,ℓ_{s_{1}}^{1})} : P_{n} → ∂^{k}P_{n}  (5.1)

continues this process inductively: If the j^{th} operator inserted parentheses with subscript j, treat each such pair and its contents as a single indeterminant and apply the (j + 1)^{st} as above, inserting parentheses subscripted by j + 1.

Refer to Figure 9 above. The composition d_{(0,1)}d_{(1,1)(4,2)} acts on (• • • • • • •) in the following way: First, d_{(1,1)(4,2)} simultaneously inserts two inner pairs of parentheses with subscript 1:

(• (• •)_{1} • (• • •)_{1}) .

Next, d_{(0,1)} inserts the single pair with subscript 2:

((• (• •)_{1})_{2} • (• • •)_{1}) .

We summarize the discussion above as a proposition.

Proposition 5. The following correspondences (defined above) preserve combinatorial structure:

\{Faces of P_{n}\} ↔ \{Partitions of \underline{n}\}
↔ {Leveled trees with n + 1 leaves}

↔ \{ \begin{matrix}Strings of n + 1 indeterminants \\ with subscripted parentheses \end{matrix} \}

↔ \{ \begin{matrix}Compositions of face operators \\ acting on n + 1 indeterminants. \end{matrix} \}

Assign the identity face operator Id to the top dimensional face of P_{n+1} and use the correspondences above to assign compositions of faces operators to lower dimensional faces (see Figure 10). For faces in codimension 1 we have:

Face of P_{n+1}  Face operator
P_{n} × 0  d_{(0,n)}
P_{n} × 1  d_{(n,1)}
d_{(i_{1},ℓ_{1})···(i_{k},ℓ_{k})} × [0, 1 − 2^{ℓ_{1}+···+ℓ_{k}−n}]  d_{(i_{1},ℓ_{1})···(i_{k},ℓ_{k})}

d_{(i_{1},ℓ_{1})···(i_{k},ℓ_{k})} × [1 − 2^{ℓ_{1}+···+ℓ_{k}−n}, 1] \{ \begin{matrix}d_{(i_{1},ℓ_{1})···(i_{k},ℓ_{k})(n,1)}, & i_{k} + ℓ_{k} < n \\ d_{(i_{1},ℓ_{1})···(i_{k},ℓ_{k}+1)}, & i_{k} + ℓ_{k} = n. \end{matrix}

• • •  • • • Id d_{(0,1)}d_{(0,1)} d_{(1,1)}d_{(0,1)} d_{(0,1)}d_{(2,1)}  d_{(0,1)}d_{(1,1)} d_{(1,1)}d_{(1,1)} d_{(1,1)}d_{(2,1)} d_{(0,1)}  d_{(2,1)} d_{(0,1)(2,1)}  d_{(1,2)} d_{(1,1)} d^{(0,2)}

Figure 10: P_{3} with face-operator labeling.

Since compositions of face operators are determined by the correspondence between faces and partitions, we only label the codimension 1 faces of the related polytopes below.

The associahedra {K_{n}} serve as parameter spaces for higher homotopy associativity. In his seminal papers of 1963 [18], J. Stasheff constructed K_{n} in the following way: Let K_{2} = ∗; if K_{n−1} has been constructed, define K_{n} to be the cone on the set

⋃_{\begin{matrix}r+s=n+1 \\ 1⩽k⩽n−s+1 \end{matrix}} (K_{r} × K_{s})_{k} .

Thus, K_{n} is an (n − 2)-dimensional convex polytope.

Stasheff’s motivating example of higher homotopy associativity in [18] is the singular chain complex on the (Poincarè) loop space of a connected CW -complex. Here associativity holds up to homotopy, the homotopies between the various associations are homotopic, the homotopies between these homotopies are homotopic, and so on. An abstract A_{∞}-algebra is a DGA in which associativity behaves as in Stasheff’s motivating example. If φ^{2} : A ⊗ A → A is the multiplication on an A_{∞}-algebra A, the homotopies φ^{n} : A^{⊗n} → A are multilinear operations such that φ^{3} is a chain homotopy between the associations (ab) c and a (bc) thought of as quadratic compositions φ^{2} (φ^{2} ⊗ 1) and φ^{2} (1 ⊗ φ^{2}) in three variables, φ^{4} is a chain homotopy bounding the cycle of five quadratic compositions in four variables involving φ^{2} and φ^{3}, and so on. Let C_{∗} (K_{r}) denote the cellular chains on K_{r}. The natural correspondence between faces of K_{r} and the various compositions of the φ^{n}’s in r variables (modulo an appropriate equivalence) induces a chain map C_{∗} (K_{r}) → Hom (A^{⊗r}, A) that determines the relations among the compositions of φ^{n}’s. This chain map together with our diagonal on K_{n} leads to the tensor product of A_{∞}-algebras (see Section 5).

Now if we disregard levels, a PLT is simply a planar rooted tree (PRT). Quite remarkably, A. Tonks [19] showed that K_{n} is the identification space P_{n−1}/ ∼ in which all faces indexed by isomorphic PRT’s are identified. Since the quotient map θ : P_{n−1} → K_{n} is cellular, the faces of K_{n} are indexed by PRT’s with n leaves. The correspondence between PRT’s with n leaves and parenthesizations of n indeterminants is simply this: Given a node N, parenthesize the indeterminants that correspond to leaves on all branches that meet at node N.

Example 7. With one exception, all classes of faces of P_{3} consist of a single element. Elements of the exceptional class

[1|3|2, 13|2, 3|1|2]

represent the parenthesization ((••) (••)) . Whereas 1|3|2 and 3|1|2 insert inner parentheses in the opposite order, the element 13|2 inserts inner parentheses simultaneously and represents a homotopy between 1|3|2 and 3|1|2. Tonks’ projection θ sends the exceptional class to the vertex of K_{4} represented by the parenthesization ((••) (••)) . The classes of faces of P_{4} with more than one element and their projections to K_{5} are:

[12|4|3, 124|3, 4|12|3] ⟶^{θ} ((• • •) (••))
[1|3|24, 13|24, 3|1|24] ⟶ ((••) (••) •)
[1|4|23, 14|23, 4|1|23] ⟶ ((••) • (••))
[2|4|13, 24|13, 4|2|13] ⟶ (• (••) (••))
[1|34|2, 134|2, 34|1|2] ⟶ ((••) (• • •))
[1|3|2|4, 13|2|4, 3|1|2|4] ⟶ (((••) (••)) •)
[2|4|3|1, 24|3|1, 4|2|3|1] ⟶ (• ((••) (••)))
[1|2|4|3, 1|24|3, 1|4|2|3, 14|2|3, 4|1|2|3] ⟶ (((••) •) (••))
[1|3|4|2, 13|4|2, 3|1|4|2, 3|14|2, 3|4|1|2] ⟶ ((••) ((••) •))
[1|4|3|2, 14|3|2, 4|1|3|2, 4|13|2, 4|3|1|2] ⟶ ((••) (• (••)))
[2|1|4|3, 2|14|3, 2|4|1|3, 24|1|3, 4|2|1|3] ⟶ ((• (••)) (••)) .

Faces and edges represented by elements of the first five classes project to edges; edges and vertices represented by elements of the next six classes project to vertices.

The multiplihedra {J_{n+1}}, which serve as parameter spaces for homotopy multiplicative morphisms of A_{∞}-algebras, lie between the associahedra and permutahedra (see [18], [6]). If f^{1} : A → B is such a morphism, there is a chain homotopy f^{2} between the quadratic compositions f^{1}φ_{A}^{2} and φ_{B}^{2} (f^{1} ⊗ f^{1}) in two variables, there is a chain homotopy f^{3} bounding the cycle of the six quadratic compositions in three variables involving f^{1}, f^{2}, φ_{A}^{2}, φ_{A}^{3}, φ_{B}^{2} and φ_{B}^{3}, and so on. The natural correspondence between faces of J_{r} and the various compositions of f^{i}, φ_{A}^{j} and φ_{B}^{k} in r variables (modulo an appropriate equivalence) induces a chain map C_{∗} (J_{r}) → Hom (A^{⊗r}, B).

The multiplihedron J_{n+1} can also be realized as a subdivision of the cube I^{n}. For n = 0, 1, 2, set J_{n+1} = P_{n+1}. If J_{n} has been constructed, J_{n+1} is the subdivision of J_{n} × I given below and its various (n − 1)-faces are labeled as indicated:

Face of J_{n+1}  Face operator
J_{n} × 0  d_{(0,n)}
J_{n} × 1  d_{(n,1)}
d_{(i,ℓ)} × I  d_{(i,ℓ)}, 1 ⩽ i < n − ℓ
d_{(i,ℓ)} × [0, 1 − 2^{−i}]  d_{(i,ℓ)}, 1 ⩽ i = n − ℓ
d_{(i,ℓ)} × [1 − 2^{−i}, 1]  d_{(i,ℓ+1)}, 1 ⩽ i = n − ℓ
d_{(0,ℓ_{1})···(i_{k},ℓ_{k})} × [0, 1 − 2^{k−n}]  d_{(0,ℓ_{1})···(i_{k},ℓ_{k})}
d_{(0,ℓ_{1})···(i_{k},ℓ_{k})} × [1 − 2^{k−n}, 1] \{ \begin{matrix}d_{(0,ℓ_{1})···(i_{k},ℓ_{k})(n,1)}, & i_{k} < n − ℓ_{k} \\ d_{(0,ℓ_{1})···(i_{k},ℓ_{k}+1)}, & i_{k} = n − ℓ_{k}. \end{matrix}

Thus faces of J_{n+1} are indexed by compositions of face operators of the form

d_{(i_{m},ℓ_{m})} ⋯ d_{(i_{k_{1}} ,ℓ_{k_{1}} )···(i_{ks} ,ℓ_{ks})} ⋯ d_{(i_{1},ℓ_{1})}.  (5.2)

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 level j parentheses one pair at a time without regard to order as in K_{n+2}; next, insert all level p parentheses simultaneously as in P_{n+1}; finally, for j > p, insert level j parentheses one pair at a time without regard to order. Thus multiple lower indices 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′ be p-leveled trees with n + 2 nodes whose p-level meets U_{p} and U′_{p} contain 1. Then T ∼ T′ if T and T′ are isomorphic as PLT’s and U_{p} = U′_{p}. This equivalence relation induces a cellular projection π : P_{n+1} → J_{n+1} under which J_{n+1} can be realized as an identification space of P_{n+1}. Furthermore, the projection J_{n+1} → K_{n+2} given by identifying faces of J_{n+1} indexed by isomorphic PLT’s gives the factorization P_{n+1} ⟶^{π} J_{n+1} → K_{n+2} of Tonks’ projection.

It is interesting to note the role of the indices ℓ_{j} in compositions of face operators representing the faces of J_{n+1} as in (5.2). With one exception, each U_{j} in the corresponding partition U_{1}| ⋯ |U_{m+1} is a set of consecutive integers; this holds without exception for all U_{j} on K_{n+2}. The exceptional set U_{p} is a union of s sets of consecutive integers with maximal cardinality, as is typical of sets U_{j} on P_{n+1}. Thus J_{n+1} exhibits characteristics of both combinatorial structures.

•  •  • •  •  •  •  •  •  • •  • •  •  • •  •  •  •  • •  •  •  •  •  •  • •  •  • (1, 1, 1) (0, 0, 0)  d_{(3,1)} d_{(0,3)} d_{(0,2)(3,1)} d_{(0,2)}  d_{(0,1)(2,1)} d_{(0,1)(2,2)} d_{(2,2)} d_{(1,1)}  d_{(2,1)} d_{(1,3)}  d_{(0,1)(3,1)} d_{(1,2)}  d_{(0,1)}

Figure 11: J_{4} as a subdivision of J_{3} × I.

We realize the associahedron K_{n+2} in a similar way. For n = 0, 1, set K_{n+2} = P_{n+1}. If K_{n+1} has been constructed, let e_{i,ϵ} denote the face (x_{1}, …, x_{i−1}, ϵ, x_{i+1}, …, x_{n}) ⊂ I^{n}, where ϵ = 0, 1 and 1 ⩽ i ⩽ n. Then K_{n+2} is the subdivision of K_{n+1} × I given below and its various (n − 1)-faces are labeled as indicated:

Face of K_{n+2}  Face operator
e_{ℓ,0}  d_{(0,ℓ)},  1 ⩽ ℓ ⩽ n
e_{n,1}  d_{(n,1),}
d_{(i,ℓ)} × I  d_{(i,ℓ),}  1 ⩽ i < n − ℓ
d_{(i,ℓ)} × [0, 1 − 2^{−i}]  d_{(i,ℓ),}  1 ⩽ i = n − ℓ
d_{(i,ℓ)} × [1 − 2^{−i}, 1]  d_{(i,ℓ+1)},  1 ⩽ i = n − ℓ

•  • • • • Id d_{(0,1)} d_{(2,1)} d_{(1,2)} d_{(1,1)} d^{(0,2)}
Figure 12: K_{4} as a subdivision of K_{3} × I.

•  • •  •  •  •  •  • •  • •  • •  • •  •  •  • •  • (1, 1, 1) (0, 0, 0)  d_{(3,1)} d_{(0,3)} d_{(0,2)}  d_{(2,2)} d_{(1,1)}  d_{(2,1)} d_{(1,3)} d_{(1,2)}  d_{(0,1)}

Figure 13: K_{5} as a subdivision of K_{4} × I.

6. Diagonals on the Associahedra and Multiplihedra

The diagonal Δ_{P} on C_{∗} (P_{n+1}) descends to diagonals Δ_{J} on C_{∗} (J_{n+1}) and Δ_{K} on C_{∗} (K_{n+2}) via the cellular projections π : P_{n+1} → J_{n+1} and θ : P_{n+1} → K_{n+2} discussed in Section 2 above. This fact is an immediate consequence of Proposition 7.

Definition 20. 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 \underline{degenerate under f} if f(e) ⊆ X^{(r)} with r < k. A component a ⊗ b of Δ_{W} is \underline{degenerate under} f if either a or b is degenerate under f.

Let us identify the non-degenerate cells of P_{n+1} under π and θ.

Definition 21. Let A_{1}| ⋯ |A_{p} be a partition of \underline{n + 1} with p > 1 and let 1 ⩽ k < p. The subset A_{k} is \underline{exceptional} if for k < j ⩽ p, there is an element a_{i,j} ∈ A_{j} such that min A_{k} < a_{i,j} < max A_{k}.

Proposition 6. Let a = A_{1}| ⋯ |A_{p} be a face of P_{n+1} and let

d_{(i_{1}^{p−1},ℓ_{1}^{p−1})···(i_{s_{p−1}}^{p−1} ,ℓ_{s_{p−1}}^{p−1} )} ⋯ d_{(i_{1}^{1},ℓ_{1}^{1})···(i_{s_{1}}^{1} ,ℓ_{s_{1}}^{1} )}

be its unique representation as a composition of face operators.

(1) The following are all equivalent:

(1a) The face a is degenerate under π.

(1b) min A_{j} > min (A_{j+1} ∪ ⋯ ∪ A_{p}) with A_{j} exceptional for some j < p.

(1c) i_{1}^{k} > 0 and s_{k} > 1 for some k < p.

(2) The following are all equivalent:

(2a) The face a is degenerate under θ.

(2b) A_{j} is exceptional for some j < p.

(2c) s_{k} > 1 for some k < p.

Proof. Obvious.

Example 8. The subset A_{1} = {13} in the partition a = 13|24 is exceptional and the face a ⊂ P_{4} is degenerate under θ. In terms of compositions of face operators, the face a corresponds to d_{(0,1)(2,1)} (x_{1} ⋯ x_{5}) with s_{1} = 2. Furthermore, a is also non-degenerate under π since i_{1}^{1} = 0 (equivalently, min A_{1} < min A_{2}).

Next, we apply Tonks’ projection and obtain an explicit formula for the diagonal Δ_{K} on the associahedra.

Proposition 7. 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) given by 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) ⟶_{Δ_{X}} C_{∗} (X) ⊗ C_{∗} (X) .

Proof. Obvious.

In Section 2 we established correspondences between faces of P_{n+1} and PLT’s with n + 2 leaves and between faces of K_{n+2} and PRT’s with n + 2 leaves. Since a PRT can be viewed as a PLT, faces of K_{n+2} can be viewed as faces of P_{n+1}.

Definition 22. For n ⩾ 0, let Δ_{P} be the diagonal on C_{∗} (P_{n+1}) and let θ : P_{n+1} → K_{n+2} be Tonks’ projection. View each face e of the associahedron K_{n+2} as a face of P_{n+1} and define Δ_{K} : C_{∗} (K_{n+2}) → C_{∗} (K_{n+2}) ⊗ C_{∗} (K_{n+2}) by

Δ_{K}(e) = (θ ⊗ θ)Δ_{P} (e).

Corollary 2. The map Δ_{K} given by Definition 22 is the diagonal on C_{∗} (K_{n+2}) induced by Δ_{P}.

Proof. This is an immediate application of Proposition 7.

Consider a CP u ⊗ v = c (F) ⊗ r (F) related to SCP a ⊗ b = c (E) ⊗ r (E) via F = D_{N_{q−1}} ⋯ D_{1}R_{M_{p−1}} ⋯ R_{1}E. Note that both factors of u ⊗ v are nondegenerate under θ if and only if b is non-degenerate and each M_{j} has maximal cardinality. Alternatively, if d^{p} ⋯ d^{1}⊗d^{q} ⋯ d^{1} (e^{n} ⊗ e^{n}) is a component of Δ_{K} (e^{n}) , factors in the corresponding pairing T_{p} ⊗ T_{q} of PRT’s have n + 2 leaves, p + 1 and q + 1 nodes and respective dimensions n − p and n − q. Hence p + q = n and T_{p} ⊗ T_{q} has exactly n+2 nodes. But if T_{u}⊗T_{v} is the pairing of PLT’s corresponding to u⊗v, forgetting levels in T_{u} ⊗T_{v} gives the pairing of PRT’s corresponding to θ (u)⊗θ (v). Since the number of nodes in T_{u} ⊗T_{v} is at least n+2, θ (a)⊗θ (b) is non-degenerate in Δ_{K} (e^{n}) if and only if the total number of nodes in T_{u} ⊗ T_{v} is exactly n + 2.

Choose a system of generators e^{n} ∈ C_{n} (K_{n+2}) , n ⩾ 0. The signs in (6.1) below follow from (3.2).

Definition 23 ([15]). For each n ⩾ 0, define Δ_{K} on e^{n} ∈ C_{n} (K_{n+2}) by

Δ_{K} (e^{n}) = ∑_{0⩽p⩽p+q=n+2} (−1)^{ϵ} d_{(i_{p−1},ℓ_{p−1})} ⋯ d_{(i_{1},ℓ_{1})}⊗d_{(i′_{q−1},ℓ′_{q−1})} ⋯ d_{(i′_{1},ℓ′_{1})} (e^{n} ⊗ e^{n}) ,

(6.1)

where

ϵ = ∑_{j=1}^{p−1} i_{j}(ℓ_{j} + 1) + ∑_{k=1}^{q−1}(i′_{k} + k + q)ℓ′_{k},

and lower indices ((i_{1}, ℓ_{1}) , …, (i_{p−1}, ℓ_{p−1}) ; (i′_{1}, ℓ′_{1}) , …, (i′_{q−1}, ℓ′_{q−1})) range over all solutions of the following system of inequalities:

\{ \begin{matrix}1 ⩽ i′_{j} < i′_{j−1} ⩽ n + 1 & (1) \\ 1 ⩽ ℓ′_{j} ⩽ n + 1 − i′_{j} − ℓ′_{(j−1)} & (2) \\ 0 ⩽ i_{k} ⩽ min_{o′(t_{k})<r<k} \{i_{r}, i′_{t_{k}} − ℓ_{(o′(t_{k}))}\} & (3) \\ 1 ⩽ ℓ_{k} = ϵ_{k} − i_{k} − ℓ_{(k−1)}, & (4) \end{matrix} \}\begin{matrix}1⩽k⩽p−1 \\ 1⩽j⩽q−1 \end{matrix}  (6.2)

where

{ϵ_{1} < ⋯ < ϵ_{q−1}} = {1, …, n} \ {i′_{1}, …, i′_{q−1}};
ϵ_{0} = ℓ_{0} = ℓ′_{0} = i_{p} = i′_{q} = 0;
i_{0} = i′_{0} = ϵ_{q} = ℓ_{(p)} = ℓ′_{(q)} = n + 1;
ℓ_{(u)} = ∑_{j=0}^{u} ℓ_{j} for 0 ⩽ u ⩽ p;
ℓ′_{(u)} = ∑_{k=0}^{u} ℓ′_{k} for 0 ⩽ u ⩽ q;
t_{u} = min {r | i′_{r} + ℓ′_{(r)} − ℓ′_{(o(u))} > ϵ_{u} > i′_{r}};
o (u) = max {r | i′_{r} ⩾ ϵ_{u}}; and
o′ (u) = max {r | ϵ_{r} ⩽ i′_{u}} .

Extend Δ_{K} to proper faces of K_{n+2} via the standard comultiplicative extension.

Theorem 7. The map Δ_{K} given by Definition 23 is the diagonal induced by θ.

Proof. If v = L_{β}(v′) is non-degenerate in some component u ⊗ v of Δ_{P}, then so is v′, and we immediately obtain inequality (1) of (6.2). Next, each non-degenerate decreasing b uniquely determines an SCP a⊗b. Although a may be degenerate, there is a unique non-degenerate u = R_{M_{p−1}} ⋯ R_{M_{1}}(a) obtained by choosing each M_{j} with maximal cardinality (the case M_{j} = ∅ 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 operators, straightforward examination shows that u has form u = d_{(i_{p−1},ℓ_{p−1})} ⋯ d_{(i_{1},ℓ_{1})}(e^{n}) and is related to b = d_{(i′_{q−1},ℓ′_{q−1})} ⋯ d_{(i′_{1},ℓ′_{1})} (e^{n}) by

i_{k} = min_{o′(t_{k})<r<k} {i_{r}, i′_{t_{k}} − ℓ_{(o′(t_{k}))}} , 1 ⩽ k < p;

and equality holds in (4) of (6.2). Finally, let b = L_{β}(b̄). As we vary b̄ in all possible ways, each b̄ is non-degenerate and we obtain all possible non-degenerate CP’s ū ⊗ b̄ associated with ā ⊗ b̄ (ū = u when b̄ = b and β = ∅). For each such ū = d_{(i_{p−1},ℓ_{p−1})} ⋯ d_{(i_{1},ℓ_{1})}(e^{n}) we have both inequality (3) and equality in (4) of (6.2). Hence, the theorem is proved.

Example 9. On K_{4} we obtain:

Δ_{K} (e^{2}) = {d_{(0,1)}d_{(0,1)} ⊗ 1 + 1 ⊗ d_{(1,1)}d_{(2,1)} + d_{(0,2)} ⊗ d_{(1,1)}

+d_{(0,2)} ⊗ d_{(1,2)} + d_{(1,1)} ⊗ d_{(1,2)} − d_{(0,1)} ⊗ d_{(2,1)}} (e^{2} ⊗ e^{2}).

7. Application: Tensor Products of A_{∞}-(co)algebras

In this section, we use Δ_{K} to define the tensor product of A_{∞}-(co)algebras in maximal generality. We note that a special case was given by J. Smith [17] for certain objects with a richer structure than we have here. We also mention that Lada and Markl [11] defined an A_{∞} tensor product structure on a construct different from the tensor product of graded modules.

We adopt the following notation and conventions: Let R be a commutative ring with unity; R-modules are assumed to be ℤ-graded, tensor products and Hom’s are defined over R and all maps are R-module maps unless otherwise indicated. If an R-module V is connected, \overline{V} = V/V_{0}. The symbol 1 : V → V denotes the identity map; the suspension and desuspension maps ↑ and ↓ shift dimension by +1 and −1, respectively. Define V^{⊗0} = R and V^{⊗n} = V ⊗ ⋯ ⊗ V with n > 0 factors; then T V = ⊕_{n⩾0}V^{⊗n} and T^{a}V (respectively, T^{c}V) denotes the free tensor algebra (respectively, cofree tensor coalgebra) of V. Given R-modules V_{1}, …, V_{n}, a permutation σ ∈ S_{n} induces an isomorphism σ : V_{1} ⊗ ⋯ ⊗ V_{n} → V_{σ^{−1}(1)} ⊗ ⋯ ⊗ V_{σ^{−1}(n)} by σ(x_{1} ⋯ x_{n}) = ± x_{σ^{−1}(1)} ⋯ x_{σ^{−1}(n)}, where ± is the Koszul sign. In particular, σ_{2,n} = (1 3 ⋯ (2n − 1) 2 4 ⋯ 2n) : (A ⊗ B)^{⊗n} → A^{⊗n} ⊗ B^{⊗n} and σ_{n,2} = σ_{2,n}^{−1} induce

isomorphisms (σ_{2,n})^{∗} : Hom (A^{⊗n} ⊗ B^{⊗n}, A ⊗ B) → Hom ((A ⊗ B)^{⊗n}, A ⊗ B)

and (σ_{n,2})_{∗}: Hom (A ⊗ B, A^{⊗n} ⊗ B^{⊗n}) → Hom (A ⊗ B, (A ⊗ B)^{⊗n}). The map ι : Hom(U, V) ⊗ Hom (U′, V′) → Hom (U ⊗ U′, V ⊗ V′) is the canonical isomorphism. If f : V^{⊗p} → V^{⊗q} is a map, we let f_{i,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 A_{∞}-(co)algebras paying particular attention to the signs. Let A be a connected R-module equipped with operations {φ^{k} ∈ Hom^{k−2} (A^{⊗k}, A)}_{k⩾1}. For each k and n ⩾ 1, linearly extend φ^{k} to A^{⊗n} via

∑_{i=0}^{n−k} φ_{i,n−k−i}^{k} : A^{⊗n} → A^{⊗n−k+1},

and consider the induced map of degree −1 given by

∑_{i=0}^{n−k} (↑ φ^{k} ↓^{⊗k})_{i,n−k−i} : (↑ \overline{A})^{⊗n} → (↑ \overline{A})^{⊗n−k+1} .

Let B̃A = T^{c} (↑ \overline{A}) and define a map d_{B̃A} : B̃A → B̃A of degree −1 by

d_{B̃A} = ∑_{\begin{matrix}1⩽k⩽n \\ 0⩽i⩽n−k \end{matrix}} (↑ φ^{k} ↓^{⊗k})_{i,n−k−i} .  (7.1)

The identities (−1)^{[n/2]} ↑^{⊗n}↓^{⊗n}= 1^{⊗n} and [n/2] + [(n + k) /2] ≡ nk + [k/2] (mod 2) imply that

d_{B̃A} = ∑_{\begin{matrix}1⩽k⩽n \\ 0⩽i⩽n−k \end{matrix}} (−1)^{[(n−k)/2]+i(k+1)} ↑^{⊗n−k+1} φ_{i,n−k−i}^{k} ↓^{⊗n} .  (7.2)

Definition 24. (A, φ^{n})_{n⩾1} is an \underline{A_{∞}-algebra} if d_{B̃A}^{2} = 0.

Proposition 8. For each n ⩾ 1, the operations {φ^{n}} on an A_{∞}-algebra satisfy the following quadratic relations:

∑_{\begin{matrix}0⩽ℓ⩽n−1 \\ 0⩽i⩽n−ℓ−1 \end{matrix}} (−1)^{ℓ(i+1)} φ^{n−ℓ}φ_{i,n−ℓ−1−i}^{ℓ+1} = 0.  (7.3)

Proof. For n ⩾ 1,

0 = ∑_{\begin{matrix}1⩽k⩽n \\ 0⩽i⩽n−k \end{matrix}} (−1)^{[(n−k)/2]+i(k+1)} ↑ φ^{n−k+1} ↓^{⊗n−k+1}↑^{⊗n−k+1} φ_{i,n−k−i}^{k} ↓^{⊗n}

= ∑_{\begin{matrix}1⩽k⩽n \\ 0⩽i⩽n−k \end{matrix}} (−1)^{n−k+i(k+1)} φ^{n−k−1}φ_{i,n−k−i}^{k}

= − (−1)^{n} ∑_{\begin{matrix}0⩽ℓ⩽n−1 \\ 0⩽i⩽n−ℓ−1 \end{matrix}} (−1)^{ℓ(i+1)} φ^{n−ℓ}φ_{i,n−ℓ−1−i}^{ℓ+1}.

It is easy to prove that

Proposition 9. If (A, φ^{n})_{n⩾1} is an A_{∞}-algebra, then (B̃A, d_{B̃A}) is a DGC.

Definition 25. Let (A, φ^{n})_{n⩾1} be an A_{∞}-algebra. \underline{The tilde bar construction on A}

is the DGC (B̃A, d_{B̃A}) .

Definition 26. Let A and C be A_{∞}-algebras. A chain map f = f^{1} : A → C is a \underline{map of A_{∞}-algebras} if there is a sequence of maps \{f^{k} ∈ Hom^{k−1} (A^{⊗k}, C)\}_{k⩾2} such that

f̃ = ∑_{n⩾1} (∑_{k⩾1} ↑ f^{k} ↓^{⊗k})^{⊗n} : B̃A → B̃C

is a DGC map.

Dually, consider a sequence of operations {ψ^{k} ∈ Hom^{k−2} (A, A^{⊗k})}_{k⩾1}. For each k and n ⩾ 1, linearly extend each ψ^{k} to A^{⊗n} via

∑_{i=0}^{n−1} ψ_{i,n−1−i}^{k} : A^{⊗n} → A^{⊗n+k−1},

and consider the induced map of degree −1 given by

∑_{i=0}^{n−1} (↓^{⊗k} ψ^{k} ↑)_{i,n−1−i} : (↓ \overline{A})^{⊗n} → (↓ \overline{A})^{⊗n+k−1} .

Let Ω̃A = T^{a} (↓ \overline{A}) and define a map d_{Ω̃A} : Ω̃A → Ω̃A of degree −1 by

d_{Ω̃A} = ∑_{\begin{matrix}n,k⩾1 \\ 0⩽i⩽n−1 \end{matrix}} (↓^{⊗k} ψ^{k} ↑)_{i,n−1−i} ,

which can be rewritten as

d_{Ω̃A} = ∑_{\begin{matrix}n,k⩾1 \\ 0⩽i⩽n−1 \end{matrix}} (−1)^{[n/2]+i(k+1)+k(n+1)} ↓^{⊗n+k−1} ψ_{i,n−1−i}^{k} ↑^{⊗n} .  (7.4)

Definition 27. (A, ψ^{n})_{n⩾1} is an \underline{A_{∞}-coalgebra} if d_{Ω̃A}^{2} = 0.

Proposition 10. For each n ⩾ 1, the operations {ψ^{k}} on an A_{∞}-coalgebra satisfy the following quadratic relations:

∑_{\begin{matrix}0⩽ℓ⩽n−1 \\ 0⩽i⩽n−ℓ−1 \end{matrix}} (−1)^{ℓ(n+i+1)} ψ_{i,n−ℓ−1−i}^{ℓ+1}ψ^{n−ℓ} = 0.  (7.5)

Proof. The proof is similar to the proof of Proposition 8 and is omitted.

Again, it is easy to prove that

Proposition 11. If (A, ψ^{n})_{n⩾1} is an A_{∞}-coalgebra , then (Ω̃A, d_{Ω̃A}) is a DGA.

Definition 28. Let (A, ψ^{n})_{n⩾1} be an A_{∞}-coalgebra. The \underline{tilde cobar construction on}

\underline{A}is the DGA (Ω̃A, d_{Ω̃A}) .

Definition 29. Let A and B be A_{∞}-coalgebras. A chain map g = g^{1} : A → B is a \underline{map of A_{∞}-coalgebras} if there is a sequence of maps \{g^{k} ∈ Hom^{k−1} (A, B^{⊗k})\}_{k⩾2} such that

g̃ = ∑_{n⩾1} (∑_{k⩾1} ↓^{⊗k} g^{k} ↑)^{⊗n} : Ω̃A → Ω̃B,  (7.6)

is a DGA map.

The structure of an A_{∞}-(co)algebra is encoded by the quadratic relations among its operations (also called “higher homotopies”). Although the “direction,” i.e., sign, of these higher homotopies is arbitrary, each choice of directions determines a set of signs in the quadratic relations, the “simplest” of which appears on the algebra side when no changes of direction are made; see (7.1) and (7.3) above. Interestingly, 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 appropriate choices are as in (7.3) and (7.5).

Let A_{∞} = ⊕_{n⩾2}C_{∗} (K_{n}) and let (A, φ^{n})_{n⩾1} be an A_{∞}-algebra with quadratic relations as in (7.3). For each n ⩾ 2, associate e^{n−2} ∈ C_{n−2} (K_{n}) with the operation φ^{n} via

e^{n−2} ↦ (−1)^{n} φ^{n}  (7.7)

and each codimension 1 face d_{(i,ℓ)} (e^{n−2}) ∈ C_{n−3} (K_{n}) with the quadratic composition

d_{(i,ℓ)} (e^{n−2}) ↦ φ^{n−ℓ}φ_{i,n−ℓ−1−i}^{ℓ+1}.  (7.8)

Then (7.7) and (7.8) induce a chain map

ζ_{A} : A_{∞} ⟶ ⊕_{n⩾2}Hom^{∗} (A^{⊗n}, A)  (7.9)

representing the A_{∞}-algebra structure on A. Dually, if (A, ψ^{n})_{n⩾1} is an A_{∞}-coalge-bra with quadratic relations as in (7.5), the associations

e^{n−2} ↦ ψ^{n} and d_{(i,ℓ)} (e^{n−2}) ↦ ψ_{i,n−ℓ−1−i}^{ℓ+1}ψ^{n−ℓ}

induce a chain map

ξ_{A} : A_{∞} ⟶ ⊕_{n⩾2}Hom^{∗} (A, A^{⊗n})  (7.10)

representing the A_{∞}-coalgebra structure on A. The definition of the tensor product is now immediate:

Definition 30. The \underline{tensor product of A_{∞}-algebras} (A, ζ_{A}) and (B, ζ_{B}) is given by

(A, ζ_{A}) ⊗ (B, ζ_{B}) = (A ⊗ B, ζ_{A⊗B}) ,

where ζ_{A⊗B} is the sum of the compositions

C_{∗}(K_{n})  ⟶^{ζ_{A⊗B}}  Hom((A ⊗ B)^{⊗n}, A ⊗ B)
Δ_{K} ↓  ↑ (σ_{2,n})^{∗}ι
C_{∗}(K_{n}) ⊗ C_{∗}(K_{n}) ⟶_{ζ_{A}⊗ζ_{B}} Hom(A^{⊗n}, A) ⊗ Hom (B^{⊗n}, B)

over all n ⩾ 2; the A_{∞}-algebra operations Φ^{n} on A ⊗ B are given by

Φ^{n} = (σ_{2,n})^{∗} ι (ζ_{A} ⊗ ζ_{B}) Δ_{K} (e^{n−2}) .

Dually, the \underline{tensor product of A_{∞}-coalgebras} (A, ξ_{A}) and (B, ξ_{B}) is given by

(A, ξ_{A}) ⊗ (B, ξ_{B}) = (A ⊗ B, ξ_{A⊗B}) ,

where ξ_{A⊗B} is the sum of the compositions

C_{∗}(K_{n})  ⟶^{ξ_{A⊗B}}  Hom(A ⊗ B, (A ⊗ B)^{⊗n})
Δ_{K} ↓  ↑ (σ_{n,2})_{∗}ι
C_{∗}(K_{n}) ⊗ C_{∗}(K_{n}) ⟶_{ξ_{A}⊗ξ_{B}} Hom(A, A^{⊗n}) ⊗ Hom (B, B^{⊗n})

over all n ⩾ 2; the A_{∞}-coalgebra operations Ψ^{n} on A ⊗ B are given by

Ψ^{n} = (σ_{n,2})_{∗} ι (ξ_{A} ⊗ ξ_{B}) Δ_{K} (e^{n−2}) .

Example 10. If (A, ψ^{n})_{n⩾1} is an A_{∞}-coalgebra, the following A_{∞} operations arise on A ⊗ A:

Ψ^{1} = ψ^{1} ⊗ 1 + 1 ⊗ ψ^{1}
Ψ^{2} = σ_{2,2} (ψ^{2} ⊗ ψ^{2})
Ψ^{3} = σ_{3,2} (ψ_{0}^{2}ψ_{0}^{2} ⊗ ψ^{3} + ψ^{3} ⊗ ψ_{1}^{2}ψ_{0}^{2})
Ψ^{4} = σ_{4,2} (ψ_{0}^{2}ψ_{0}^{2}ψ_{0}^{2} ⊗ ψ^{4} + ψ^{4} ⊗ ψ_{2}^{2}ψ_{1}^{2}ψ_{0}^{2} + ψ_{0}^{3}ψ_{0}^{2} ⊗ ψ_{1}^{2}ψ_{0}^{3}
+ψ_{0}^{3}ψ_{0}^{2} ⊗ ψ_{1}^{3}ψ_{0}^{2} + ψ_{1}^{2}ψ_{0}^{3} ⊗ ψ_{1}^{3}ψ_{0}^{2} − ψ_{0}^{2}ψ_{0}^{3} ⊗ ψ_{2}^{2}ψ_{0}^{3})
⋮  ⋮

Note that the compositions in Definition 30 only use the operations ψ^{n} and not the quadratic relations (7.5). Indeed, one can iterate an arbitrary family of operations {ψ^{n}} as in Example (10) to produce iterated operations Ψ^{n} : A^{⊗k} → (A^{⊗k})^{⊗n} whether or not (A, ψ^{n}) is an A_{∞}-coalgebra. Of course, the Ψ^{n}’s define an A_{∞}-coalgebra structure on A^{⊗k} whenever d_{Ω̃(A^{⊗k})}^{2} = 0, and we make extensive use of this fact in the sequel [16]. Finally, since Δ_{K} is homotopy coassociative (not strict), the tensor product only iterates up to homotopy. In the sequel we always coassociate on the extreme left.

8. Appendix

For completeness, we review the definitions of the functors given by Kadeishvili and Saneblidze in [8], [9] from the category of 1-reduced simplicial sets to the category of cubical sets and from the category of 1-reduced cubical sets to the category of permutahedral sets.

8.1. The cubical set functor ΩX

Given a 1-reduced simplicial set X = {X_{n}, ∂_{i}, s_{i}}_{n⩾0}, define the graded set ΩX as follows: Let X^{c} be the graded set of formal expressions

X_{n+k}^{c} = {η_{i_{k}} ⋯ η_{i_{1}}η_{i_{0}}(x) | x ∈ X_{n}}_{n⩾0;k⩾0},

where η_{i_{0}} = 1, i_{1} ⩽ ⋯ ⩽ i_{k}, 1 ⩽ i_{j} ⩽ n + j − 1, 1 ⩽ j ⩽ k, and let X̄^{c} = s^{−1}(X_{>0}^{c}) be the desuspension of X^{c}. Let Ω′X be the free graded monoid generated by X̄^{c}; denote elements of Ω′X by x̄_{1} ⋯ x̄_{k}, where x_{j} ∈ X_{m_{j}+1}, m_{j} ⩾ 0. The total degree m = |x̄_{1} ⋯ x̄_{k}| = ∑ |x̄_{j}| and we write x̄_{1} ⋯ x̄_{k} ∈ (Ω′X)_{m}. The product of two elements x̄_{1} ⋯ x̄_{k} and ȳ_{1} ⋯ ȳ_{ℓ} is given by concatenation x̄_{1} ⋯ x̄_{k}ȳ_{1} ⋯ ȳ_{ℓ}; the only relation on Ω′X is strict associativity. Let ΩX be the graded monoid obtained from Ω′X via

ΩX = Ω′X⧸∼ ,

where \overline{η_{n}(x)} ∼ \overline{s_{n}(x)} for x ∈ X_{>0}, and x̄_{1} ⋯ \overline{η_{m_{i}+1}(x_{i})} · x̄_{i+1} ⋯ x̄_{k} ∼ x̄_{1} ⋯ x̄_{i} · \overline{η_{1}(x_{i+1})} ⋯ x̄_{k} for x_{i} ∈ X_{m_{i}+1}^{c}, i < k. Let MX denote the free monoid generated by X̄ = s^{−1}(X_{>0}); there is an inclusion of graded modules MX ⊂ Ω′X.

Apparently Ω′X canonically admits the structure of a cubical set. Denote the components of Alexander-Whitney diagonal by

ν_{i} : X_{n} → X_{i} × X_{n−i},

where ν_{i}(x) = ∂_{i+1} ⋯ ∂_{n}(x) × ∂_{0} ⋯ ∂_{i−1}(x), 0 ⩽ i ⩽ n, and let x^{n} ∈ X_{n} denote an n-simplex simplex. Then

ν_{i}(x^{n}) = (x′)^{i} × (x′′)^{n−i} ∈ X_{i} × X_{n−i}

for all n > 0. For 1 ⩽ i ⩽ n − 1, define face operators d_{i}^{0}, d_{i}^{1} : (ΩX)_{n−1} → (ΩX)_{n−2} on a (monoidal) generator \overline{x^{n}} ∈ X̄_{n} ⊂ X̄_{n}^{c} by

d_{i}^{0} (\overline{x^{n}}) = \overline{(x′)^{i}} · \overline{(x′′)^{n−i}} and d_{i}^{1} (\overline{x^{n}}) = \overline{∂_{i} (x^{n})},

and extend to elements x̄_{1} ⋯ x̄_{k} ∈ MX via

\begin{matrix}d_{i}^{0} (\overline{x}_{1} ⋯ \overline{x}_{k}) = \overline{x}_{1} ⋯ \overline{(x′_{q})^{j_{q}}} · \overline{(x′′_{q})^{m_{q}−j_{q}+1}} ⋯ \overline{x}_{k}, \\ d_{i}^{1} (\overline{x}_{1} ⋯ \overline{x}_{k}) = \overline{x}_{1} ⋯ \overline{∂_{j_{q}} (x_{q})} ⋯ \overline{x}_{k}, \end{matrix}

where i = m_{(q−1)} +j_{q} ⩽ m_{(q)}, 1 ⩽ i ⩽ n−1, 1 ⩽ q ⩽ k. Then the defining identities for a cubical set involving d_{i}^{0} and d_{i}^{1} can easily be checked on MX. In particular, the simplicial relations between the ∂_{i}’s imply the cubical relations between d_{i}^{1}’s; the associativity relations between ν_{i}’s imply the cubical relations between d_{i}^{0}’s, and the commutativity relations between ∂_{i}’s and ν_{j}’s imply the cubical relations between d_{i}^{1}’s and d_{j}^{0}’s. Next, define degeneracy operators η_{i} : (ΩX)_{n−1} → (ΩX)_{n} on a (monoidal) generator \overline{x} ∈ (X̄^{c})_{n−1} by

η_{i}(\overline{x}) = \overline{η_{i}(x)};

and extend to elements x̄_{1} ⋯ x̄_{k} ∈ ΩX via

\begin{matrix}η_{i} (\overline{x}_{1} ⋯ \overline{x}_{k}) = \overline{x}_{1} ⋯ η_{j_{q}}(\overline{x_{q}}) ⋯ \overline{x}_{k}, \\ η_{n} (\overline{x}_{1} ⋯ \overline{x}_{k}) = \overline{x}_{1} ⋯ \overline{x}_{m_{k−1}} · η_{m_{k}+1} (\overline{x}_{k}) , \end{matrix}

where i = m_{(q−1)} + j_{q} ⩽ m, 1 ⩽ i ⩽ n − 1, 1 ⩽ q ⩽ k, and extend face operators on degenerate elements inductively so that the defining identities of a cubical set are satisfied. Then in particular, the following identities hold for all x^{n} ∈ X_{n}:

\begin{matrix}d_{1}^{0} (\overline{x^{n}}) = \overline{(x′)^{1}} · \overline{(x′′)^{n−1}} = e · \overline{(x′′)^{n−1}} = \overline{(x′′)^{n−1}} = \overline{∂_{0} (x^{n})}, \\ d_{n−1}^{0} (\overline{x^{n}}) = \overline{(x′)^{n−1}} · \overline{(x′′)^{1}} = \overline{(x′′)^{n−1}} · e = \overline{(x′)^{n−1}} = \overline{∂_{n} (x^{n})}, \end{matrix}

where e ∈ (ΩX)_{0} denotes the unit. It is easy to see that the cubical set {ΩX, d_{i}^{0}, d_{i}^{1}, η_{i}} depends functorially on X.

8.2. The permutahedral set functor ΩQ Let Q = (Q_{n}, d_{i}^{0}, d_{i}^{1}, η_{i})_{n⩾0} be a 1-reduced cubical set. Recall that the diagonal

Δ : C_{∗}(Q) → C_{∗}(Q) ⊗ C_{∗}(Q)

on C_{∗}(Q) is defined on a ∈ Q_{n} by

Δ(a) = Σ (−1)^{ϵ}d_{B}^{0}(a) ⊗ d_{A}^{1}(a),

where d_{B}^{0} = d_{j_{1}}^{0} ⋯ d_{j_{q}}^{0}, d_{A}^{1} = d_{i_{1}}^{1} ⋯ d_{i_{p}}^{1}, summation is over all shuffles (A; B) = (i_{1} < ⋯ < i_{q}; j_{1} < ⋯ < j_{p}) of \underline{n} and ϵ is the sign of the shuffle. The primitive components of the diagonal are given by the extreme cases A = ∅ and B = ∅.

Let Q̄ = s^{−1}(Q_{>0}) denote the desuspension of Q, let Ω′′Q be the free graded monoid generated by Q̄ with the unit e ∈ Q̄_{1} ⊂ Ω′′Q and let Υ be the set of formal expressions

Υ = {ϱ_{M_{k}|N_{k}}((⋯ ϱ_{M_{2}|N_{2}}(ϱ_{M_{1}|N_{1}}(ā_{1} · ā_{2}) · ā_{3}) ⋯) · ā_{k+1})| a_{i} ∈ Q_{r_{i}}}_{r_{i}⩾1;k⩾2},

M_{i}|N_{i} ∈ P_{r_{(i)},r_{i+1}}(r_{(i+1)}) or M_{i}|N_{i} ∈ P_{r_{i+1},r_{(i)}}(r_{(i+1)}), 1 ⩽ i ⩽ k. Note that one or more of the a_{i}’s can be the unit e. Adjoin the elements of Υ to Ω′′Q and obtain the graded monoid Ω′Q and let ΩQ be the monoid

ΩQ = Ω′Q⧸∼,

where ϱ_{M|N}(ā · b̄) ∼ ϱ_{N|M}(ā · b̄), ϱ_{j|\underline{n}\j}(e · ā) ∼ ϱ_{\underline{n}\j|j}(ā · e) ∼ \overline{η_{j}(a)}, a, b ∈ Q_{>0}, and ā_{1} ⋯ ϱ_{\underline{r_{i}}|r_{i}+1}(ā_{i} · e) · ā_{i+2} ⋯ ā_{k+1} ∼ ā_{1} ⋯ ā_{i} · ϱ_{1|\underline{r_{i+2}+1}\1}(e · ā_{i+2}) ⋯ ā_{k+1} for a_{i} ∈ Q_{r_{i}}, a_{i+1} = e, 1 ⩽ i ⩽ k. Then ΩQ is canonically a multipermutahedral set in the following way: First, define the face operator d_{A|B} on a monoidal generator ā ∈ Q̄_{n} by

d_{A|B}(ā) = \overline{d_{B}^{0}(a)} · \overline{d_{A}^{1}(a)}, A|B ∈ P_{∗,∗}(n).

Next, use the formulas in the definition of a singular multipermutahedral set (4.3) to define d_{A|B} and ϱ_{M|N} on decomposables. In particular, the following identities hold for 1 ⩽ i ⩽ n:

d_{i|\underline{n+1}\i} (\overline{a}) = \overline{d_{i}^{1}(a)} and d_{\underline{n+1}\i|i} (\overline{a}) = \overline{d_{i}^{0}(a)}.

It is easy to see that (ΩQ, d_{A|B}, ϱ_{M|N}) is a multipermutahedral set that depends functorially on Q.

Remark 3. The fact that the definition of ΩQ uses all cubical degeneracies is justified geometrically by the fact that a degenerate singular n-cube in the base of a path space fibration lifts to a singular (n − 1)-permutahedron in the fibre, which is degenerate with respect to Milgram’s projections [14] (c.f., the definition of the cubical set ΩX on a simplicial set X).

References

[1] J. F. Adams, On the cobar construction, Proc. Nat. Acad. Sci. (USA), 42 (1956), 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, Handbook of Algebraic Topology (Edited by I. M. James), North-Holland (1995), 505-583.

[4] H.S.M. Coxeter, W.O.J. Moser, Generators and relations for discrete groups, Springer-Verlag, 1972.

[5] Matthias R. Gaberdiel and Barton Zwiebach, Tensor constructions of open string theories I: Foundations, Nucl.Phys. B505 (1997), 569-624.

[6] N. Iwase and M. Mimura, Higher homotopy associativity, Lecture Notes in Math., 1370 (1986), 193-220.

[7] D. W. Jones, A general theory of polyhedral sets and corresponding Tcomplexes, Dissertationes Mathematicae, CCLXYI, Warszava (1988).

[8] T. Kadeishvili and S. Saneblidze, A cubical model of a fibration, preprint, AT/0210006.

[9] ——————–, The twisted Cartesian model for the double path space fibration, preprint, AT/0210224.

[10] D. M. Kan, Abstract homotopy I, Proc. Nat. Acad. Sci. U.S.A., 41 (1955), 1092-1096.

[11] T. Lada and M. Markl, Strongly homotopy Lie algebras, Communications in Algebra 23 (1995), 2147-2161.

[12] J.-L. Loday and M. Ronco, Hopf algebra of the planar binary trees, Adv. in Math. 139, No. 2 (1998), 293-309.

[13] S. Mac Lane, “Homology,” Springer-Verlag, Berlin/New York, 1967.

[14] R. J. Milgram, Iterated loop spaces, Ann. of Math., 84 (1966), 386-403.

[15] S. Saneblidze and R. Umble, A diagonal on the associahedra, preprint, math. AT/0011065.

[16] ————————–, The biderivative and A_{∞}-bialgebras, J. Homology, Homotopy and Appl., to appear, preprint, math. AT/0011065.

[17] J. R. Smith, “Iterating the cobar construction”, Memiors of the Amer. Math. 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: Proceedings of the Renaissance Conferences (Hartford CT / Luminy Fr 1995)” Contemporary Mathematics, 202 (1997), pp. 33-36.

[20] G. Ziegler, “Lectures on Polytopes,” GTM 152, Springer-Verlag, New York, 1995.

This article may be accessed via WWW at http://www.rmi.acnet.ge/hha/ or by anonymous ftp at

ftp://ftp.rmi.acnet.ge/pub/hha/volumes/2004/n1a20/v6n1a20.(dvi,ps,pdf)

Samson Saneblidze sane@rmi.acnet.ge

A. Razmadze Mathematical Institute Georgian Academy of Sciences M. Aleksidze st., 1 0193 Tbilisi, Georgia

Ronald Umble ron.umble@millersville.edu

Department of Mathematics Millersville University of Pennsylvania Millersville, PA. 17551