Theory and Applications of Categories, Vol. 32, No. 6, 2017, pp. 148–253.

HOMOTOPY THEORY FOR ALGEBRAS OVER POLYNOMIAL MONADS

M. A. BATANIN AND C. BERGER

Abstract. We study the existence and left properness of transferred model structures for “monoid-like” objects in monoidal model categories. These include genuine monoids, but also all kinds of operads as for instance symmetric, cyclic, modular, higher operads, properads and PROP’s. All these structures can be realised as algebras over polynomial monads.

We give a general condition for a polynomial monad which ensures the existence and (relative) left properness of a transferred model structure for its algebras. This condition is of a combinatorial nature and singles out a special class of polynomial monads which we call tame polynomial. Many important monads are shown to be tame polynomial.

Contents

Introduction  149

I Model structure for algebras over admissible monads  154
1 Homotopy cofibrations and h-monoidal model categories  154
2 Admissible monads on compactly generated model categories  165
3 Monoids in h-monoidal model categories  170
4 Diagram categories and Day convolution  173

II Algebras over tame polynomial monads  176
5 Cartesian monads and their internal algebra classifiers  176
6 Polynomial and tame polynomial monads  185
7 Free algebra extensions  197
8 Admissibility of tame polynomial monads and Quillen adjunctions  208

III Operads as algebras over polynomial monads  213
9 Operads based on contractible graphs  213
10 Operads based on general graphs  218
11 Baez-Dolan +-construction for polynomial monads  222
12 Higher operads  223

IV Graphs, trees and graph insertion  239

Received by the editors 2016-01-11 and, in final form, 2017-01-24.

Transmitted by Stephen Lack. Published on 2017-02-06.

2010 Mathematics Subject Classification: 18D20, 18D50, 55P48.

Key words and phrases: Quillen model category, polynomial monad, coloured operad, graph.

\begin{matrix}c \\ ◯ \end{matrix} M. A. Batanin and C. Berger, 2017. Permission to copy for private use granted.

13 Graphs and graph insertion  240
14 Planar trees and n-planar trees  243
15 Other definitions of graphs  247

Introduction

This text emerged from model-theoretical properties needed in our approach to the stabilisation hypothesis of Baez-Dolan [2]. Indeed, our proof [8] of this hypothesis relies on a careful homotopical analysis of n-operads and their symmetrisation. This analysis was initiated in [5, 6] but for the proof of the stabilisation hypothesis, the formulas obtained in loc. cit. had to be extended to a much broader context. Moreover, our study of stabilisation phenomena in [9] required the existence of a certain left Bousfield localisation of the transferred model structure on n-operads which turns n-operads into higher categorical analogues of E_{n}-operads [7, 17]. However, the available techniques for left Bousfield localisation (cf. [36]) are based on left properness, and it turned out to be surprisingly difficult to verify this property for n-operads. These two problems motivated us to reconsider foundational aspects of the homotopy theory of operads from a new categorical perspective.

In this article we address among others the general problem of preservation of left properness under transfer. We show that, under some specific conditions on the base category, a certain form of preservation is given for an interesting class of transfers, including those for the known model structures on monoids [60], reduced symmetric operads [11], general non-symmetric operads [52], reduced n-operads [5].

The common feature of all these transfers is that in each case the algebraic structure is governed by a polynomial monad in sets. Building on 2-categorical techniques developed in [6, 66, 67] we show that for this kind of algebraic structure, the existence of a transferred model structure and its left properness are intimately related. Both rely on a careful analysis of free algebra extensions. In the case of free monoid extensions this analysis has been done by Schwede-Shipley [60] in an exemplary and prototypical way. It is among the main results of this article that an analogous analysis is available for free algebra extensions over a general polynomial monad, provided the latter satisfies an extra-condition. This condition is of a combinatorial nature: it requires a certain category (attached to the polynomial monad) to be a coproduct of categories with terminal object. A polynomial monad fulfilling this extra-condition will be called tame. This article provides a combinatorial toolkit to construct free algebra extensions over any tame polynomial monad.

All operads above are algebras over tame polynomial monads. In particular, we recover Muro’s [52] recent construction of free non-symmetric operad extensions. Although nonsymmetric operads can be viewed as monoids for a certain circle-product, the construction of these free operad extensions is highly non-trivial, since the circle-product commutes with colimits only on one side, while the Schwede-Shipley construction of free monoid extensions is based on a commutation with colimits on both sides. The availability of a Schwede-Shipley type construction for free algebra extensions depends on the behaviour of what we call semi-free coproducts. These are coproducts of an algebra with a free algebra. Any tame polynomial monad induces a “polynomial expansion” for semi-free coproducts. E. g., the underlying object of the coproduct M ∨ F_{T} (K) of a monoid M with a free monoid F_{T} (K) can be computed as follows (cf. [60] and Section 9.2):

M ∨ F_{T} (K) = ∐_{n≥0} M ⊗ (K ⊗ M)^{⊗n}.  (1)

The existence of an analogous functorial “polynomial expansion” for semi-free coproducts of T -algebras over a tame polynomial monad T is the main ingredient for a transferred model structure on T -algebras with good properties.

Interestingly, the question of left properness has been dealt with in literature only recently in some special cases, cf. Cisinski-Moerdijk [18, Theorem 8.7] and Muro [53, Theorem 1.11]. Although the monoid axiom of Schwede-Shipley [60] gives a quite precise criterion for the existence of a transfer, the monoid axiom alone does not guarantee preservation of left properness under transfer. We propose in this article a common strengthening of the monoid axiom and of left properness which ensures that the transferred model structure on T -algebras is left proper if T is tame polynomial. We also show (cf. [31, 61]) that a relative form of left properness (namely, weak equivalences between T -algebras with cofibrant underlying object are closed under pushout along cofibrations) already follows from the monoid axiom.

This strengthening crucially involves a model-theoretical concept of h-cofibration. We call a Quillen model category [55] h-monoidal if it is a monoidal model category in the sense of Hovey [37] and the tensor product of a (trivial) cofibration with an arbitrary object is a (trivial) h-cofibration. An h-monoidal model category, which is compactly generated [14], satisfies the monoid axiom of Schwede-Shipley. Most of the model categories of algebraic topologists are compactly generated h-monoidal. If in addition the class of weak equivalences is closed under tensor product (e.g. all objects are cofibrant) then the model category is called strongly h-monoidal.

Our main theorem can now be stated as follows:

0.1. Theorem. For any tame polynomial monad T in sets and any compactly generated monoidal model category E fulfilling the monoid axiom, the category of T -algebras in E admits a relatively left proper transferred model structure.

The transferred model structure is left proper provided E is strongly h-monoidal.

Examples of T -algebras in E for tame polynomial monads T include monoids, nonsymmetric operads, reduced symmetric operads, reduced n-operads, reduced cyclic operads, as well as higher opetopic extensions of all these structures. In several of these cases, existence results for a transferred model structure (under some conditions on E) were known before. It seems however that even in the known cases, our assumptions on E are weaker than those which appeared in literature. Moreover, the discussion of left properness in the generality considered here seems to be new. Even more importantly, the uniformity of our approach allows us to give explicit formulas for the total left derived functors induced by morphisms of polynomial monads. These explicit formulas have often concrete applications.

Failure of tameness for a polynomial monad very often produces obstructions for the existence of transfer. However, these obstructions can be removed by imposing more restrictive conditions on the base category E. For instance, if E is the category of chain complexes over a field of characteristic 0, or the category of simplicial sets, resp. compactly generated topological spaces with the Quillen model structure, then a transferred model structure for algebras in E over any (tame or not tame) polynomial monad exists. The question of left properness is more subtle, yet.

The article is subdivided into four rather independent parts.

Part 1 develops basic properties of h-monoidal model categories and relates this notion to the monoid axiom of Schwede-Shipley [60]. We recall the concept of compact generation [14] of a monoidal model category and give general “admissibility” conditions on a monad, sufficient for the existence and relative left properness of the transfer. Two themes are treated in some detail: monoids in h-monoidal model categories (closely following Schwede-Shipley [60] but adding left properness) and stability of h-monoidality under passage to “convoluted” diagram categories (here we extend some of the results of Dundas-Østvær-Röndigs [21]).

Part 2 is devoted to polynomial monads. This part relies on 2-categorical techniques developed in [6, 67], but we have tried to keep the presentation as self-contained as possible. These techniques are used to reformulate the construction of a pushout along a free T -algebra map as a left Kan extension of a certain functor attached to T. More generally, given a morphism of polynomial monads S → T, the induced functor Alg_{S}(E) → Alg_{T} (E), left adjoint to restriction, is expressible as a left Kan extension. Our main theorem then follows by combining this construction with the results of Part 1, since the explicit formula for free algebra extensions over a tame polynomial monad implies the admissibility of the latter.

At the end we study the Quillen adjunction induced by a morphism of tame polynomial monads. We show that in good cases the total left derived functor can be calculated as a homotopy colimit. Instances of this appear in [5], where a higher-categorical Eckmann-Hilton argument is used to show that the derived symmetrisation of the terminal noperad is homotopy-equivalent to the Fulton-MacPherson operads of compactified point configurations in ℝ^{n}; and in [27], where Giansiracusa computes the derived modular envelope of several cyclic operads. Doing so he closely follows Costello [19] who suggested that the derived modular envelope of the terminal planar cyclic operad is homotopy equivalent to the modular operad of nodal Riemann spheres with boundary. Notice that the main obstacle for Giansiracusa and Costello in rendering such a statement precise was the missing model structure on cyclic operads. This is by now not anymore the case.

Part 3 studies examples. We first show that the polynomial monads based on contractible graphs (i.e. trees) tend to be tame, at least their normalised or reduced versions^{1}. We then show that most of the polynomial monads for operads which are based on graphs rather than trees (such as modular operads, properads or PROP’s) are not tame, even if we consider just their normalised versions. For all these operad types there is no transferred model structure for chain operads in positive characteristics. Nevertheless, a transfer exists in characteristic 0. We get the surprising result that for any polynomial monad T, its Baez-Dolan +-construction T^{+} is a tame polynomial monad. This can be used to define a homotopy theory of homotopy T -algebras for any polynomial monad T.

1See Remarks 9.6 and 10.5 regarding a subtlety of the definitions of reduced operad and PROP.

We finally study in detail the monad for normalised n-operads. In [6, 5], the latter was shown to be polynomial. Here we show that it is tame polynomial, which is quite a bit harder. This particular example is of special interest for us for reasons explained at the beginning of this introduction. In fact, it was this example which motivated the whole project. We also show that the polynomial monads for general (non-reduced) symmetric, cyclic and n-operads for n ≥ 2, are not tame.

Part 4 contains a concise combinatorial definition of the notions of graph, tree and graph insertion. We decided to include this material here because the tameness of a given polynomial monad often relies on subtle properties of a canonically associated class of structured graphs. The monad multiplication reflects the operation of insertion of a graph into the vertex of another graph of the same class. This close relationship between graph insertion and operad types is actually the central idea of Markl’s article [46], and has been further developed in the recent book by Johnson-Yau [32], cf. also chapter 13.14 in the book [44] of Loday-Vallette. Our study of algebras over polynomial monads subsumes all these examples. Each class of graphs which is suitably closed under graph insertion defines a polynomial monad for which the question of tameness can be raised.

For the reader’s convenience we present here two tables which summarise various results obtained in this article. The first table presents monoidal model categories considered in Part 1 for which we were able to establish (strong) h-monoidality.

all objects  strongly

Monoidal model category cofibrant h-monoidal

h-monoidal

Simplicial sets (Quillen)  yes  yes  yes
Small categories (groupoids) (Joyal-Tierney)  yes  yes  yes
Complete Θ_{n}-spaces (Rezk)  yes  yes  yes
Chain complexes over a field  yes  yes  yes
C.g. topological spaces (Strøm)  yes  yes  yes

Modules over a commutative monoid

in a monoidal category with cofibrant objects  yes  yes  yes
C.g. topological spaces (Quillen)  no  yes  yes

Small 2-categories (2-groupoids) with

Gray tensor product (Lack) no yes yes

Modules over a commutative monoid

in a strongly h-monoidal model category no yes yes

Chain complexes over a commutative ring

with the projective model structure no no yes

Symmetric spectra in simplicial sets with

levelwise or stable projective model structures no no yes

Modules over commutative monoid

in an h-monoidal model category  no  no  yes

Figure 1: h-monoidal model categories

HOMOTOPY THEORY FOR ALGEBRAS OVER POLYNOMIAL MONADS  153

The second table contains the polynomial monads treated in Part 3 for which the question of tameness has been settled. This table refines a similar table contained in the aforementioned article [46] by Markl.

polynomial monad for type insertional class of graphs

tame

ℂ-diagrams  ℂ-coloured corollas  yes
monoids  linear rooted trees  yes
enriched categories  I-coloured linear
with object-set I  rooted trees  yes
non-symmetric operads  general  planar rooted trees  yes
symmetric operads  general  rooted trees  no
reduced  non-degenerate rooted trees  yes
constant-free  regular rooted trees  yes
normal  normal rooted trees  yes
planar cyclic operads  general  planar trees  no
reduced  non-degenerate planar trees  yes
constant-free  regular planar trees  yes
normal  normal planar trees  yes
cyclic operads  general  trees  no
reduced  non-degenerate trees  yes
constant-free  regular trees  yes
normal  normal trees  yes
n-operads for n ≥ 2  general  n-planar trees  no
reduced  non-degenerate n-planar trees  yes
constant-free  regular n-planar trees  yes
normal  normal n-planar trees  yes
dioperads  general  directed trees  no
normal  normal directed trees  yes
\frac{1}{2} PROP’s  general  \frac{1}{2} graphs  no
normal  normal \frac{1}{2} graphs  yes
modular operads  general  connected graphs (with genus)  no
normal  normal connected (stable) graphs  no
properads  general  loop-free connected directed graphs  no
normal  normal loop-free connected directed graphs  no
PROP’s  general  loop-free directed graphs  no
normal  normal loop-free directed graphs  no
wheeled operads  general  wheeled rooted trees  no
normal  normal wheeled rooted trees  yes
wheeled properads  general  connected directed graphs  no
normal  normal connected directed graphs  no
wheeled PROP’s  general  directed graphs  no
normal  normal directed graphs  no

Figure 2: Polynomial monads based on graphs

Part I

Model structure for algebras over admissible monads

1. Homotopy cofibrations and h-monoidal model categories

We introduce and investigate here a model-theoretical concept of h-cofibration^{2} which seems interesting in itself. The dual concept of an h-fibration has been studied by Rezk [56] under the name of sharp map. The definition of an h-cofibration only depends on the class of weak equivalences and on the existence of pushouts. In left proper model categories, the class of h-cofibrations can be considered as the closure of the class of cofibrations under cofibre equivalence, cf. Proposition 1.6. We prove a useful gluing lemma for weak equivalences between pushouts along h-cofibrations in left proper model categories, cf. Proposition 1.8. We mainly use h-cofibrations in order to formulate a strengthening of left properness (h-monoidality) well adapted to monoidal model categories. A similar concept has been developed by Dundas-Østvær-Röndigs [21, Definition 4.6].

In the course of studying basic properties of h-monoidal model categories, we establish in Propositions 1.13, 1.14 and 1.15 below some useful recognition criteria for hmonoidality. Since a compactly generated h-monoidal model categories fulfills the monoid axiom of Schwede-Shipley (Proposition 2.5) and is left proper (Lemma 1.12), these criteria are helpful tools in establishing the monoid axiom of Schwede-Shipley and/or the left properness of a given monoidal model category.

We have been advertised by Maltsiniotis that the notion of h-cofibration already appears in some of Grothendieck’s unpublished manuscripts. In recent work, Ara and Maltsiniotis use h-cofibrations to prove a version of the transfer theorem [1, Proposition 3.6] which is related to our Theorem 2.11.

For an object X of a category E the undercategory X/E has as objects morphisms with domain X, and as morphisms “commuting triangles” under X. If E carries a model structure then so does X/E. A map X → A → B in X/E is a cofibration, weak equivalence, resp. fibration if and only if the underlying map A → B in E is.

1.1. Definition. A morphism f : X → Y in a model category E is called an hcofibration if the functor f_{!} : X/E → Y/E (given by cobase change along f) preserves weak equivalences.

In more explicit terms, a morphism f : X → Y in E is an h-cofibration if and only if in each commuting diagram of pushout squares in E

2Mike Hopkins suggested the term flat morphism for h-cofibration, cf. [35]. Our terminology is in conflict with the terminology of Peter May and Kate Ponto [50, Chapter 17] who use the term hcofibration (resp. q-cofibration) to designate a cofibration in Strøm’s (resp. Quillen’s) model structure on topological spaces. We argue that this terminological conflict is not peculiar, because our h-cofibrations are defined for all model categories, while the h-cofibrations of May and Ponto are defined for topological model categories only. In those cases where the two definitions telescope each other, they do so in a nice way, cf. the proof of Proposition 1.17, especially its footnote.

[figure: X; A; w; B; Y; f; A′; w′; B′]  (2)

w′ is a weak equivalence as soon as w is.

1.2. Lemma. A model category is left proper if and only if each cofibration is an hcofibration.

Proof. If in diagram (2) above E is left proper, f is a cofibration and w a weak equivalence, then w′ is a weak equivalence as well, thus f is an h-cofibration. Conversely, if every cofibration is an h-cofibration, then (2) shows that weak equivalences are stable under pushout along cofibrations, so that E is left proper.

1.3. Lemma. The class of h-cofibrations is closed under composition, cobase change, retract, and under formation of finite coproducts.

Proof. Closedness under composition, cobase change and retract follows immediately from the definition. For closedness under finite coproducts, it is enough to show that for each h-cofibration f : X → Y and each object Z, the coproduct f ⊔1_{Z} is an h-cofibration. This follows from the fact that the commutative square

[figure: X; X ⊔ Z; Y; f; Y ⊔ Z; f ⊔ 1_{Z}]

is a pushout.

1.4. Lemma. –

(i) An object Z is h-cofibrant if and only if − ⊔ Z preserves weak equivalences.

(ii) The class of weak equivalences is closed under finite coproducts if and only if all objects of the model category are h-cofibrant.

(iii) The class of weak equivalences is closed under arbitrary coproducts whenever all objects are h-cofibrant and weak equivalences are closed under filtered colimits along coproduct injections.

Proof. The first statement expresses the fact that a pushout along the map from an initial object to Z is the same as taking the coproduct with Z. The second statement follows from the first and from the identity f ⊔ g = (1_{codomain(f)} ⊔ g) ∘ (f ⊔ 1_{domain(g)}). The third statement follows from the second and the fact that any coproduct can be calculated as a filtered colimit of finite coproducts with structure maps being coproduct injections.

1.5. Homotopy pushouts and cofibre equivalences. –

A commutative square in a general model category

[figure: A; B; C; D]

will be called a formal homotopy pushout if for any factorisation A ↣ B′ ⟶^{∼} B (resp. A ↣ C′ ⟶^{∼} C) of A → B (resp. A → C) into a cofibration followed by a weak equivalence, the induced map B′ ∪_{A} C′ → D is a weak equivalence.

In left proper model categories, it suffices to choose a particular factorisation of A → B and check that B′∪_{A}C → D is a weak equivalence. We will see in Corollary 1.9 below that in left proper model categories, formal homotopy pushouts are homotopy pushouts (i.e. homotopy colimits). Yet, in order to avoid any confusion, we maintain the terminological distinction.

The following proposition gives several useful characterisations of h-cofibrations in left proper model categories. Left properness is essential here because formal homotopy pushouts are easier to recognise in left proper model categories than in general model categories. For instance, in a left proper model category any pushout along a cofibration is a formal homotopy pushout, which is not the case in general model categories.

A weak equivalence w in X/E is called a cofibre equivalence if for each morphism g : X → B the functor g_{!} : X/E → B/E takes w to a weak equivalence in B/E.

1.6. Proposition. In a left proper model category E, the following four properties of a morphism f : X → Y are equivalent:

(i) f is an h-cofibration;

(ii) every pushout along f is a formal homotopy pushout;

(iii) for every factorisation of f into a cofibration followed by a weak equivalence, the weak equivalence is a cofibre equivalence;

(iv) there exists a factorisation of f into a cofibration followed by a cofibre equivalence.

Proof. (i) ⟹ (ii) For a given outer pushout rectangle like in diagram (2) above with an h-cofibration f, factor the given map X → B as a cofibration X ↣ A followed by a weak equivalence w : A ⟶^{∼} B, and define Y → A′ as the pushout of X ↣ A along f. Since the right square is then a pushout, w′ : A′ → B′ is a weak equivalence, whence the outer rectangle is a formal homotopy pushout.

(ii) ⟹ (iii) The pushout

[figure: X; g; B; Y; f; B′]

is factored vertically according to a factorisation of f into a cofibration X ↣ Z followed by a weak equivalence v : Z ⟶^{∼} Y:

X \overline{g^{}}B

[figure: Z; ∨; Z′; ∨]

[figure: Y; v; B.; v′]

Since the outer rectangle is a formal homotopy pushout by assumption, v′ is a weak equivalence, whence v is a cofibre equivalence.

(iii) ⟹ (iv) This is obvious.

(iv) ⟹ (i) Consider a commutative diagram like in (2) above, and factor f into a cofibration X ↣ Z followed by a cofibre equivalence v : Z ⟶^{∼} Y. This induces the following commuting diagram of pushout squares

[figure: X; A; w; B]

[figure: Z; ∨; W; ∨; w′′; Z′; ∨]

[figure: Y; v; A′; v′′; w′; B′; v′]

in which v′′ and v′ are weak equivalences because v is a cofibre equivalence, and w′′ is a weak equivalence by left properness of E. Therefore, the 2-out-of-3 property of the class of weak equivalences implies that w′ is a weak equivalence as well, and hence f is an h-cofibration as required.

1.7. Lemma. Let E be a left proper model category.

(a) A commutative square

[figure: A; A′; B; w ∼; B′; w′]

with a left vertical weak equivalence w : A ⟶^{∼} B is a formal homotopy pushout if and only if w′ : A′ → B′ is a weak equivalence; (b) In a commutative diagram

[figure: A; B; C; A′; B′; C′]

in which the left square is a formal homotopy pushout, the right square is a formal homotopy pushout if and only if the outer rectangle is a formal homotopy pushout.

Proof. (a) Factoring A → A′ into a cofibration A ↣ A′′ followed by a weak equivalence v : A′′ ⟶^{∼} A′ and taking a pushout we get the following commutative square

[figure: A; >; A′′; v; A′; B; w; >; B′′; w′′; v′; B′; w′]

in which w′′ is a weak equivalence by left properness. Therefore, by the 2-out-of-3 property of weak equivalences, v′ is a weak equivalence (i.e. the given square is a formal homotopy pushout) if and only if w′ is a weak equivalence.

(b) Factoring A → A′ into a cofibration A ↣ A′′ followed by a weak equivalence v : A′′ ⟶^{∼} A′ and taking pushouts we get the following commutative diagram

[figure: A; B; C]

[figure: A′′; ∨; B′′; ∨; C′′; ∨]

[figure: A′; v ∼; >; B′; v′′ ∼; C′; v′]

in which v′′ is a weak equivalence because the left square above is a formal homotopy pushout. Now v′ is a weak equivalence if and only if either the right square above is a formal homotopy pushout or, equivalently, the outer rectangle above is a formal homotopy pushout.

1.8. Proposition. [cf. Proposition B.12 in [35]]– In a model category E, consider the following commutative diagram

[figure: C; A; u; B; C′; f_{γ}; A′; f_{α}; u′; B′; f_{β}]

in which f_{α}, f_{β}, f_{γ} are supposed to be weak equivalences.

Then the induced map on pushouts f_{γ} ∪_{f_{α}} f_{β} : C ∪_{A}B → C′∪_{A′} B′ is a weak equivalence provided one of the following two conditions is satisfied:

(a) all objects of the diagram are cofibrant and the maps u, u′ are cofibrations;

(b) the model category E is left proper and the maps u, u′ are h-cofibrations.

Proof. Case (a) is classical, see e.g. Goerss-Jardine [29, Lemma 9.8]. Alternatively, (a) can be deduced from (b) by the following trick: the full subcategory of E spanned by the cofibrant objects is a category of cofibrant objects in the sense of Brown and the proof of (b) holds in such categories (in which every cofibration is an h-cofibration because all objects are cofibrant).

To prove (b) let us write D = C ∪_{A} B and D′ = C′ ∪_{A′} B′. Then the induced map f_{δ} : D → D′ is part of the following commutative cube

[figure: C; D; A; u; B; f_{γ}; C′; D′; f_{δ}; A′; f_{α}; u′; B′; f_{β}]  (3)

in which top and bottom squares are formal homotopy pushouts by Proposition 1.6ii, and the left square is a formal homotopy pushout by Lemma 1.7a. It follows then from Lemma 1.7b that the right square is also a formal homotopy pushout. This implies by Lemma 1.7a that f_{δ} is a weak equivalence as required.

1.9. Corollary. In left proper model categories, formal homotopy pushouts are homotopy pushouts in the homotopical sense.

Proof. In cube (3) assume that f_{α} : A ⟶^{∼} A′ is a cofibrant replacement of A′, and define B (resp. C) by factoring A ⟶^{∼} A′ → B′ (resp. A ⟶^{∼} A′ → C′) as a cofibration A ↣ B (resp. A ↣ C) followed by a weak equivalence f_{β} : B ⟶^{∼} B′ (resp. f_{γ} : C ⟶^{∼} C′). The top square is then a formal homotopy pushout and D = B ∪_{A} C realises the homotopy colimit of the lower diagram C′ ← A′ → B′.

If the bottom square is a formal homotopy pushout then the proof of Proposition 1.8b shows that the canonical map f_{δ} : D → D′ from the homotopy pushout to the formal homotopy pushout is a weak equivalence.

A weak equivalence which is an h-cofibration will be called a trivial h-cofibration. A weak equivalence which remains a weak equivalence under any cobase change will be called couniversal. For instance, trivial cofibrations are couniversal weak equivalences.

1.10. Lemma. In general, couniversal weak equivalences are trivial h-cofibrations. In left proper model categories, the converse holds: trivial h-cofibrations are couniversal weak equivalences.

Proof. The 2-out-of-3 property of the class of weak equivalences implies that couniversal weak equivalences are trivial h-cofibrations. In a left proper model category, the pushout of a trivial h-cofibration is a trivial h-cofibration in virtue of Lemmas 1.3, 1.6ii and 1.7a.

1.11. Definition. A model category is called h-monoidal if it is a monoidal model category [37] such that for each (trivial) cofibration f : X → Y and each object Z, the tensor product f ⊗ 1_{Z} : X ⊗ Z → Y ⊗ Z is a (trivial) h-cofibration.

It is called strongly h-monoidal if moreover the class of weak equivalences is closed under tensor product.

In particular, each cofibration is an h-cofibration so that, by Lemma 1.2, h-monoidal model categories are left proper. Moreover, in virtue of Lemma 1.10, the condition on trivial cofibrations can be considered as a weak form of the monoid axiom of Schwede-Shipley [60], cf. Proposition 2.5 and Corollary 2.6 below.

1.12. Lemma. For monoidal model categories the following implications hold:

all objects cofibrant ⟹ strongly h-monoidal ⟹ h-monoidal ⟹ left proper.

Proof. For the first implication, it suffices to observe that, by a well-known argument of Rezk, if all objects are cofibrant then the model structure is left proper, i.e. (by 1.2) cofibrations are h-cofibrations. Moreover, the pushout-product axiom implies that tensoring a (trivial) cofibration with an arbitrary object yields again a (trivial) cofibration. Therefore, the model structure is h-monoidal. The class of weak equivalences is closed under tensor product, since by Brown’s Lemma (if all objects are cofibrant) each weak equivalence factors as a trivial cofibration followed by a retraction of a trivial cofibration. The other two implications are obvious.

It is in general difficult to describe explicitly the class of h-cofibrations of a model category. The following three propositions are useful since they are applicable even if such an explicit description is unavailable.

1.13. Proposition. Let E be a closed symmetric monoidal category with two model structures, called resp. injective and projective, and sharing the same class of weak equivalences. We assume that the following three properties hold:

• the projective model structure is a monoidal model structure;

• the injective model structure is left proper; • tensoring a (trivial) cofibration of the projective model structure with an arbitrary

object yields a (trivial) cofibration of the injective model structure.

Then the projective model structure is h-monoidal.

Proof. Observe that the notion of h-cofibration only depends on the class of weak equivalences, hence both model structures have the same class of h-cofibrations. The statement then follows directly from Lemma 1.2.

1.14. Proposition. Let E be a symmetric monoidal category with two monoidal model structures such that each cofibration (resp. weak equivalence, resp. fibration) of the first model structure is an h-cofibration (resp. weak equivalence, resp. fibration) of the second. If all objects of the first model structure are cofibrant then both model structures are hmonoidal.

Proof. Since all objects of the first model structure are cofibrant, the first model structure is (strongly) h-monoidal by Lemma 1.12. Since the trivial fibrations of the first structure are among the trivial fibrations of the second, the cofibrations of the second are among the cofibrations of the first. The latter class is closed under tensor product and contained in the class of h-cofibrations of the second structure. This yields the first half of hmonoidality for the second model structure. Similarly, since the fibrations of the first model structure are among the fibrations of the second, the trivial cofibrations of the second are among the trivial cofibrations of the first. The latter class is closed under tensor product and contained in the class of trivial h-cofibrations of the second model structure. This shows that the second half of h-monoidality holds for the second model structure as well.

1.15. Proposition. Let E be a monoidal model category in which all objects are fibrant. Then E is h-monoidal provided the internal hom of E detects weak equivalences in the following sense: a map f : X → Y is a weak equivalence whenever \underline{E}(f, W) is a weak equivalence for all objects W.

Proof. Let f : X → Y be a cofibration. We have to show that in

[figure: X ⊗ Z; A; w; B; Y ⊗ Z; f ⊗ Z; A′; w′; B′]

w′ is a weak equivalence if w is. For this it suffices to show that \underline{E}(w′, W) is a weak equivalence for all W, which follows from the pushout-product axiom and the hom-tensor adjunction. If f is a trivial cofibration then \underline{E}(f ⊗ Z, W) ≅ \underline{E}(f, \underline{E}(Z, W)) is a trivial fibration for each object W. Hence f ⊗ Z is a weak equivalence.

1.16. Remark. We implicitly used in the preceding proof that E is right proper because all of its objects are fibrant, and that therefore weak equivalences in E are stable under pullback along fibrations. Proposition 1.15 deduces from this and the good behaviour of the internal hom of E that E is h-monoidal and hence in particular left proper. This explicit relationship between right and left properness in monoidal model categories does not seem to have been observed before.

1.17. Corollary. The category of compactly generated topological spaces is strongly hmonoidal with respect to Strøm’s and Quillen’s cartesian model structures.

Proof. Recall that in Strøm’s model structure the weak equivalences and fibrations are homotopy equivalences and Hurewicz fibrations respectively; the corresponding classes in Quillen’s model structure are weak homotopy equivalences and Serre fibrations. These classes verify the inclusion relations required by Proposition 1.14. The cofibrations of Strøm’s model structure are the closed cofibrations (i.e. NDR-pairs) in the topologist’s classical sense. Closed cofibrations are h-cofibrations for Quillen’s model structure^{3}. In Strøm’s model structure all objects are cofibrant so that it is strongly h-monoidal by Lemma 1.12. Proposition 1.14 implies that Quillen’s model structure is h-monoidal. It is strongly h-monoidal since the product of two weak homotopy equivalences is again a weak homotopy equivalence.

1.18. Corollary. The following two examples are h-monoidal model categories:

• the category of chain complexes over a commutative ring with the projective model structure;

• the category of symmetric spectra (in simplicial sets) with the stable projective model structure.

Proof. We use in both cases Proposition 1.13. Recall that the cofibrations of the injective (resp. projective) model structure on chain complexes are the monomorphisms (resp. monomorphisms with degreewise projective quotient). In particular, a projective cofibration f_{•} : X_{•} → Y_{•} is degreewise split so that f_{•} ⊗ Z_{•} is degreewise a monomorphism, and hence a cofibration in the injective model structure. If f_{•} is trivial (i.e. a quasi-isomorphism), its degreewise projective quotient Y_{•}/X_{•} is acyclic, and hence contractible. Therefore (Y_{•}/X_{•}) ⊗ Z_{•} is contractible as well, and hence f_{•} ⊗ Z_{•} is trivial as required. The statement about symmetric spectra follows by an analogous argument from Proposition III.1.11i, Lemma III.1.4 and Theorem III.2.2 of Schwede’s book project [59].

3In order to show that weak homotopy equivalences are preserved under cobase-change along closed cofibrations, it is enough to consider weak homotopy equivalences which are closed cofibrations. In other words, for any NDR-triad (X, X_{1}, X_{2}) we have to show that if (X_{1}, X_{1} ∩ X_{2}) is ∞-connected then so is (X, X_{2}). This holds if all spaces are CW -complexes. CW -approximation reduces thus the problem to a gluing lemma for weak homotopy equivalences between NDR-triads. This follows from the analogous statement for excisive triads [20, Theorem 6.7.9] because each NDR-triad is homotopy equivalent to an excisive triad by a double mapping cylinder construction.

1.19. Examples. Below a list of frequently used monoidal model categories in which all objects are cofibrant. By Lemma 1.12 they are thus strongly h-monoidal.

• simplicial sets;

• small categories with the folklore model structure, cf. [41, 14];

• Rezk’s model for (∞, n)-categories [57];

• compactly generated spaces with Strøm’s model structure;

• chain complexes over a field with the projective model structure.

There are strongly h-monoidal model categories in which not all objects are cofibrant, e.g.

• compactly generated spaces with Quillen’s model structure, cf. Corollary 1.17;

• small 2-categories (or 2-groupoids) with the Gray tensor product, cf. Proposition 1.15 and [41, 14].

Corollary 1.18 treats two examples of h-monoidal model categories which are not strongly h-monoidal.

1.20. Resolution axiom and strong unit axiom. It can be verified by direct inspection that in the preceding examples all objects are h-cofibrant. In Proposition 1.21 below we give a sufficient criterion for this to hold. This is the only place in this article where we make explicit use of Hovey’s unit axiom [37] under a strengthened form. We are indebted to Muro for clarifying comments, who uses in [53] another strengthening of Hovey’s unit axiom, weaker than ours, but with a similar purpose.

The unit e of a monoidal model category E plays an important role. The minimal requirement for the existence of a unit in the homotopy category of E has been formulated by Hovey [37] as the so-called unit axiom: cofibrant resolutions of the unit should remain weak equivalences under tensor with cofibrant objects.

It is often the case that the following (stronger) resolution axiom holds: general cofibrant resolutions are stable under tensor with cofibrant objects. The resolution axiom implies (by 2-out-of-3) that the class of weak equivalences is stable under tensor with cofibrant objects, and actually implies (again by 2-out-of-3) that cofibrant resolutions of the unit remain weak equivalences under tensor with arbitrary objects. We call the latter property the strong unit axiom. We thus have for any monoidal model category the following chain of implications

strongly h-monoidal ⟹ resolution axiom ⟹ strong unit axiom

The reader should observe that the strong unit axiom also holds if the unit e of E is already cofibrant, in which case the following proposition has a much easier proof.

1.21. Proposition. In any h-monoidal model category, in which the strong unit axiom holds, all objects are h-cofibrant.

Proof. We shall use Lemma 1.4(i) for recognising h-cofibrant objects. The strong unit axiom requires the existence of a cofibrant resolution Q(e) → e for the unit e, which remains a weak equivalence after tensoring with arbitrary objects. For each object X of E, we thus have a weak equivalence Q(e) ⊗ (e ⊔ X) → e ⊔ X. Since the tensor commutes with coproducts, this weak equivalence can be rewritten as

Q(e) ⊔ (Q(e) ⊗ X) → Q(e) ⊔ X → e ⊔ X

where the first map is the coproduct of Q(e) with Q(e) ⊗ X → X. Therefore, since Q(e) is h-cofibrant by Lemma 1.2, the first map above is a weak equivalence. By the 2-of-3 property of weak equivalences, the second map Q(e) ⊔ X → e ⊔ X is a weak equivalence as well. But then, for each weak equivalence X → Y, the commutative diagram

[figure: Q(e) ⊔ X; Q(e) ⊔ Y; e ⊔ X; e ⊔ Y]

implies that e ⊔ X → e ⊔ Y is a weak equivalence, which shows that e is h-cofibrant.

In an h-monoidal model category we have the stronger property that Q(e) ⊗ Z is h-cofibrant for each object Z. Therefore, factoring the weak equivalence

Q(e) ⊗ (Z ⊔ X) = (Q(e) ⊗ Z) ⊔ (Q(e) ⊗ X) → Z ⊔ X

through (Q(e) ⊗ Z) ⊔ X yields a weak equivalence (Q(e) ⊗ Z) ⊔ X → Z ⊔ X for all objects Z and X. This implies as above that all objects Z are h-cofibrant.

1.22. Remark. If all objects of a (monoidal) model category are h-cofibrant then each weak equivalence factors as a trivial h-cofibration followed by a retraction of a trivial hcofibration, using the same argument as for Brown’s Lemma. In this case, the resolution axiom amounts thus to the property that tensoring a trivial h-cofibration with a cofibrant object yields a weak equivalence. In particular, the two examples of Corollary 1.18 fulfill the resolution axiom.

The following lemma is also useful to retain:

1.23. Lemma. In an h-monoidal model category, tensoring a weak equivalence between cofibrant objects with an arbitrary object yields again a weak equivalence.

Proof. By Brown’s Lemma, a weak equivalence between cofibrant objects factors as a trivial cofibration followed by a retraction of a trivial cofibration. Both factors yield a weak equivalence when tensored with an arbitrary object.

2. Admissible monads on compactly generated model categories

It is well-known that the class of (trivial) cofibrations in an arbitrary model category is closed under cobase change, transfinite composition and retract. Classes of morphisms with these three closure properties will be called saturated.

2.1. Definition. With respect to a saturated class of morphisms K in a model category E, the class W of weak equivalences of E is called K-perfect if W is closed under filtered colimits along morphisms in K.

2.2. Remark. Our terminology is borrowed from Lurie [45] who calls a class of weak equivalences perfect if it is K-perfect with respect to the saturated class K of all morphisms. By Hovey’s argument (see the proof of [37, Corollary 7.4.2] or [21, Lemma 3.5] for a more recent treatment) a sufficient condition for the K-perfectness of the class of weak equivalences is the existence of a generating set of cofibrations whose domain and codomain are finite with respect to K.

2.3. Lemma. If the class W of weak equivalences is K-perfect then the intersection W ∩K is closed under transfinite composition.

Proof. Any transfinite composition of maps can be identified with the colimit of a natural transformation from a constant diagram to the given sequence of maps. If the given maps belong to W ∩ K this colimit is a filtered colimit of weak equivalences along morphisms in K. By assumption such a colimit is a weak equivalence.

We shall say that a class of morphisms is monoidally saturated if it is saturated and moreover closed under tensoring with arbitrary objects of the monoidal model category. Accordingly, the monoidal saturation of a class K is the least monoidally saturated class containing K. For instance, in virtue of the pushout-product axiom, the class of (trivial) cofibrations of a monoidal model category is monoidally saturated whenever all objects of the model category are cofibrant.

We are mainly interested in the monoidal saturation of the class of cofibrations. This monoidal saturation will be denoted I^{⊗} since it suffices to monoidally saturate a generating set of cofibrations which traditionally is denoted I. For brevity we shall call ⊗-cofibration any morphism in I^{⊗}. An object will be called ⊗-small (resp. ⊗-finite) if it is small (resp. finite) with respect to I^{⊗}. The class of weak equivalences will be called ⊗-perfect if it is I^{⊗}-perfect.

2.4. Definition. [cf. [14]] A model category is called K-compactly generated if it is cofibrantly generated, its class of weak equivalences is K-perfect, and each object is small with respect to K.

A monoidal model category is called compactly generated, if the underlying model category is I^{⊗}-compactly generated.

For instance, any monoidal model category whose underlying model category is combinatorial, and whose class of weak equivalences is closed under filtered colimits, is an example of a compactly generated monoidal model category. The majority of our examples are of this kind. However, compactly generated topological spaces form a monoidal model category which is neither combinatorial nor does it have a class of weak equivalences which is closed under filtered colimits. Yet, every compactly generated space is ⊗-small, and the class of weak equivalences is ⊗-perfect, hence the monoidal model category of compactly generated spaces is compactly generated in the aforementioned model-theoretical sense, cf. [37, 14].

2.5. Proposition. In any compactly generated h-monoidal model category, the monoid axiom of Schwede-Shipley holds and each ⊗-cofibration is an h-cofibration.

If in addition the strong unit axiom holds (cf. Section 1.20) then the class of weak equivalences is closed under arbitrary coproducts.

Proof. The monoid axiom of Schwede-Shipley [60] requires the monoidal saturation of the class of trivial cofibrations to stay within the class of weak equivalences. In a cofibrantly generated monoidal model category this monoidal saturation can be constructed by choosing a generating set J for the trivial cofibrations, and saturating the class {f ⊗1_{Z} | f ∈ J, Z ∈ ObE} under cobase change, transfinite composition and retract. Since, by Lemma 1.10, each f ⊗ 1_{Z} is a couniversal weak equivalence and a ⊗-cofibration, and both classes are closed under cobase change and retract, it remains to be shown that the class of maps, which are simultaneously weak equivalences and ⊗-cofibrations, is closed under transfinite composition. This is precisely Lemma 2.3 for K = I^{⊗}.

For the second statement, we have to show that the monoidal saturation of the class of cofibrations stays within the class of h-cofibrations. As before, this monoidal saturation can be constructed by choosing a generating set I for the cofibrations, and saturating the class {f ⊗1_{Z} | f ∈ I, Z ∈ ObE} under cobase change, transfinite composition and retract. Since each f ⊗ 1_{Z} is an h-cofibration and a ⊗-cofibration, and both classes are closed under cobase change and retract, it remains to be shown that the class of maps, which are simultaneously h-cofibrations and ⊗-cofibrations, is closed under transfinite composition. This follows from the definition of an h-cofibration, since a vertical transfinite composition of diagrams of the form (2) (all vertical maps being h-cofibrations and ⊗-cofibrations) yields a diagram of the same form (2).

For the last statement, note first that by Proposition 1.21 all objects are h-cofibrant so that by Lemma 1.4(iii) it remains to be shown that weak equivalences are closed under filtered colimits along coproduct injections. By the strong unit axiom, a cofibrant resolution Q(e) ⟶^{∼} e of the monoidal unit e yields a resolution Q(e) ⊗ Z ⟶^{∼} Z of each object Z by a ⊗-cofibrant object Q(e) ⊗ Z. This resolution functor commutes with colimits so that each colimit can be replaced with a weakly equivalent colimit of ⊗-cofibrant objects. Any coproduct injection with respect to a ⊗-cofibrant object is a ⊗-cofibration. By compact generation weak equivalences are closed under filtered colimits along ⊗-cofibrations as required.

2.6. Corollary. In a monoidal model category with ⊗-perfect class of weak equivalences, the monoid axiom of Schwede-Shipley holds if and only if the tensor product of a trivial cofibration with an arbitrary object is a couniversal weak equivalence.

Proof. This follows from the argument of first paragraph of the preceding proof.

2.7. Remark. The preceding proposition and corollary (together with 1.13, 1.14 or 1.15) may be an efficient tool to establish the monoid axiom and left properness. For instance, Lack’s original proofs [41, Theorems 6.3 and 7.7] of these properties for the category of small 2-categories are quite a bit more involved.

2.8. Admissible monads. Recall that a monad T on E is called finitary if T preserves filtered colimits, or what amounts to the same, if the forgetful functor U_{T} : Alg_{T} → E preserves filtered colimits. Here, Alg_{T} denotes the category of T -algebras and

F_{T} : E ⇆ Alg_{T} : U_{T}

the free-forgetful adjunction. Thus T = U_{T} F_{T} and F_{T} (X) = (T X, μ_{X}) where μ : T^{2} → T is the multiplication of the monad T.

2.9. Definition. Let E be a model category, W its class of weak equivalences, and K be an arbitrary saturated class in E. A monad T on E is said to be K-admissible if for each cofibration (resp. trivial cofibration) u : X → Y and each map of T -algebras α : F_{T} (X) → R, the pushout in Alg_{T}

[figure: F_{T} (X); α; R; F_{T} (Y); F_{T} (u); R[u, α]; u_{α}]  (4)

yields a T -algebra map u_{α} : R → R[u, α] whose underlying map U_{T} (u_{α}) belongs to K (resp. to W ∩ K).

For all the sequel a weak equivalence f : R → S of T -algebras means a map of T - algebras such that the underlying map U_{T} (f) : U_{T} (R) → U_{T} (S) is a weak equivalence in E. A T -algebra R will be called U_{T} -cofibrant if the underlying object U_{T} (R) is cofibrant in E.

Note that the notion of h-cofibration (cf. Definition 1.1) makes sense for any category with pushouts and a specified class of weak equivalences. Accordingly, a map of free T -algebras F_{T} (u) : F_{T} (X) → F_{T} (Y) will be called an h-cofibration if for any diagram of pushouts of T -algebras

[figure: F_{T} (X); α; R; f; S; F_{T} (Y); F_{T} (u); R[u, α]; S[u, fα]]  (5)

in which f : R → S is a weak equivalence, the induced map R[u, α] → S[u, fα] is again a weak equivalence. We shall say that F_{T} (u) is a relative h-cofibration if (*) for any weak equivalence f : R → S between U_{T} -cofibrant T -algebras and any

α : F_{T} (X) → R, the induced map R[u, α] → S[u, fα] is again a weak equivalence between U_{T} -cofibrant T -algebras.

If all objects of E are cofibrant, any h-cofibration F_{T} (u) is a relative h-cofibration. In general there might be h-cofibrations which are not relative h-cofibrations.

2.10. Definition. A model structure on T -algebras will be called relatively left proper if for any weak equivalence f : R → S between U_{T} -cofibrant T -algebras and any cofibration R → R′ of T -algebras, cobase change along the latter yields a weak equivalence R′ → R′ ∪_{R} S between U_{T} -cofibrant T -algebras.

Again, if all objects of E are cofibrant, then a left proper model structure on Alg_{T} is automatically relatively left proper. In general however this might be wrong.

2.11. Theorem. For any finitary K-admissible monad T on a K-compactly generated model category E, the category of T -algebras admits a transferred model structure. This model structure is (relatively) left proper if and only if the free T -algebra functor takes cofibrations in E to (relative) h-cofibrations in Alg_{T}.

Proof. By definition of a transfer, a map of T -algebras f is defined to be a weak equivalence (resp. fibration) precisely when U_{T} (f) is a weak equivalence (resp. fibration) in E. Cofibrations of T -algebras are defined by the left lifting property with respect to trivial fibrations. In order to show that these three classes define a model structure on Alg_{T}, the main difficulty consists in proving the existence of cofibration/trivial fibration (resp. trivial cofibration/fibration) factorisations. For this we apply Quillen’s small object argument to the image F_{T} (I) (resp. F_{T} (J)) of a generating set I (resp. J) for the cofibrations (resp. trivial cofibrations) of E. The following two points have to be shown:

(i) The domains of the maps in F_{T} (I) (resp. F_{T} (J)) are small with respect to the saturation of F_{T} (I) (resp. F_{T} (J)) under cobase change and transfinite composition in Alg_{T};

(ii) The saturation of F_{T} (J) under cobase change and transfinite composition in Alg_{T} stays within the class of weak equivalences.

Since the forgetful functor U_{T} preserves filtered colimits, an adjunction argument and the K-smallness of the objects of E yield (i). Moreover, Lemma 2.3 and the K-perfectness of the weak equivalences in E yield (ii).

If the transferred model structure on Alg_{T} is (relatively) left proper then the left Quillen functor F_{T} takes cofibrations in E to (relative) h-cofibrations in Alg_{T} by Lemma 1.2. Conversely, assume that F_{T} (u) is a (relative) h-cofibration for each generating cofibration u. Note first that the forgetful functor U_{T} preserves transfinite compositions since it preserves filtered colimits. It follows then from the K-perfectness of the class of weak equivalences and the K-admissibility of T that cobase change along a transfinite composition of free T -algebra extensions of the form R → R[u, α] preserves weak equivalences (between U_{T} -cofibrant T -algebras). But any cofibration in Alg_{T} is retract of such a transfinite composition. Thus, Alg_{T} is (relatively) left proper.

The reader should observe that in the relatively left proper case, we need the full condition (*) of a relative h-cofibration in order to ensure that, at each step of the transfinite composition, the underlying objects are cofibrant.

2.12. Proposition. The free T -algebra functor takes cofibrations to relative h-cofibrations if it takes cofibrations with cofibrant domain to relative h-cofibrations.

Proof. Suppose that u : X → Y is a cofibration. We have to show that for a weak equivalence f : R → S between U_{T} -cofibrant T -algebras, the morphism R[u, α] → S[u, fα] in the diagram (5) is a weak equivalence. Let α′ : X → U_{T} (R) be the composite

X →^{ϵ} U_{T} F_{T} (X) →^{U_{T} (α)} U_{T} (R)

and consider the following pushout in E :

[figure: X; α′; U_{T} (R); Y; u; P; v]

The given map α factors as

F_{T} (X) →^{F_{T} (α′)} F_{T} U_{T} (R) →^{k} R

where k is the structure map of the T -algebra R. Therefore, by the universal property of pushouts, the right-hand square of the following commutative diagram

[figure: F_{T} (X); F_{T} (α′); F_{T} U_{T} (R); k; R; F_{T} (Y); F_{T} (u); F_{T} (P); R[u, α]]

is a pushout. Hence, we get the following pushout diagram in Alg_{T} :

[figure: F_{T} U_{T} (R); k; R; f; S; F_{T} (P); F_{T} (v); R[u, α]; S[u, fα]]

Since v is a cofibration with cofibrant domain, F_{T} (v) is a relative h-cofibration by assumption, so that R[u, α] → S[u, fα] is a weak equivalence as required.

2.13. Definition. A monad T is K-adequate if the underlying map of any free T -algebra extension u_{α} : R → R[u, α] admits a functorial factorisation

U_{T} (R) = R[u]^{(0)} → R[u]^{(1)} → … → R[u]^{(n)} → … → colim_{n}R[u]^{(n)} = U_{T} (R[u, α]);

such that for a (trivial) cofibration u, each map of the sequence belongs to K (resp. W ∩K), and for a weak equivalence f : R → S, the induced morphisms R[u]^{(n)} → S[u]^{(n)} are weak equivalences for all n ≥ 0.

A monad T is relatively K-adequate if the second condition only holds for cofibrations u with cofibrant domain and for weak equivalences f : R → S between U_{T} -cofibrant T - algebras, and the individual maps of the horizontal sequences are cofibrations.

2.14. Theorem. Any finitary (relatively) K-adequate monad T on a K-compactly generated model category E is K-admissible, and the associated free T -algebra functor takes cofibrations to (relative) h-cofibrations. Hence, the category of T -algebras has a transferred model structure which is (relatively) left proper.

Proof. The second statement follows from the first and from Theorem 2.11.

That a K-adequate monad is K-admissible follows from the saturation of K and from Lemma 2.3. Moreover, given a cofibration u : X → Y and a weak equivalence f : R → S of T -algebras, the underlying map of morphism R[u, α] → S[u, fα] of diagram (5) is a sequential colimit of a ladder in E

[figure: R[u]^{(0)}; R[u]^{(1)}; ⋯; R[u]^{(n)}; ⋯; colim_{n}R[u]^{(n)}; = U_{T} (R[u, α])]

[figure: S[u]^{(0)}; S[u]^{(1)}; ⋯; S[u]^{(n)}; ⋯; colim_{n}S[u]^{(n)}; = U_{T} (S[u, fα])]

in which the vertical maps are weak equivalences and the horizontal maps belong to K. Since E is K-compactly generated this colimit is a weak equivalence. This shows that the free T -algebra functor takes cofibrations to h-cofibrations.

For the relative version, K-admissibility is proved as before. For the relative hcofibration property of F_{T} (u) we can assume, according to Proposition 2.12, that u has a cofibrant domain. Then, by assumption, the horizontal maps of the diagram above are cofibrations so that their composite is a cofibration as well, whence U_{T} (R[u, α]) is cofibrant, given that R is U_{T} -cofibrant by assumption. Moreover, the colimit of the ladder is a weak equivalence by the same argument as before (or by invoking a Reedy telescope lemma). Therefore, F_{T} (u) is a relative h-cofibration.

3. Monoids in h-monoidal model categories

This section presents the main result of Schwede-Shipley [60] concerning the existence of a model structure on monoids if the monoid axiom holds. We add a discussion of left properness of the transferred model structure, cf. Muro [53].

Recall that I^{⊗} denotes the monoidal saturation of the class of cofibrations, and that any morphism in I^{⊗} is called a ⊗-cofibration. Accordingly, we say ⊗-admissible (resp. ⊗-adequate) instead of I^{⊗}-admissible (resp. I^{⊗}-adequate).

3.1. Theorem. For any compactly generated monoidal model category E the free monoid monad T on E is :

(a) relatively ⊗-adequate if the monoid axiom holds;

(b) ⊗-adequate if E is strongly h-monoidal.

And hence

(a′) there is a relatively left proper transferred model structure on monoids if the monoid axiom holds;

(b′) the model structure on monoids is left proper if E is strongly h-monoidal.

Proof. (a′), (b′) follow from (a), (b) and Theorem 2.14.

Let R be a monoid in E, and let u : Y_{0} → Y_{1} be a map in E equipped with a map of monoids F_{T} (Y_{0}) → R. We shall exhibit the pushout in the category of monoids as a sequential colimit in E.

Let R[u]^{(0)} = R and define inductively R[u]^{(n)} by the following pushout

[figure: Y_{−}^{(n)}; R[u]^{(n−1)}; Y^{(n)}; R[u]^{(n)}]  (6)

where

Y^{(n)} = R ⊗ \overbrace{Y_{1} ⊗ R ⊗ ⋯ ⊗ Y_{1} ⊗ R}^{n}

and Y_{−}^{(n)} is the colimit of a diagram over a punctured n-cube {0, 1}^{n} − {(1, …, 1)} in which the vertex (i_{1}, …, i_{n}) takes the value

R ⊗ Y_{i_{1}} ⊗ ⋯ ⊗ R ⊗ Y_{i_{n}} ⊗ R

and the edge-maps are induced by u. The map Y_{−}^{(n)} → Y^{(n)} is the comparison map from the colimit of this diagram to the value at (1, …, 1) of the extended diagram on the whole n-cube. The map Y_{−}^{(n)} → R[u]^{(n−1)} is defined inductively, using the fact that the construction of R[u]^{(n−1)} involves n − 1 tensor factors only.

Since the tensor − ⊗ − commutes with pushouts in both variables, there are canonical maps of R[u]^{(p)} ⊗ R[u]^{(q)} → R[u]^{(p+q)}. Since the tensor − ⊗ − commutes with sequential colimits in both variables, these maps induce the structure of a monoid on the colimit colim_{n}R[u]^{(n)}. A proof that this monoid has indeed the universal property of R[u] has been sketched in [60]. We obtain in Theorem 7.11 below a far-reaching generalisation of this result.

We shall now prove that, for each n > 0, the map R[u]^{(n−1)} → R[u]^{(n)} is a (trivial) ⊗- cofibration whenever u is a (trivial) cofibration. The considered map derives from Y_{−}^{(n)} → Y^{(n)} through a cobase change. Collecting all tensor factors R, the map Y_{−}^{(n)} → Y^{(n)} may be identified with an iterated pushout-product map along u, tensored with R^{⊗n+1}. Therefore, Y_{−}^{(n)} → Y^{(n)} is a ⊗-cofibration and its cobase change R[u]^{(n−1)} → R[u]^{(n)} as well. If u is a trivial cofibration, the iterated pushout-product map is a trivial cofibration, and its tensor product with R^{⊗n+1} is a couniversal weak equivalence by the monoid axiom; thus R[u]^{(n−1)} → R[u]^{(n)} is a trivial ⊗-cofibration. This proves that the free monoid monad is ⊗-admissible.

For the proof of (a) we consider for each n > 0, the following commutative cube in E

[figure: Z_{−}^{(n)}; S[u]^{(n−1)}; Y_{−}^{(n)}; R[u]^{(n−1)}; Z^{(n)}; S[u]^{(n)}; Y^{(n)}; R[u]^{(n)}]  (7)

in which Z_{−}^{(n)} → Z^{(n)} is defined like Y_{−}^{(n)} → Y^{(n)} just replacing R with S, and where we assume that U_{T} (R) and U_{T} (S) are cofibrant, and that u has a cofibrant domain.

Front and back square of the cube are pushouts; in particular the right vertical maps are cofibrations since the left vertical maps are so by the pushout-product axiom. The natural transformation from front to back square is induced by tensor powers of f : R → S. By induction, it suffices now to show that R[u]^{(n)} → S[u]^{(n)} is a weak equivalence whenever R[u]^{(n−1)} → S[u]^{(n−1)} is. Indeed, all objects of the cube (7) are cofibrant, the two left vertical maps are cofibrations, and the two left horizontal maps are weak equivalences. Proposition 1.8a implies then that R[u]^{(n)} → S[u]^{(n)} is a weak equivalence as required.

For the proof of (b) we consider the same cube assuming that E is strongly h-monoidal and that f : R → S is a weak equivalence of monoids. We have seen that Y_{−}^{(n)} → Y^{(n)} and Z_{−}^{(n)} → Z^{(n)} are ⊗-cofibrations and hence h-cofibrations by Proposition 2.5.

Since E is strongly h-monoidal, the tensor power f^{⊗n+1} : R^{⊗n+1} → S^{⊗n+1} is again a weak equivalence. Hence, for any vertex (i_{1}, …, i_{n}) of the n-cube, the map

R ⊗ Y_{i_{1}} ⊗ ⋯ ⊗ R ⊗ Y_{i_{n}} ⊗ R → S ⊗ Y_{i_{1}} ⊗ ⋯ ⊗ S ⊗ Y_{i_{n}} ⊗ S  (8)

is a weak equivalence. Recollecting the tensor factors as above shows that the maps Y^{(n)} → Z^{(n)} and Y_{−}^{(n)} → Z_{−}^{(n)} are weak equivalences. Proposition 1.8b implies then that if R[u]^{(n−1)} → S[u]^{(n−1)} is a weak equivalence then so is R[u]^{(n)} → S[u]^{(n)}.

4. Diagram categories and Day convolution

As a first application of our methods we observe that the class of compactly generated (strongly) h-monoidal categories E is closed under taking diagram categories over a small E-enriched category ℂ. More precisely, let E be a monoidal model category and ℂ be a small E-enriched category. Let [ℂ, E] be the category of E-enriched functors and E-natural transformations. Let ℂ_{0} be the set of objects of ℂ, considered as a discrete E-category. We have an inclusion E-functor i : ℂ_{0} → ℂ. The category [ℂ_{0}, E] ≅ E^{ℂ_{0}} has an obvious product model structure.

There is a monad i^{∗}i_{!} on [ℂ_{0}, E] where i^{∗} denotes the restriction functor and i_{!} its left adjoint. The restriction functor i^{∗} is monadic, and the projective model structure on [ℂ, E] is by definition the model structure which is transferred from [ℂ_{0}, E] along the adjunction i_{!} : [ℂ_{0}, E] ⇆ [ℂ, E] : i^{∗} if such a transfer exists.

We shall call an object of E discrete if it is a coproduct of copies of the unit of E. Clearly, any tensor product of discrete objects is again discrete.

4.1. Theorem. Let E be a compactly generated monoidal model category, and let ℂ be a small E-enriched category. Then the projective model structure on [ℂ, E] exists in each of the following three cases:

(i) all hom-objects of ℂ are discrete in E;

(ii) all hom-objects of ℂ are cofibrant in E;

(iii) the monoid axiom holds in E.

The projective model structure on [ℂ, E] is left proper if either E is h-monoidal (and hence (iii) holds), or if E is just left proper, but (i) or (ii) holds. If moreover ℂ is equipped with a symmetric monoidal structure, then [ℂ, E] is a compactly generated monoidal model category with respect to Day’s convolution product, and

(a) the monoid axiom holds in [ℂ, E] whenever it holds in E;

(b) [ℂ, E] is (strongly) h-monoidal whenever E is (strongly) h-monoidal;

(c) all objects in [ℂ, E] are h-cofibrant whenever all objects in E are h-cofibrant.

Proof. The existence and left properness of the projective model structure on [ℂ, E] follows from Theorem 2.11 if we prove that the monad i^{∗}i_{!} is K-admissible, where K is the class of pointwise ⊗-cofibrations. Note that the class of weak equivalences in [ℂ_{0}, E] is K-perfect. Moreover, all objects of [ℂ_{0}, E] are K-small, so that [ℂ_{0}, E] is a K-compactly generated model category. Note also that the monad i^{∗}i_{!} is finitary because the right adjoint i^{∗} is left adjoint as well and thus preserves all colimits.

Now, for any object X of [ℂ_{0}, E], we have (i_{!}X)(a) = ⊔_{b∈ℂ_{0}}ℂ(b, a)⊗X(b). Let u : X → Y be a morphism in [ℂ_{0}, E] and let α : i_{!}X → R be a morphism in [ℂ, E]. This defines for each a ∈ ℂ_{0} the following pushout

[figure: ∐_{b∈ℂ} ℂ(b, a) ⊗ X(b); α; R(a); ∐_{b∈ℂ} ℂ(b, a) ⊗ Y (b); R[u, α](a); u]

in E. For the K-admissibility of i^{∗}i_{!} we have to show that the right vertical map is a ⊗-cofibration (resp. weak equivalence) if u : X → Y is a cofibration (resp. trivial cofibration). This is obviously the case under assumptions (i) and (ii). For case (iii), note first that a pushout u : R(a) → R[u, α](a) like above can be realised as a transfinite composition of pushouts of single maps ℂ(b, a) ⊗ X(b) → ℂ(b, a) ⊗ Y (b). For any cofibration u, such a pushout is a ⊗-cofibration, and hence a transfinite composition of them is again a ⊗-cofibration. For a trivial cofibration u, the analogous transfinite composition belongs to the monoidal saturation of the class of trivial cofibrations, and is therefore a weak equivalence under assumption (iii).

If E is left proper and ℂ satisfies (i) or (ii) then the left vertical map above is a cofibration, and left properness of E implies left properness of [ℂ, E]. Under assumption (iii) and assuming that E is h-monoidal, Proposition 2.5 shows that the left vertical map above is an h-cofibration which implies left properness of [ℂ, E].

From now on we assume that ℂ is a symmetric monoidal category with tensor

⊙ : ℂ ⊗ ℂ → ℂ

and we endow [ℂ, E] with the Day convolution product. There is an external tensor product ¯⊗ : [ℂ, E] ⊗ [ℂ, E] → [ℂ ⊗ ℂ, E] which is a Quillen functor of two variables with respect to the projective model structures on both sides, cf. Barwick [4]. Left Kan extension along the tensor ⊙ : ℂ ⊗ ℂ → ℂ also yields a left Quillen functor ⊙_{!} : [ℂ ⊗ ℂ, E] → [ℂ, E]. Therefore, the composite functor

[figure: − − : [ℂ, E] ⊗ [ℂ, E]; ¯⊗; [ℂ ⊗ ℂ, E]; ⊙_{!}; [ℂ, E]]

which may be identified with the Day convolution product, is a left Quillen functor of two variables, hence [ℂ, E] satisfies the pushout-product axiom. The unit axiom for [ℂ, E] follows from the unit axiom for E.

For the compact generation of [ℂ, E], note first that the projective model structure on [ℂ, E] is K-compactly generated for the saturated class K of pointwise ⊗-cofibrations, since the weak equivalences of [ℂ, E] are pointwise weak equivalences, and colimits in [ℂ, E] are computed pointwise. Therefore, it suffices to show that each generating cofibration of [ℂ, E] belongs to K, and that K is stable under Day convolution − Z with an arbitrary object Z. The aforementioned formula for the left adjoint i_{!} shows that i_{!} takes cofibrations in [ℂ_{0}, E] to pointwise ⊗-cofibrations in [ℂ, E]. Observe furthermore that X Z is a pointwise retract of (i_{!}i^{∗}X) (i_{!}i^{∗}Z), and hence f Z is a pointwise retract of (i_{!}i^{∗}f) (i_{!}i^{∗}Z) for any map f : X → Y in [ℂ, E]. The latter morphism evaluated at c ∈ ℂ_{0} is given by

∐_{a,b} ℂ(a ⊙ b, c) ⊗ X(a) ⊗ Z(b) → ∐_{a,b} ℂ(a ⊙ b, c) ⊗ Y (a) ⊗ Z(b)  (9)

which is a ⊗-cofibration whenever f : X → Y is a pointwise ⊗-cofibration. Hence, the pointwise retract f Z is also a pointwise ⊗-cofibration, as required.

For statement (a), it will now be enough to apply Corollary 2.6 and to show that for a trivial cofibration f : X → Y, we get a couniversal weak equivalence f Z : X Z → Y Z in [ℂ, E]. For this, observe that like before f Z is a pointwise retract of (i_{!}i^{∗}f) (i_{!}i^{∗}Z). The latter evaluated at c ∈ ℂ_{0} is given by coproduct (9) above. Since the monoid axiom holds in E, each component of this coproduct is as well a couniversal weak equivalence as well a ⊗-cofibration. Writing this coproduct as a transfinite composition of pushouts of its components shows (in virtue of Lemma 2.3) that the coproduct itself is a couniversal weak equivalence. Since couniversal weak equivalences in [ℂ, E] are pointwise couniversal weak equivalences and since they are closed under retract, f Z is indeed a couniversal weak equivalence.

For statement (b), observe first that since colimits in [ℂ, E] are computed pointwise, and since the weak equivalences in [ℂ, E] are the pointwise weak equivalences, the hcofibrations in [ℂ, E] are precisely the pointwise h-cofibrations. Therefore, a similar argument as above (based on Proposition 2.5) yields (b). Statement (c) follows easily from Lemma 1.4ii.

4.2. Remark. This theorem recovers and strengthens Theorem 4.4 and Corollary 4.8 of Dundas-Østvær-Röndigs [21]. We do not talk about right properness here but right properness is preserved under any transfer.

If E possesses a sufficiently nice system of spheres (with symmetries) then the formalism of [21] enables one to define (symmetric) spectra in E, as ℂ-enriched functors on a certain E-enriched category ℂ which satisfies assumption (ii) above. Therefore, there exists a levelwise projective model structure on (symmetric) spectra in any compactly generated monoidal model category E with nice system of spheres (with symmetries). This projective model structure is thus h-monoidal whenever E is. In this special case, h-monoidality could also be derived from Proposition 1.13, since there is a suitable injective model structure on (symmetric) spectra witnessing the fact that ℂ is a (generalised) E-enriched Reedy category.

4.3. Remark. Any one-object E-enriched symmetric monoidal category ℂ can be viewed as a commutative monoid in E and vice-versa. In this case, the diagram category [ℂ, E] (equipped with the Day convolution product) may be identified with the category of ℂmodules (equipped with the usual tensor product of ℂ-modules). Theorem 4.1 for this special case recovers one of the results of Schwede-Shipley [60].

Part II

Algebras over tame polynomial monads

In this second part we study algebras over polynomial monads and show that the techniques of Part 1 are applicable to them. Polynomial monads are intermediate between non-symmetric and symmetric coloured operads. They have remarkable properties which among others allow a thorough combinatorial analysis of free algebra extensions. Beside the prototypical example of the free monoid monad, most of the currently used notions of operads are expressible as algebras over polynomial monads. Part 3 treats these examples in more detail. The reader may wish to go forth and back between Parts 2 and 3 so as to have concrete examples at hand.

The main new result of this second part is a combinatorial condition under which a polynomial monad is relatively ⊗-adequate (resp. ⊗-adequate) whenever the ambient compactly generated monoidal model category is h-monoidal (resp. strongly h-monoidal). In particular we get a (relatively) left proper model structure on the algebras over this monad. Polynomial monads which satisfy this condition will be called tame. At the end of this second part we study the Quillen adjunction induced by a cartesian morphism of tame polynomial monads, and describe the total left derived functor of such an adjunction as a homotopy colimit.

There are other techniques for establishing the existence of a transferred model structure on algebras. One of the most popular and powerful methods, applicable to algebras over symmetric operads, goes back to a joint paper of the second author and Ieke Moerdijk [11]. This method was generalised further in [13, 22, 32]. Since polynomial monads can be considered as a particular kind of coloured symmetric operad, it follows that under the Berger-Moerdijk conditions (the existence in E of a cocommutative interval and of a symmetric monoidal fibrant replacement functor), the category of algebras over any polynomial monad admits a transferred model structure. This is in particular the case for the category of chain complexes over a field of characteristic 0, or the categories of simplicial sets, resp. compactly generated topological spaces.

These conditions are however not satisfied in all cases of interest, nor do they provide a clue for approaching the problem of left properness of transferred model structures. It makes therefore sense to consider the smaller class of tame polynomial monads for which a transfer exists under less restrictive conditions on E, and for which the transferred model structures are at least relatively left proper.

5. Cartesian monads and their internal algebra classifiers

In this section we recall the theory of internal algebra classifiers of the first author [6] including its recent developments (cf. [66, 67]). This tool is fundamental for us because it enables us (cf. Section 7) to replace free algebra extensions with left Kan extensions which are easier to handle. We formulate the theory for general cartesian monads, though later on we shall only apply it to polynomial monads.

The reader less familiar with 2-category theory can skip the 2-categorical Definitions 5.3 and 5.9, and take Theorems 5.4 and 5.10 as definitions. Indeed, as far as cartesian monads are concerned, the theory of internal algebra classifiers can be considered as a 2-categorical characterisation of the well-known simplicial bar resolution (cf. [49]), the internal algebra classifier being a categorified version of it.

It should however be observed that the whole theory applies to arbitrary 2-monads and yields here internal algebra classifiers which in general are not anymore categorified bar resolutions (cf. [66, 67]).

5.1. Internal categories and their simplicial nerves. –

Let ℂ be a category with pullbacks. An internal category C in ℂ is a reflexive graph C_{1} [figure] C_{0} equipped with a unitary and associative multiplication m : C_{1} ×_{C_{0}} C_{1} → C_{1}. This data assembles into a 2-truncated simplicial object

[figure: C_{0}; s; t; i; C_{1} ×_{C_{0}} C_{1}; pr_{2}; pr_{1}; m; C_{1}]

enjoying the additional property that the following square

[figure: C_{1} ×_{C_{0}} C_{1} ×_{C_{0}} C_{1}; id_{C_{1}} ×_{C_{0}} m; C_{1} ×_{C_{0}} C_{1}; C_{1} ×_{C_{0}} C_{1}; m ×_{C_{0}} id_{C_{1}}; m; C_{1}; m]

commutes. An internal functor between internal categories is a natural transformation of the associated 2-truncated simplicial objects. Internal categories and internal functors form a category, denoted Cat(ℂ). Each internal category C extends to a simplicial object C_{•} in ℂ, the so-called nerve of C, by

C_{n} = \overbrace{C_{1} ×_{C_{0}} ⋯ ×_{C_{0}} C_{1}}^{n}, n ≥ 0,

with obvious simplicial operators. The nerve functor (−)_{•} : Cat(ℂ) → ℂ^{Δ^{op}} is fully faithful and its essential image consists of those simplicial objects C_{•} of ℂ for which the Segal maps

C_{n} ⟶ \overbrace{C_{1} ×_{C_{0}} ⋯ ×_{C_{0}} C_{1}}^{n}, n ≥ 0,

are invertible. A simplicial object with invertible Segal maps will be called a strict Segal object. The nerve functor induces thus an equivalence of categories between internal categories and strict Segal objects. Accordingly, the 2-truncation of a strict Segal object will be called its underlying internal category.

Each internal category C possesses an internal arrow category Arr(C) with Arr(C)_{0} = C_{1} and Arr(C)_{1} = C_{2} ×_{C_{1}} C_{2}. The latter object represents “commuting squares” in C so that “projecting in one direction” yields the structural source/target maps Arr(C)_{1} ⇉ Arr(C)_{0} while “projecting in the other direction” yields two internal functors s_{C}, t_{C} : Arr(C) ⇉ C. For two internal functors f, g : C ⇉ D, an internal natural transformation ϕ : f ⇒ g is given by an internal functor ϕ : C → Arr(D) such that f = s_{D}ϕ and g = t_{D}ϕ.

Internal categories, internal functors and internal natural transformations form a 2category, still denoted Cat(ℂ). For ℂ = Set we obtain the familiar 2-category Cat = Cat(Set) of small categories, functors and natural transformations.

5.2. Strict and lax morphisms of categorical T -algebras. –

A natural transformation is called cartesian if all naturality squares are pullbacks. A monad T = (T, μ, η) on a category ℂ with pullbacks is called cartesian if T preserves pullbacks, and as well the multiplication μ : T^{2} ⇒ T as well the unit η : id_{ℂ} ⇒ T of the monad are cartesian natural transformations.

Let T be a cartesian monad on a finitely complete category ℂ. Since T preserves pullbacks it induces a monad on the category Cat(ℂ) of internal categories. Algebras for this extended monad (also denoted T) are called categorical T -algebras. As usual, categorical T -algebras can either be considered as T -algebras in internal categories, or as internal categories in T -algebras. According to the preceding subsection a categorical T - algebra can thus also be viewed as a strict Segal object in T -algebras. For instance, since the multiplication of T is cartesian, any T -algebra (X, ξ_{X} : T (X) → X) has a simplicial bar resolution B_{•}(T, T, X) = T^{•+1}(X) which is such a strict Segal object in T -algebras, cf. the proof of Theorem 5.4.

The monad T on Cat(ℂ) takes an internal natural transformation ϕ : f ⇒ g to an internal natural transformation T (ϕ) : T (f) ⇒ T (g). Such a monad on a 2-category gives rise to a so-called 2-monad. This allows the definition of two different notions of morphisms of categorical T -algebras. Beside the classical strict morphisms there are also the lax morphisms, cf. [42, 66]. Let (A, ξ_{A}), (B, ξ_{B}) be categorical T -algebras. A lax morphism (A, ξ_{A}) → (B, ξ_{B}) is given by a pair (f, ϕ) consisting of an internal functor f : A → B and an internal natural transformation

T (A) A T (B) B ϕ T (f) f ξ_{A} ξ_{B}

such that the following conditions hold:

T (A) A T (B) B ξ_{A} ξ_{B} ϕ T (f) f A B f η_{A} η_{B} = A B f A B f id_{A} id_{B}

and

T (A) A T (B) B ξ_{A} ξ_{B} μ_{B} ϕ T (f) f ξ_{B} T^{2}(f) T^{2}(A) T^{2}(B) T (B) μ_{B} μ_{A} = T (A) A T (A) B ϕ f μ_{A} ξ_{A} T (f) ξ_{A} μ_{B} μ_{A} T^{2}(A) T^{2}(B) T (B) ξ_{B} T^{2}(f) T (ϕ)

A T -natural transformation between two lax morphisms (f, ϕ), (g, ψ) : A ⇉ B is given by an internal natural transformation ρ : f ⇒ g such that

ξ_{A} ξ_{B} T (A) A T (B) B ψ T (f) g T (ρ) T (g) = T (A) A T (B) B T (f) g ξ_{A} ξ_{B} ρ fϕ

For a cartesian monad T on a category ℂ with pullbacks, categorical T -algebras, strict morphisms of categorical T -algebras and T -natural transformations form a 2-category which we shall denote Alg_{T} (Cat(ℂ)) or Cat(Alg_{T} (ℂ)).

If ℂ has a terminal object 1 and hence is finitely complete then Cat(ℂ) as well has a terminal object and is finitely complete. An internal category C is terminal if and only if C_{0} and C_{1} are terminal. A terminal internal category has a unique T -algebra structure; the latter promotes it to a terminal categorical T -algebra. All terminal objects will be denoted 1 hoping that this will cause no confusion.

5.3. Definition. [6] Let A be a categorical T -algebra for a cartesian monad T.

An internal T -algebra in A is a lax morphism of categorical T -algebras from the terminal categorical T -algebra to A.

Internal T -algebras in A and T -natural transformations form a category Int_{T} (A) and this construction extends to a 2-functor Int_{T} : Alg_{T} (Cat(ℂ)) → Cat.

5.4. Theorem. [6] The 2-functor Int_{T} is representable. The representing categorical T -algebra T^{T} in Alg_{T} (Cat(ℂ)) is the underlying internal category

[figure: T (1); T^{2}(1); T^{3}(1)]  (10)

of the simplicial bar resolution B_{•}(T, T, 1) of the terminal T -algebra in Alg_{T} (ℂ).

This categorical T -algebra T^{T} will be called the internal algebra classifier of T because morphisms of categorical T -algebras T^{T} → A correspond one-to-one to lax morphisms of categorical T -algebras 1 → A, i.e. to internal T -algebras in A.

Proof. The free-forgetful adjunction F_{T} : ℂ ⇆ Alg_{T} (ℂ) : U_{T} induces a simplicial bar resolution B_{•}(T, T, 1) of the terminal T -algebra 1 in Alg_{T} (ℂ). Explicitly, B_{•}(T, T, 1) = T^{•+1}(1) with the usual simplicial operators, induced by multiplication and unit of T.

Since T has a cartesian multiplication, the following naturality square (where ! : T (1) → 1 denotes the unique T -algebra structure of 1)

[figure: T^{3}(1); T^{2}(!); T^{2}(1); T^{2}(1); μ_{T (1)}; T (!); T (1); μ_{1}]

is a pullback in Alg_{T} (ℂ), and hence the Segal map T^{3}(1) → T^{2}(1)×_{T (1)} T^{2}(1) is invertible. Notice that this pullback square realises the identity of simplicial face operations ∂^{0}∂^{2} = ∂^{1}∂^{1} : B_{2}(T, T, 1) → B_{0}(T, T, 1). Similarly, the cartesianness of μ : T^{2} ⇒ T implies that the identity of simplicial face operations ∂^{0}∂^{n} = ∂^{n−1}∂^{0} : B_{n}(T, T, 1) → B_{n−2}(T, T, 1) is realised by a pullback square in Alg_{T} (ℂ). It follows then by induction on n that all higher Segal maps

B_{n}(T, T, 1) ⟶ \overbrace{B_{1}(T, T, 1) ×_{B_{0}(T,T,1)} ⋯ ×_{B_{0}(T,T,1)} B_{1}(T, T, 1)}^{n}

are invertible, so that (10) is the 2-truncation of a strict Segal object in T -algebras, and therefore represents indeed a categorical T -algebra T^{T}.

It remains to be shown that T^{T} has the asserted universal property, namely that the category of strict morphisms T^{T} → A is canonically isomorphic to the category of lax morphisms 1 → A. Our proof closely follows Lack [42, Section 2].

A lax morphism of categorical T -algebras 1 → A consists of an internal functor a : 1 → A together with an internal natural transformation ϕ from T (1) →^{T (a)} T (A) →^{ξ_{A}} A to T (1) → 1 →^{a} A fulfilling coherence conditions. Now, the existence of the 1-cell a : 1 → A

in Cat(ℂ) amounts to the existence of the 1-cell ā : T (1) →^{T (a)} T (A) →^{ξ_{A}} A in Alg_{T} (Cat(ℂ)). Moreover, the existence of the 2-cell ϕ in Cat(ℂ) amounts to the existence of the 2-cell ϕ̄ = ξ_{A} · T (ϕ) in Alg_{T} (Cat(ℂ)).

It can be checked that the coherence conditions of a lax morphism 1 → A translate under this correspondence into the coherence conditions of a morphism of categorical T - algebras (ā, ϕ̄, ϕ̄ ×ā ϕ̄) : T^{T} → A. This correspondence respects the category structures on both sides and is 2-functorial in A, see [42] for details.

5.5. Example. The previous theorem applies to the free monoid monad T which is a cartesian monad on Set. In this case, categorical T -algebras are strict monoidal small categories. Bénabou [10] noticed that a lax monoidal functor from the terminal monoidal category to a monoidal category A is the same as a monoid in A. The category of internal T -algebras in A is thus the category of monoids in A.

On the other hand, the internal algebra classifier T^{T} is easily identified with a skeleton of the category of finite ordinals and order-preserving maps, also known as the augmented simplex category Δ_{+}. This is a strict monoidal category with unit the empty ordinal, and tensor given by the join of ordinals. This strict monoidal category contains a generic monoid (the first non-empty ordinal) and Theorem 5.4 recovers the well-known fact that monoids in a (strict) monoidal category A are the same as (strict) monoidal functors from Δ_{+} to A.

5.6. Monad morphisms. Let S (resp. T) be a finitary monad on a cocomplete category 𝔻 (resp. ℂ). For any functor d : ℂ → 𝔻 with left adjoint c : 𝔻 → ℂ the following three conditions are equivalent:

1. There exists a functor d′ : Alg_{T} → Alg_{S} such that U_{S}d′ = dU_{T};

2. There exists a natural transformation Ψ : Sd ⇒ dT compatible with the multiplication and unit of S and T;

3. There exists a morphism of monads Φ : S ⇒ dT c.

The equivalence between (1) and (2) is classical and does not require the existence of a left adjoint c. For the equivalence between (2) and (3), use unit η : id_{𝔻} ⇒ dc and counit ϵ : cd ⇒ id_{ℂ} of the adjunction to define Φ = Ψc ∘ Sη, resp. Ψ = dT ϵ ∘ Φd. A 2-categorical diagram chase shows that these two assignments are mutually inverse.

If these conditions are satisfied then by the adjoint lifting theorem the functor d′ has a left adjoint c′ such that the following square of adjoint functors commutes:

(11)

[figure: U_{T}; F_{T}; c; d; U_{S}; F_{S}; Alg_{S}; d′; c′; Alg_{T}; 𝔻; ℂ]

The natural transformation Φ : S ⇒ dT c yields (by adjunction) a natural transformation Φ′ : cS ⇒ T c and hence a natural transformation T Φ′ : T cS ⇒ T^{2}c which, after composition with μc : T^{2}c ⇒ T c, gives rise to a natural transformation

θ : T cS ⇒ T c

inducing the structure of a right S-module on the composite functor T c : 𝔻 → ℂ.

5.7. Definition. We will say that Φ : S ⇒ dT c is a cartesian monad morphism if Φ is a cartesian natural transformation and c ⊣ d is a cartesian adjunction (i.e. unit and counit are cartesian natural transformations and c preserves pullbacks).

5.8. Lemma. For a natural transformation Φ : S ⇒ dT c between cartesian monads such that c ⊣ d is a cartesian adjunction, the following conditions are equivalent:

(i) the natural transformation Φ : S ⇒ dT c is cartesian;

(ii) the natural transformation Φ′ : cS ⇒ T c is cartesian;

(iii) the natural transformation θ : T cS ⇒ T c is cartesian.

Proof. Φ is cartesian if and only if Φ′ is because of the identities Φ′ = (ϵT c)(cΦ) and Φ = (dΦ′)(ηS) and the hypothesis that c preserves pullbacks. Since μ : T^{2} ⇒ T is cartesian and θ = (μc)Φ′ we see that Φ′ is cartesian if and only if θ is.

5.9. Definition. [6] Let Φ : S ⇒ dT c be a cartesian monad morphism.

An internal S-algebra in a categorical T -algebra A is a lax morphism of categorical S-algebras from the terminal categorical S-algebra to d′(A).

Internal S-algebras in A and S-natural transformations form a category Int_{S}(A). This construction extends to a 2-functor

Int_{S} : Alg_{T} (Cat(ℂ)) → Cat.

5.10. Theorem. [6] The 2-functor Int_{S} is representable. The representing categorical T -algebra T^{S} is the underlying internal category

[figure: T c(1); T cS(1); T cS^{2}(1)]  (12)

of the two-sided simplicial bar construction B_{•}(T c, S, 1) = T cS^{•}(1) of the terminal Salgebra, where the right action of S on T c is given by θ : T cS ⇒ T c.

This categorical T -algebra T^{S} will be called the internal S-algebra classifier of T because morphisms of categorical T -algebras T^{S} → A correspond one-to-one to lax morphisms of categorical S-algebras 1 → d′(A), i.e. to internal S-algebras in A.

Proof. Since Φ : S ⇒ dT c is a cartesian monad morphism, the right action θ : T cS ⇒ T c is cartesian as well (cf. Lemma 5.8), so that B_{•}(T c, S, 1) is a strict Segal object of Alg_{T} (ℂ) by the same inductive argument as in the proof of Theorem 5.4.

The universal property of the underlying categorical T -algebra T^{S} follows now from the following adjunction argument. Lax morphisms 1 → d′(A) correspond by Theorem 5.4 one-to-one to simplicial maps B_{•}(S, S, 1) → d′(A)_{•}; the latter correspond via the adjunction c′ ⊣ d′ to simplicial maps c′B_{•}(S, S, 1) → A_{•}. The simplicial isomorphism c′B_{•}(S, S, 1) ≅ B_{•}(T c, S, 1) permits us to conclude.

5.11. Internal left Kan extensions. For each categorical T -algebra A, the cartesian monad morphism Φ : S ⇒ dT c induces a functor

δ_{A}^{Φ} : Int_{T} (A) → Int_{S}(A),

taking an internal T -algebra X : 1 → A to the internal S-algebra d′(X) : 1 → d′(A). In good cases, the functor δ_{A}^{Φ} admits a left adjoint

γ_{A}^{Φ} : Int_{S}(A) → Int_{T} (A).

It is one of the crucial observations of [6] that this left adjoint γ_{A}^{Φ} (if it exists) can be computed as an internal left Kan extension. Indeed, δ_{A}^{Φ} may be identified with restriction (T^{Φ})^{∗} along a certain internal functor of classifiers

T^{Φ} : T^{S} → T^{T}

in the following way: represent an internal T -algebra X in A by X̃ : T^{T} → A. Then the internal S-algebra δ_{A}^{Φ}(X) is represented by the composite morphism

[figure: T^{S}; T^{Φ}; T^{T}; X̃; A.]

Accordingly, the left adjoint γ_{A}^{Φ} may be identified with left Kan extension (T^{Φ})_{!} along the same internal functor. On objects, the internal functor T^{Φ} : T^{S} → T^{T} is given by T (!) : T c(1) → T (1), where ! : c(1) → 1 while on morphisms T^{Φ} is given by

T cS(1) ⟶^{T Φ′_{1}} T^{2}c(1) ⟶^{T^{2}(!)} T^{2}(1).

5.12. Proposition. [6] Let A be a categorical T -algebra and Φ : S ⇒ dT c be a cartesian monad morphism.

The adjoint pair γ_{A}^{Φ} : Int_{S}(A) ⇆ Int_{T} (A) : δ_{A}^{Φ} is represented by left Kan extension and restriction along the internal functor T^{Φ} : T^{S} → T^{T} in T -algebras.

Proof. It suffices to show that δ_{A}^{Φ} is represented by restriction along T^{Φ}.

The image δ_{A}^{Φ}(X) of an internal T -algebra X : 1 → A is the lax morphism of categorical S-algebras d′(X) : 1 = d′(1) → d′(A). By Theorem 5.4, such a lax morphism is represented by a simplicial map B_{•}(S, S, 1) → d′(A)_{•}. In virtue of the adjunction c′ ⊣ d′, the latter corresponds to a simplicial map c′B_{•}(S, S, 1) ≅ B_{•}(T c, S, 1) → A_{•}. It remains to be shown that this simplicial map factors through the simplicial map B_{•}(T, T, 1) → A_{•} representing the internal T -algebra X.

The required simplicial map c′B_{•}(S, S, 1) → B_{•}(T, T, 1) is adjoint to a simplicial map B_{•}(S, S, 1) → d′B_{•}(T, T, 1). The latter derives from the natural transformation Ψ : Sd ⇒ dT so that the former derives from its “mate” Φ′ : cS ⇒ T c. As underlying internal functor we get the functor T^{Φ} : T^{S} → T^{T} defined above.

5.13. Definition. [67] Let (A, ξ_{A}) be a categorical T -algebra and ξ : B → C be a morphism of categorical T -algebras. The algebra A is called cocomplete with respect to ξ if for any morphism of T -algebras F : B → A the following pointwise left Kan extension

[figure: ξ; B; C; A; F; G; ϕ]

exists in Cat(ℂ) and the induced diagram

[figure: T (ξ); T (B); T (C); T (A); T (F); T (G); T (ϕ); A; ξ_{A}]

exhibits ξ_{A} · T (G) as the pointwise left Kan extension of ξ_{A} · T (F) in Cat(ℂ).

5.14. Theorem. [67] Let A be a categorical T -algebra which is cocomplete with respect to T^{Φ} : T^{S} → T^{T} and let Y be an internal S-algebra in A. Then the pointwise left Kan extension of Ỹ along T^{Φ} in Alg_{T} (Cat(ℂ)) exists and its underlying functor is the pointwise left Kan extension of U_{T} (Ỹ) along U_{T} (T^{Φ}).

In particular,

U_{T} ((T^{Φ})_{!}(Y)) = colim_{U_{T} (T^{S})}U_{T} (Ỹ) in Cat(ℂ).

A useful generalisation is the following relative version. Let

[figure: R; T; S; Φ]

be a commutative triangle of cartesian monad morphisms (cf. Definition 5.7). As above it induces a morphism of categorical T -algebras T^{Φ} : T^{R} → T^{S}.

5.15. Theorem. [67] Let A be a categorical T -algebra which is cocomplete with respect to T^{Φ} : T^{R} → T^{S} and let Y be an internal R-algebra in A. Then the pointwise left Kan extension of Ỹ along T^{Φ} in Alg_{T} (Cat(ℂ)) exists and its underlying functor is the pointwise left Kan extension of U_{T} (Ỹ) along U_{T} (T^{Φ}).

In other words, the following diagram of adjoint functors commutes:

Int_{R}(A) [figure: \underline{(T^{Φ})^{∗}}; (T^{Φ})_{!}] Int_{S}(A)

[figure: [U_{T} (T^{R}), U_{T} (A)]; U_{T}; \underline{U_{T} (T^{Φ})^{∗}}; U_{T} (T^{Φ})_{!}; [U_{T} (T^{S}), U_{T} (A)]; U_{T}]

5.16. Remark. Theorems 5.14 and 5.15 are valid more generally in a 2-monadic setting, and a conceptual proof is based on an internalisation of Guitart’s theory of exact squares [30]. A detailed exposition would lead us too far from our main purpose and we refer the reader to Weber [67]. Theorem 2.4.4 and Theorem 5.7.2 in loc. cit. yield a comparatively short proof in the special case of cartesian monads. The two main ideas entering in the proof may be summarised as follows:

(a) If in the situation of Definition 5.13 the additional assumption is made that the commuting square of internal functors

[figure: T (B); T (ξ); T (C); B; ξ_{B}; ξ; C; ξ_{C}]

is exact (cf. [67, Definition 2.4.1]) then the pair of pointwise left Kan extensions

(T (G), G) : (T (C), C) → (T (A), A)

is a pseudomorphism of T -algebras and the forgetful functor Alg_{T} (Cat(ℂ)) → Cat(ℂ) preserves the pointwise left Kan extension of F : B → A along ξ : B → C.

(b) Under the hypotheses of Theorem 5.14 (and similarly for Theorem 5.15) the commuting square of internal functors

T (T^{S}) \overline{T (T^{Φ})_{}}T (T^{T})

[figure: T^{S}; ξT_{S}; T^{Φ}; T^{T}; ξT_{T}]

is indeed exact in Cat(ℂ) by [67, Proposition 4.3.4] since it is a pullback square and the vertical functors are discrete fibrations.

It is remarkable that the cartesianness of the unit of the monads S and T is not needed, neither for the existence of the internal algebra classifiers nor for the validity of Theorems 5.14 and 5.15. We are however not aware of a single example of a pullback preserving monad, whose multiplication is cartesian and whose unit is not. So, we preferred to keep working with cartesian monads.

6. Polynomial and tame polynomial monads

In this section we recall the definition of a polynomial monad in sets and of its associated coloured symmetric operad. We also introduce the new concept of a tame polynomial monad which will be crucial for us. For a nice and instructive account of polynomial functors we recommend Kock’s article [38] from which we shall borrow the idea of representing coloured bouquets as certain special polynomials. For a general treatment of polynomial monads in locally cartesian closed categories the reader may consult Gambino-Kock [24]. An extension to categories with pullbacks has been studied by Weber [64]. Earlier appearances of polynomial functors can be found in the articles of Tambara [62] and of Moerdijk-Palmgren [51].

6.1. Polynomial functors. For any set I we denote Set/I the comma category over I. Objects of Set/I are mappings π : X → I, and morphisms of Set/I are commuting triangles over I. For each i ∈ I, the preimage π^{−1}(i) will be called the fibre of π over i. The mapping π is completely determined by its fibres, and hence the category Set/I may be identified with the category of I-indexed families of sets (X_{i})_{i∈I}. This will be our favourite notation for the objects of Set/I.

6.2. Definition. A polynomial P = (s, p, t) is a diagram in sets of the form

[figure: J; s; E; p; B; t; I]

A polynomial is of finite type if all fibres of the middle arrow p are finite. Each polynomial P generates a functor between overcategories

\underline{P} : Set/J → Set/I

which is defined as the composite functor

[figure: Set/J; s^{∗}; Set/E; p_{∗}; Set/B; t_{!}; Set/I]

where s^{∗} is the pullback functor,

s^{∗}(X)_{e} = X_{s(e)},

p_{∗} is right adjoint to p^{∗},

p_{∗}(X)_{b} = ∏_{e∈p^{−1}(b)} X_{e},

and t_{!} is left adjoint to t^{∗},

t_{!}(X)_{i} = ∐_{b∈t^{−1}(i)} X_{b}.

So, the functor \underline{P} is given by the formula

\underline{P} (X)_{i} = ∐_{b∈t^{−1}(i)} ∏_{e∈p^{−1}(b)} X_{s(e)},  (13)

which explains the name ‘polynomial’ that is a sum of products of formal variables.

Any functor \underline{P} generated by a polynomial P is called a polynomial functor. In particular, polynomial functors preserve connected limits. This property characterises polynomial functors from Set/J to Set/I. For this and other characterisations of polynomial functors we refer the reader to [38, 24]. In particular, polynomial functors compose. The composite functor \underline{P} ∘ \underline{Q} is the polynomial functor \underline{P Q} generated by an up to unique isomorphism uniquely determined polynomial P Q. Cartesian natural transformations of polynomial functors correspond bijectively to commutative diagrams of the form

[figure: J; s′; E′; p′; B′; t′; I; J; 1_{J}; s; E; p; B; t; I; 1_{I}]

in which the horizontal lines are polynomials and the middle square is a pullback square. This defines a 2-category Poly with 0-cells the overcategories Set/I, with 1-cells the polynomial functors, and with 2-cells the cartesian natural transformations. We denote Poly(I) the category of polynomial endofunctors Set/I → Set/I and cartesian natural transformations. It is a monoidal category for composition of endofunctors.

6.3. Definition. A polynomial monad is a monad in the 2-category Poly.

Hence a polynomial monad T over I is a monoid in (Poly(I), ∘). Each polynomial monad over I is a cartesian monad on Set/I. The polynomial monad is finitary if and only if the generating polynomial is of finite type.

From now on we always assume that our polynomial monads are finitary.

6.4. Remark. Let T be the polynomial monad generated by the polynomial

[figure: I; s; E; p; B; t; I]

We shall outline how to define an I-coloured symmetric operad O_{T} whose associated monad is T. Each element b ∈ B comes equipped with a target t(b) = i ∈ I, and a fibre p^{−1}(b) ⊂ E. The elements e ∈ p^{−1}(b) of the fibre have sources s(e) ∈ I.

A T -operation is a pair (b, σ) consisting of an element b ∈ B and a bijection σ : {1, 2, …, k} → p^{−1}(b). We shall refer to σ as a linear ordering of the fibre. The Icoloured symmetric operad O_{T} associated to T consists precisely of all T -operations. Such a T -operation (b, σ) belongs to O_{T} (i_{1}, …, i_{k}; i) if and only if

t(b) = i and (s(σ(1)), s(σ(2)), …, s(σ(k)) = (i_{1}, …, i_{k}).

We shall write s(b, σ) = (i_{1}, …, i_{k}) and t(b, σ) = i and call them source and target of the T -operation (b, σ).

A composite T -operation consists of a list ((b, σ); (b_{1}, σ_{1}), (b_{2}, σ_{2}), …, (b_{k}, σ_{k})) such that (t(b_{1}, σ_{1}), …, t(b_{k}, σ_{k})) = s(b, σ). The multiplication of the operad O_{T} is induced by the multiplication of the polynomial monad T (cf. Remark 6.5 below) and associates to a composite T -operation a single T -operation (b, σ)((b_{1}, σ_{1}), …, (b_{k}, σ_{k})) with same target as (b, σ) and with source-list (s(b_{1}, σ_{1}), s(b_{2}, σ_{2}), …, s(b_{k}, σ_{k})) linearly ordered in the obvious way. This multiplication satisfies the usual associativity, unitarity and equivariance constraints of an I-coloured symmetric operad.

We shall denote the composed T -operation by

(b, σ)((b_{1}, σ_{1}), …, (b_{k}, σ_{k})) = (b^{σ}(b_{1}, …, b_{k}), σ(σ_{1}, …, σ_{k}))

to remind that the linear ordering σ of the fibre of b determines the way in which the individual T -operations (b_{i}, σ_{i}) are “inserted” into the leading T -operation (b, σ).

6.5. Remark. The process just described constitutes a functor O from the category of finitary polynomial monads over I to the category of symmetric I-coloured operads in sets with freely acting symmetry groups. Kock [38] and Szawiel-Zawadowski [58] showed that this functor is an equivalence of categories. For a deeper study of the relationship between polynomial monads and operads, the reader may consult the recent article [65] of Weber.

Let us briefly recall the argument given by Kock in [38].

6.6. Definition. [38] An I-coloured bouquet of arity k is a polynomial

[figure: I; s; {1, 2, …, k}; p; {1}; t; I.]

The latter will be represented by the (k + 1)-tuple (s(1), …, s(k); t(1)) ∈ I^{k+1}.

The full subcategory of Poly(I) spanned by I-coloured bouquets will be denoted Bouq(I). The associated nerve functor is denoted

O : Poly(I) → Coll(I) = Set^{Bouq(I)^{op}}
P ↦ O_{P} = Hom_{Poly(I)}(−, P)

The subcategory Bouq(I) is dense in Poly(I), i.e. the nerve functor is fully faithful. Moreover, Bouq(I) is a groupoid: the symmetry group of a bouquet of arity k may be identified with a certain subgroup of the symmetry group of {1, …, k}. The essential image of the nerve functor consists of those I-coloured collections in Coll(I) for which the automorphisms in Bouq(I) act freely, cf. [38, Theorem 2.4.10].

There is a substitutional ∘-product on Coll(I) for which the monoids are precisely the I-coloured symmetric operads in sets, cf. the appendix of [13], where the category of I-coloured bouquets Bouq(I) is denoted 𝔽^{≤}(I). It can be checked by hand that the nerve functor is a monoidal functor

O : (Poly(I), ∘) → (Coll(I), ∘)

and therefore takes polynomial monads over I to I-coloured symmetric operads. It follows from [38, Theorem 2.2.12] that this “enhanced” nerve functor induces an equivalence between the category of finitary polynomial monads over I and the category of I-coloured symmetric operads with freely acting symmetry groups, cf. also [58].

6.7. Algebras over polynomial monads. The category of T -algebras Alg_{T} for a polynomial monad T on Set/I coincides with the category of O_{T} -algebras of the associated coloured symmetric operad O_{T}. Explicitly a T -algebra in sets is given by an I-indexed family of sets (A_{i})_{i∈I} together with structural maps

m_{(b,σ)} : A_{s(σ(1))} × ⋯ × A_{s(σ(k))} → A_{t(b)}

for each operation (b, σ) of T. These structure maps satisfy the usual associativity, unitarity and equivariance conditions of an algebra for a coloured symmetric operad.

Given a cocomplete symmetric monoidal category (E, ⊗, e), the strong symmetric monoidal functor

Set → E : X ↦ ∐_{X} e

takes the coloured symmetric operad O_{T} to a coloured symmetric operad in E and thus defines a category Alg_{T} (E) of T -algebras in E. Explicitly, a T -algebra A in E is an Iindexed family (A_{i})_{i∈I} of objects of E together with structural maps

m_{(b,σ)} : A_{s(σ(1))} ⊗ ⋯ ⊗ A_{s(σ(k))} → A_{t(b)}

for each operation (b, σ) of T, subject to the same associativity, unitarity and equivariance conditions as above.

6.8. Internal T -algebras in cocomplete symmetric monoidal categories. Since each polynomial monad T is cartesian it generates a 2-monad on the category Cat/I where I is considered as a discrete category. The category of strict algebras for this 2monad is by definition the category Alg_{T} (Cat) of categorical T -algebras. There is also a 2-category of pseudo-T -algebras associated to the 2-monad T. A general strictification theorem of Power implies that any pseudo-T -algebra is equivalent to a strict T -algebra (cf. [54, 42, 6]). We tacitly apply this strictification whenever necessary.

A categorical T -algebra (A_{i})_{i∈I} is cocomplete with respect to morphisms between small categorical T -algebras in the sense of Definition 5.13 if and only if each A_{i} is a cocomplete category and the structure maps m_{(b,σ)} : A_{s(σ(1))} × ⋯ × A_{s(σ(k))} → A_{t(b)} preserve colimits in each variable.

Let A be a categorical T -algebra. Then an internal T -algebra in A can be explicitly given by a collection of objects a_{i} ∈ A_{i} together with a morphism

μ_{(b,σ)} : m_{(b,σ)}(a_{s(σ(1))}, …, a_{s(σ(k))}) → a_{t(b)},

for each operation (b, σ), which satisfies obvious associativity, unitarity and equivariancy conditions. Here, m_{(b,σ)} is the structure functor of A.

To any symmetric monoidal category (E, ⊗, e) we associate the categorical pseudo-T - algebra E_{T}^{•} with constant underlying collection

E_{T}^{•}(i) = E, i ∈ I.

Nullary T -operations act as unit e : 1 → E, unary T -operations act as identity and T - operations of arity n ≥ 2 acts as iterated tensor product ⊗^{n}. This pseudo-T -algebra E_{T}^{•} is cocomplete with respect to morphisms between small pseudo-T -algebras if and only if E is cocomplete as a category, and moreover the tensor of E commutes with colimits in both variables, cf. [67, Proposition 2.3.3]. Recall that the latter holds in particular if E is closed symmetric monoidal.

The assignment E ↦ E_{T}^{•} is the right adjoint part of an adjunction between categorical T -algebras and symmetric monoidal categories. This adjunction is induced by a map T → P of polynomial monads in Cat where P denotes the monad for symmetric monoidal categories. The existence of this adjunction provides a conceptual reason for the existence of an enrichment over E of the category of T -algebras. The interested reader may find more details in [66, 67]. We will not pursue this point of view any further here. However, it will be essential for us to represent T -algebras in E as internal T -algebras in E_{T}^{•}, based on the following proposition.

6.9. Proposition. The category of T -algebras in E is isomorphic to the category of internal T -algebras in E_{T}^{•}.

Proof. An internal T -algebra in E_{T}^{•} is by definition a lax morphism of categorical T - algebras 1 → E_{T}^{•}. Such a lax morphism is given by an I-collection (X_{i})_{i∈I} of objects of E together with coherence data fulfilling coherence conditions. The coherence data consists of a 2-cell from T (1) → T (E_{T}^{•}) → E_{T}^{•} to T (1) → 1 → E_{T}^{•} which amounts precisely to Σ_{k}-equivariant structure maps in E

X_{i_{1}} ⊗ ⋯ ⊗ X_{i_{k}} → X_{i}

one for each orbit of T -operations b ∈ T (1) of type (i_{1}, …, i_{k}; i), cf. Remark 6.4 and Section 6.13. The unit and associativity constraints of this 2-cell (cf. Section 5.2) translate into the familiar unit and associativity constraints of an operad action.

6.10. Representing T -algebras as internal functors T^{T} → E_{T}^{•}. –

According to Proposition 6.9 and Theorem 5.4, T -algebras in E can be represented as internal functors T^{T} → E_{T}^{•}. By Theorem 5.4, the objects of the classifier T^{T} are the elements of the free T -algebra T (1) ≅ O_{T} (1). These elements correspond bijectively to orbits of T -operations (cf. Remark 6.4), i.e. to elements of B.

A morphism from b′ to b is given by an element of T^{2}(1) with correct source and target. Since T^{2}(1) ≅ (O_{T} ∘O_{T})(1), such an element corresponds to an orbit of composite T -operations ((b, σ); (b_{1}, σ_{1}), …, (b_{k}, σ_{k})) fulfilling b′ = b^{σ}(b_{1}, …, b_{k}) in the notation of Remark 6.4. It is important to observe that each such orbit can be represented by a (k + 1)-tuple (b; b_{1}, …, b_{k}) ∈ B^{k+1} together with a colour-preserving bijection between the source-list of b and the list of targets of the individual b_{i}. This representation of the elements of T^{2}(1) is unique up to a reordering of the b_{i} going along with the appropriate change of bijection.

The unit of the polynomial monad T defines an I-indexed collection (1_{i})_{i∈I} of special elements 1_{i} ∈ B. The latter have singleton fibre with source and target i ∈ I. They induce two families of morphisms in T^{T}, namely the identities

b (b; 1_{i_{1}}, …, 1_{i_{k}})_{}b

and the morphisms

b \overline{(1_{i}; b)^{}}1_{i}.

Now, let (X_{i})_{i∈I} be the I-collection underlying the T -algebra X in E. Then the representing functor of categorical T -algebras

X̃ : T^{T} → E_{T}^{•}

is constructed as follows. We have X̃(1_{i}) = X_{i} and X̃(b) = X_{i_{1}} ⊗ ⋯ ⊗ X_{i_{k}} where (i_{1}, …, i_{k}) is the source-list of the fibre p^{−1}(b) for a fixed linear ordering σ. Then the map X̃(b → 1_{i}) in E_{T}^{•}(i) represents the T -action m_{(b,σ)} : X_{i_{1}} ⊗ ⋯ ⊗ X_{i_{k}} → X_{i} on X, and the functoriality of X̃ : T^{T} → E_{T}^{•} amounts precisely to the equivariance, associativity and unitarity constraints of this T -action.

6.11. Remark. The T -algebra structure on the internal algebra classifier T^{T} splits the latter into components T_{i}^{T} spanned by those objects b ∈ B with target t(b) = i. The restrictions of the representing functor X̃ : T^{T} → E_{T}^{•} to these components will be denoted X̃ : T_{i}^{T} → E. This amounts to removing the forgetful functor U_{T} : Alg_{T} (Cat) → Cat from our notation.

In other words, we will identify the categorical T -algebra T^{T} with its underlying Icollection of categories (T_{i}^{T})_{i∈I}, and will make no notational distinction between the representing functor X̃ : T^{T} → E_{T}^{•} and its components X̃ : T_{i}^{T} → E. We hope this will cause no confusion.

The reader should observe that the object 1_{i} is terminal in its component T_{i}^{T}, so that the component X_{i} of the I-collection (X_{i})_{i∈I} can be recovered as

X_{i} = X̃(1_{i}) = colim_{b∈T_{i}^{T}}X̃(b).

6.12. Example. At this point, we should mention two examples which have been decisive for the elaboration of the whole theory. If T is the free monoid monad (see Section 9.2) then T^{T} is isomorphic to the augmented simplex category Δ_{+}, cf. Bénabou [10], and we recover the fact, mentioned in Example 5.5, that monoids in E correspond to strict monoidal functors Δ_{+} → E. If T is the free symmetric operad monad (see Section 9.4) then T^{T} is isomorphic to a category of labelled rooted planar trees RTr^{RTr} which goes back to Ginzburg-Kapranov [28, Section 1.2], and which again has the characteristic property that symmetric operads in E correspond to certain functors RTr^{RTr} → E.

6.13. Graphical formalism. It is convenient to use some sort of graphical formalism (cf. [39, 51]) to visualise objects and morphisms of T^{T}. An object of T^{T} (i.e. an orbit of T -operations) will be represented as a non-planar corolla

[figure: i_{1}; i_{5}; i_{2}; i_{4}; i_{3}; i; b]

where b ∈ B, the incoming edges are decorated by the source-list of the fibre s(p^{−1}(b)) = (i_{1}, i_{2}, …, i_{5}) and the outgoing edge is decorated by the target t(b) = i. This orbit of T -operations b is said to be of type (i_{1}, …, i_{5}; i), cf. Definition 6.6.

A morphism of T^{T} (i.e. an orbit of composite T -operations) will be represented by a non-planar bicorolla (i.e. corolla of corollas) as for instance

[figure: i_{12}; i_{13}; i_{11}; b_{1}; b; i; i_{2}; i_{1}; i_{22}; i_{21}; b_{2}]

where b is of type (i_{1}, i_{2}; i) and b_{1}, b_{2} are respectively of type (i_{11}, i_{12}, i_{13}; i_{1}) and (i_{21}, i_{22}; i_{2}). This bicorolla represents a morphism b(b_{1}, b_{2}) → b in T^{T} with source b(b_{1}, b_{2}) obtained by “contracting” inner edges, i.e. by inserting b_{1} and b_{2} into b according to the multiplication of the polynomial monad T and the source/target matching displayed in the bicorolla. The notation b(b_{1}, b_{2}) → b for morphisms in T^{T} is slightly abusive, insofar as it does not explicitly mention the bijection between the list of targets of the b_{i} and the source-list of b. The graphical representation incorporates this bijection and we tacitly assume that such a bijection is given.

6.14. Cartesian morphisms of polynomial monads. We need a more general notion of map between polynomials which includes the possibility of base-change. Let S be a polynomial monad generated by a polynomial

[figure: J; s′; E′; p′; B′; t′; J.]

A cartesian morphism Φ = (δ, ψ, ϕ) from S to T is a commutative diagram

[figure: J; s′; E′; p′; B′; t′; J; I; δ; s; E; ψ; p; B; ϕ; t; I; δ]

in sets in which the middle square is a pullback, the horizontal lines generate the polynomial monads S and T and the diagram

[figure: ϕ; p; ψ; δ∘s′; δ∘t′; E′; I; I; p′; B′; E; B]

generates a morphism of polynomial monads. The mapping δ : J → I induces a cartesian adjunction c ⊣ d where d = δ^{∗} : Set/I → Set/J is the pullback functor and c = δ_{!} : Set/J → Set/I is its left adjoint, so that for an object Y of Set/J :

c(Y)_{i} = ∐_{j∈δ^{−1}(i)} Y_{j}.  (14)

Then the equivalent conditions of Lemma 5.8 are fulfilled and Φ generates a cartesian monad morphism Φ : S ⇒ dT c in the sense of Definition 5.7.

For a symmetric monoidal category E we get a restriction functor

δ_{E}^{Φ} : Alg_{T} (E) → Alg_{S}(E).

Observe that d′(E_{T}^{•}) = E_{S}^{•} so that an internal S-algebra in E_{T}^{•} is the same as an ordinary S-algebra in E. Therefore, the restriction functor δ_{E}^{Φ} is induced by a functor of internal algebra classifiers T^{Φ} : T^{S} → T^{T}, and its left adjoint

γ_{E}^{Φ} : Alg_{S}(E) → Alg_{T} (E)

can be calculated as a left Kan extension along the same functor. To carry out such a program we need a description of the internal S-algebra classifier T^{S} and of the canonical functor T^{Φ} : T^{S} → T^{T} in terms of the given map Φ between the generating polynomials.

6.15. The category T^{S}. By Theorem 5.10, the objects of T^{S} are the elements of T c(1). According to (13) and (14), these elements can be understood as J-coloured T -operations. In order to distinguish them from the objects of T^{T} we denote them by bold letters. A Jcoloured T -operation b is given by an element b ∈ B together with a colour j ∈ δ^{−1}(s(e)) for each e ∈ p^{−1}(b). The internal functor T^{Φ} : T^{S} → T^{T} replaces the J-colouring with an I-colouring by applying δ. So, an object b of T^{S} is determined by its image T^{Φ}(b) together with a compatible J-colouring.

In terms of our graphical formalism, such an object is represented by a non-planar corolla

[figure: j_{1}; j_{5}; j_{2}; j_{4}; j_{3}; i; b]

with J-decorated incoming edges and I-decorated outgoing edge. The component θ_{1} of the right S-action θ : T cS ⇒ T c is defined as follows, where we freely use our slightly abusive notation for composite operations, cf. Section 6.13. Note first that the elements of T cS(1) can be understood as J-coloured T -operations b together with a compatible family of S-operations d_{1}, …, d_{k} ∈ B′ in the sense that (t′(d_{1}), …, t′(d_{k})) coincides with the J-colouring of b. Then

T^{Φ}(θ(b; d_{1}, …, d_{k})) = T^{Φ}(b)(ϕ(d_{1}), …, ϕ(d_{k})),

and the J-colouring of θ(b; d_{1}, …, d_{k}) is inherited from (the sources of) the fibres of d_{1}, …, d_{k} in an obvious way.

A morphism b′ → b in T^{S} is given by an element (b; d_{1}, …, d_{k}) of T cS(1) such that b′ = θ(b; d_{1}, …, d_{k}). The effect of T^{Φ} on a morphism b′ → b is obvious: if b′ = θ(b; d_{1}, …, d_{k}) then the identity T^{Φ}(b′) = T^{Φ}(b)(ϕ(d_{1}), …, ϕ(d_{k})) represents a morphism T^{Φ}(b′) → T^{Φ}(b) in T^{T}.

6.16. Representing S-algebras as internal functors T^{S} → E_{T}^{•}. –

Let X be an S-algebra in E. By the universal property of T^{S}, the corresponding internal S-algebra in E_{T}^{•} is represented by a morphism of T -algebras X̃ : T^{S} → E_{T}^{•}, which can be can be described as follows: Let b be an object of T^{S}. Then

X̃(b) = X_{j_{1}} ⊗ ⋯ ⊗ X_{j_{k}}  (15)

where (j_{1}, …, j_{k}) is the J-colouring of b. The morphism X̃(b′ → b) in E is defined by the action of the S-operations d_{1}, …, d_{k} on X, where b′ = θ(b; d_{1}, …, d_{k}).

The T -algebra structure on the internal algebra classifier T^{S} splits the latter into components T_{i}^{S} spanned by those objects b with target t(b) = i. The restrictions of the representing functor X̃ : T^{S} → E_{T}^{•} to these components will be denoted X̃ : T_{i}^{S} → E. This amounts to removing the forgetful functor U_{T} : Alg_{T} (Cat) → Cat from our notation.

In other words, we will identify the categorical T -algebra T^{S} with its underlying Icollection of categories (T_{i}^{S})_{i∈I}, and will make no notational distinction between the representing functor X̃ : T^{S} → E_{T}^{•} and its components X̃ : T_{i}^{S} → E. We hope this will cause no confusion.

6.17. Theorem. Let E be a cocomplete, closed symmetric monoidal category and let Φ : S ⇒ dT c be a cartesian monad morphism between polynomial monads. Then restriction δ_{E}^{Φ} : Alg_{T} (E) → Alg_{S}(E) has a left adjoint γ_{E}^{Φ} : Alg_{S}(E) → Alg_{T} (E).

For any S-algebra X in E, the underlying I-collection of the T -algebra γ_{E}^{Φ}(X) can be calculated as the following colimit:

γ_{E}^{Φ}(X)_{i} = (T^{Φ})_{!}(X̃)(1_{i}) = colim_{b∈T_{i}^{S}}X̃(b) (i ∈ I).  (16)

Proof. The first identification follows from Theorem 5.14, cf. Remark 6.11 for our notations and Section 6.8 for applicability. The second identification just expresses that left Kan extension along T_{i}^{S} → 1 (which calculates the colimit on the right) can be achieved in two steps: first left Kan extension along (T^{Φ})_{i} : T_{i}^{S} → T_{i}^{T} then left Kan extension along T_{i}^{T} → 1 (which calculates evaluation at 1_{i}).

6.18. Tame polynomial monads. Let T be a finitary monad on a cocomplete category ℂ. We denote by T + 1 the finitary monad on ℂ × ℂ given by

(T + 1)(X, Y) = (T X, Y)
(T + 1)(ϕ, ψ) = (T ϕ, ψ)

with evident multiplication and unit. We get the following square of adjunctions

Alg_{T} × ℂ [figure: \underline{(id_{Alg_{T}} × U_{T})Δ_{Alg_{T}}}; − ∨ F_{T} (−)] Alg_{T}

[figure: ℂ × ℂ; U_{T} × id_{ℂ}; F_{T} × id_{ℂ}; \underline{Δ_{ℂ}}; − ⊔ −; ℂ; U_{T}; F_{T}]

(17)

in which the right adjoints commute by definition.

If ℂ has pullbacks which commute with coproducts, and T is a cartesian monad, then it is straightforward to verify that T +1 is a cartesian monad as well, and that the adjoint square (17) induces a cartesian morphism from T + 1 to T in the sense of Definition 5.7.

If T is a polynomial monad on Set/I generated by the polynomial

[figure: I; s; E; p; B; t; I]

then T + 1 is a polynomial monad on Set/I × Set/I = Set/(I ⊔ I) generated by

[figure: I ⊔ I; s ⊔ 1_{I}; E ⊔ I; p ⊔ 1_{I}; B ⊔ I; t ⊔ 1_{I}; I ⊔ I]

More precisely, the adjoint square (17) for a polynomial monad T on Set/I is induced by the following cartesian morphism of polynomials (cf. 6.14)

[figure: I ⊔ I; s ⊔ 1_{I}; E ⊔ I; p ⊔ 1_{I}; B ⊔ I; t ⊔ 1_{I}; I ⊔ I; I; ∇_{I}; s; E; ψ; p; B; ϕ; t; I; ∇_{I}]

in which ∇_{I} is the identity on each copy of I, and ϕ (resp. ψ) is the identity on B (resp. E) and the unit η of T on I.

6.19. Definition. A semi-free coproduct of T -algebras is a coproduct X ∨ F_{T} (K) of a T -algebra X and a free T -algebra F_{T} (K).

A polynomial monad T is said to be tame if the internal classifier for semi-free coproducts T^{T+1} is a coproduct of categories with terminal object.

6.20. The category T^{T+1} explicitly. The generating polynomial of T + 1

[figure: I ⊔ I; s ⊔ 1_{I}; E ⊔ I; p ⊔ 1_{I}; B ⊔ I; t ⊔ 1_{I}; I ⊔ I]

can be described in terms of our graphical formalism. Its set of operations B ⊔ I consists of corollas of two types

[figure: X; X; X; X; X; X; b; and; K; K; 1_{i}]

where b ∈ B, and 1_{i} ∈ B for i ∈ I represents the unit of B = T (1).

According to Section 6.15 an object b of T^{T+1} is then represented by a corolla

[figure: K; K; X; K; X; t(b); b]

with incoming edges coloured by X and K and outgoing edge coloured by the target t(b) of b. The X-edges correspond to the operations on the T -algebra summand of the semi-free coproduct, while the K-edges correspond to the free summand.

A morphism g : b′ → b in T^{T+1} is given by a set of elements b_{1}, …, b_{k} ∈ B, one for each X-coloured edge of b, where the 1′s correspond to K-edges and the b′_{i}s correspond to X-edges of b. In the formalism of Section 6.15 a typical morphism in T^{T+1} is therefore a bicorolla

[figure: X; X; X; b_{1}; K; 1; K; 1; X; X; K; K; b; X; X; X; b_{2}]

In this picture we tacitly assume that 1 is the unit element 1_{s(e)} where e belongs to the fibre p^{−1}(b). The corolla representing the source of g : b′ → b is obtained by contracting inner edges of the bicorolla according to the multiplication b′ = b(1, …, b_{1}, 1, …, b_{k}, …, 1) of the polynomial monad T, cf. Section 6.13.

6.21. Remark. If T is a tame polynomial monad then semi-free coproducts admit a functorial polynomial formula similar to formula (1) of the introduction. Indeed, Theorem 6.17 applied to the adjoint square (17), shows that the underlying object of the semi-free coproduct X ∨F_{T} (K) is the colimit of a functor X̃ defined on T^{T+1}. If T^{T+1} has a terminal object in each connected component, then the colimit of X̃ is the coproduct of the values of X̃ at these terminal objects. These values are tensor products of as many X′s and K′s, as there are X- resp. K-edges in the corollas representing the terminal objects of the different connected components of T^{T+1}.

More precisely, there is a (uniquely determined) polynomial functor

P : Set/I × Set/I → Set/I

rendering the following diagram

Alg_{T} × Set/I \overline{(−) ∨ F_{T} (−)_{}}Alg_{T}

[figure: Set/I × Set/I; U_{T} × id_{Set/I}; P; Set/I; U_{T}]

commutative with generating polynomial given by

I ⊔ I ^{_{}s} π_{0}(T^{T+1})^{∗} \overline{p_{}}π_{0}(T^{T+1}) t^{}I.

Here we identify the set π_{0}(T^{T+1}) of connected components of T^{T+1} with a representative set of objects of T^{T+1} which are terminal in their component. Such an object of T^{T+1} is represented by a corolla decorated by an element b ∈ B with edges having colours X or K. The target of b gives a map t : π_{0}(T^{T+1}) → I. The set π_{0}(T^{T+1})^{∗} is the set of corollas as above with one edge marked. The map p : π_{0}(T^{T+1})^{∗} → π_{0}(T^{T+1}) simply forgets the marking. The source map s : π_{0}(T^{T+1})^{∗} → I ⊔ I returns the colour of the marked edge of b and places it to the first copy of I if the edge-colour is X and to the second if the edge-colour is K.

See Sections 9.2 and 9.4 for explicit examples.

7. Free algebra extensions

In this central section we apply the theory of internal algebra classifiers to get an explicit formula for free algebra extensions over tame polynomial monads. This formula generalises the Schwede-Shipley formula [60] for free monoid extensions and involves a careful analysis of the internal classifier T^{T_{f,g}} for free algebra extensions over a tame polynomial monad T. We show in particular that a good behaviour of semi-free coproducts of T -algebras (the tameness of T) is sufficient to express the underlying object of a free T -algebra extension as a sequential colimit of pushouts.

7.1. Internal classifier for free algebra extensions. Let T be a finitary monad on a cocomplete category ℂ. Let P_{f,g} be the category whose objects are quintuples (X, K, L, g, f), where X is a T -algebra, K, L are objects in ℂ and g : K → U_{T} (X), f : K → L are morphisms in ℂ. There is an obvious forgetful functor

U_{f,g} : P_{f,g} → ℂ × ℂ × ℂ,

taking the quintuple (X, K, L, f, g) in P_{f,g} to the triple (U_{T} (X), K, L) in ℂ × ℂ × ℂ.

7.2. Proposition. Let T be a finitary monad on a cocomplete category ℂ.

(i) The functor U_{f,g} is monadic and the induced monad T_{f,g} is finitary;

(ii) There is a commutative square of adjunctions

(18)

[figure: U_{T}; F_{T}; ⊔; Δ; U_{f,g}; F_{f,g}; P_{f,g}; Δ′; ⊔′; Alg_{T}; ℂ × ℂ × ℂ; ℂ]

in which Δ : ℂ → ℂ × ℂ × ℂ is the diagonal and Δ′ is given by

Δ′(Y) = (Y, U_{T} (Y), U_{T} (Y), 1_{U_{T} (Y)}, 1_{U_{T} (Y)}).

(iii) The left adjoint ⊔ to Δ is given by coproduct in ℂ; the left adjoint ⊔′ to Δ′ is given by the following pushout in Alg_{T}:

[figure: F_{T} (K); F_{T} (f); F_{T} (L); X; ĝ; ⊔′ (X, K, L, g, f)]  (19)

in which ĝ is adjoint to g.

(iv) If ℂ has pullbacks which commute with coproducts and T is a cartesian monad, then T_{f,g} is a cartesian monad as well, and the adjoint square (18) induces a cartesian morphism from T_{f,g} to T in the sense of Definition 5.7.

(v) If T is a polynomial monad on Set/I then T_{f,g} is a polynomial monad on Set/(I ⊔ I ⊔ I).

Proof. –

(i) The left adjoint F_{f,g} to U_{f,g} takes a triple (X, K, L) in ℂ × ℂ × ℂ to the quintuple (F_{T} (X ⊔ K), K, K ⊔ L, j, i) in P_{f,g} where i : K → K ⊔ L is the coproduct injection and j : K → U_{T} F_{T} (X ⊔ K) is the composite of the coproduct injection K → X ⊔ K and the unit of the monad T at X ⊔ K. It is then straightforward to check that F_{f,g} is indeed left adjoint to U_{f,g}, and that T_{f,g} = U_{f,g}F_{f,g} is finitary.

(ii) It is obvious that the square of right adjoints commutes. The existence of the left adjoint ⊔′ follows from the adjoint lifting theorem.

(iii) By adjointness, a map (X, K, L, g, f) → Δ′(Y) in P_{f,g} corresponds one-to-one to a pair of T -algebra morphisms (ϕ : X → Y, ψ : F_{T} (L) → Y) such that ϕĝ = ψF_{T} (f). The universal property of pushout (19) then implies that this pair corresponds one-to-one to a T -algebra morphism ⊔′(X, K, L, g, f) → Y.

(iv) We have seen in (i) that T_{f,g}(X, K, L) = (T (X ⊔ K), K, K ⊔ L) so that T_{f,g} is a cartesian monad, since T is a cartesian monad and moreover pullbacks commute with coproducts in ℂ. It remains to be shown that Proposition 5.8 applies, i.e. that Φ : T_{f,g} → Δ ∘ T ∘ ⊔ is a cartesian natural transformation. Indeed, all three components of

Φ_{(X,K,L)} : (T (X ⊔ K), K, K ⊔ L) → (T (X ⊔ K ⊔ L), T (X ⊔ K ⊔ L), T (X ⊔ K ⊔ L))

are cartesian natural transformations. The first component is obtained by applying T to the coproduct injection X ⊔ K ↪ X ⊔ K ⊔ L, the second component is obtained as the composite of the unit K → T (K) with T (K ↪ X ⊔ K ⊔ L), the third component as the composite K ⊔ L → T (K ⊔ L) → T (X ⊔ K ⊔ L). In all three cases we can conclude, since the unit of T is a cartesian natural transformation, T preserves pullbacks, and pullbacks commute with coproducts in ℂ.

(v) It is enough to show that T_{f,g} preserves connected limits. But in Set/I connected limits commute with coproducts so that the explicit formula for T_{f,g} yields the result.

In virtue of the preceding proposition, Theorem 5.14 allows us to compute free T - algebra extensions in cocomplete categorical T -algebras as left Kan extensions along a map of categorical T -algebras T^{T_{f,g}} → T^{T}.

If E is a cocomplete, closed symmetric monoidal category and T is a polynomial monad, Theorem 6.17 expresses free T -algebra extensions in E as colimits of certain Evalued functors on the free T -algebra extension classifier T^{T_{f,g}}. It is therefore vital to get a better hold on the free T -algebra extension classifier T^{T_{f,g}}. To this effect it will be convenient to introduce three other monads associated to T, which we shall denote by T_{f}, T_{g} and T + 2 respectively.

Let P_{f} be the category whose objects are quadruples (X, K, L, f), where X is a T - algebra, K, L are objects in ℂ and f : K → L is a morphism in ℂ.

Let P_{g} be the category whose objects are quadruples (X, K, L, g), where X is a T - algebra, K, L are objects in ℂ and g : K → U_{T} (X) is a morphism in ℂ.

The obvious forgetful functors U_{f} : P_{f} → ℂ × ℂ × ℂ and U_{g} : P_{g} → ℂ × ℂ × ℂ are monadic yielding monads T_{f} and T_{g} for which there are propositions analogous to Proposition 7.2. We leave the details to the reader.

Finally, recall the monad T + 1 from Section 6.18. We put T + 2 = (T + 1) + 1 which is also a monad on ℂ × ℂ × ℂ as are T_{f,g}, T_{f} and T_{g}.

There is a commutative square of forgetful functors

[figure: P_{f,g}; P_{f}; P_{g}; Alg_{T} × ℂ × ℂ]

over ℂ×ℂ×ℂ. All four forgetful functors have left adjoints so that we get a commutative square of monad morphisms going in the opposite direction

[figure: T_{f,g}; T_{f}; T_{g}; T + 2]

and augmented over T via cartesian natural transformations. We thus obtain a commutative square of categorical T -algebra maps of the corresponding classifiers

[figure: T^{T_{f,g}}; T^{T_{f}}; T^{T_{g}}; T^{T+2}]  (20)

which enables us to analyse the category structure of T^{T_{f,g}}.

Form now on we assume that T is a polynomial monad on Set/I. We have seen that the monad T_{f,g} is then a polynomial monad on Set/(I ⊔ I ⊔ I). Similarly, 7.3. Lemma. For any polynomial monad T on Set/I, the monads T + 2, T_{f}, T_{g} are polynomial monads on Set/(I ⊔ I ⊔ I).

The internal classifiers T^{T_{f,g}}, T^{T_{f}}, T^{T_{g}}, T^{T+2} all have the same object-set, and diagram (20) identifies T^{T_{f}}, T^{T_{g}} with subcategories of T^{T_{f,g}} which intersect in T^{T+2} and which generate T^{T_{f,g}} as a category.

Proof. The first assertion follows by a similar argument as for Proposition 7.2(v) from the explicit formulas for the monads T + 2, T_{f}, T_{g} given below.

According to Theorem 5.10, the object-set of all four internal classifiers is T c(1) where c : ℂ × ℂ × ℂ → ℂ is given by the coproduct in ℂ, while the morphism-sets are T cS(1) where S is one of the four monads T_{f,g}, T_{f}, T_{g}, T +2. We have seen in Proposition 7.2(i) that T_{f,g}(X, K, L) = (T (X ⊔ K), K, K ⊔ L). Similarly, we have T_{f}(X, K, L) = (T (X), K, K ⊔ L) and T_{g}(X, K, L) = (T (X ⊔ K), K, L) as well as (T + 2)(X, K, L) = (T (X), K, L). Evaluating these formulas for X = K = L = 1, and using the fact that c and T are faithful functors, it follows that T^{T_{f}} and T^{T_{g}} are subcategories of T^{T_{f,g}} which intersect in T^{T+2}. Moreover, each morphism in T^{T_{f,g}} is the composite of morphisms in T^{T_{f}} and T^{T_{g}}.

7.4. The category T^{T_{f,g}} explicitly. We begin by describing the cartesian morphism (∇_{I}, ϕ, ψ) of polynomials (cf. Section 6.14)

[figure: I ⊔ I ⊔ I; s′; E′; p′; B′; t′; I ⊔ I ⊔ I; I; ∇_{I}; s; E; ψ; p; B; ϕ; t; I; ∇_{I}]

which generates the cartesian monad morphism Φ : T_{f,g} ⇒ Δ ∘ T ∘ ⊔ described in Proposition 7.2. We use our graphical formalism to represent the elements of B′, compare with Section 6.20. The set B′ consists of corollas of the following types

(i) for b ∈ B, b ≠ 1_{i},

[figure: K; K; X; X; X; b; X]

(observe that a corolla of this type does not have L-coloured edges);

(ii) for i ∈ I,

[figure: X; X; 1_{i}; K; K; 1_{i}; L; L; 1_{i}; K; X; g; K; L; f]

the first three corollas represent identity operations, the fourth corolla represents the operation g : K → U_{T} (X) in a T_{f,g}-algebra, and the last one represents the operation f : K → L in a T_{f,g}-algebra.

The set E′ is the set of such corollas equipped with a marking of one of the incoming edges. The map p′ : E′ → B′ forgets this additional marking. The source map s′ : E′ → I ⊔ I ⊔ I is determined by the source of the decoration of the corolla together with the labeling of the marked edge. In a similar way, the target map t′ : B′ → I ⊔ I ⊔ I is determined by the decoration of the corolla together with the labeling of the root edge. We leave it to the reader to check that this polynomial generates the monad T_{f,g} constructed in Proposition 7.2. On the level of the generating polynomial the multiplication of T_{f,g} is induced by the obvious substitution of corollas into corollas together with the following type of relations:

[figure: X; K; X; X; K; X; b; ∼; X; X; X; X; X; X; b; (; ); X; X; 1_{i}; ,; X; X; 1_{i}; ,; K; X; g; ,; X; X; 1_{i}; ,; K; X; g]

The two mappings ϕ : B′ → B and ψ : E′ → E forget the edge-colourings of the corollas, and identify f and g with identity operations. This explicit presentation of the generating map (∇_{I}, ϕ, ψ) in conjunction with Section 6.15 yields the following description of the free T -algebra extension classifier T^{T_{f,g}}, cf. Section 6.20.

The objects of T^{T_{f,g}} are corollas decorated by the elements of B = T (1) with incoming edges coloured by one of the three colours X, K, L :

[figure: K; L; X; X; X; b; t(b)]

These incoming edges will be called X-edges, K-edges or L-edges accordingly.

The morphisms of T^{T_{f,g}} can be described in terms of generators and relations. There are three types of generators. First, we have the generators coming from the T -algebra structure on X-coloured edges, with a similar description as in T^{T+1}. The relations between these generators witness the relations between T -operations. The subcategory of T^{T_{f,g}} spanned by these generators coincides with T^{T+2}.

The next type of generators corresponds to the morphism f : K → L. Such a generator simply replaces a K-edge with an L-edge in the corolla. Generators of this kind will be called F -generators. The category T^{T_{f}} is precisely the subcategory of T^{T_{f,g}} generated by T^{T+2} and F -generators.

Finally, we have generators corresponding to g : K → U_{T} (X). Such a generator replaces a K-edge with an X-edge. Generators of this kind will be called G-generators. The category T^{T_{g}} is precisely the subcategory of T^{T_{f,g}} generated by T^{T+2} and G-generators.

The relations in T^{T_{f,g}} between the morphisms in T^{T+2}, the F -generators and the Ggenerators readily follow from the aforementioned description of T^{T_{f,g}}. Most importantly for us, every span b ←^{ϕ} a →^{ψ} a′ in which ϕ is an F -generator (resp. G-generator) and ψ belongs to T^{T+2}, extends to a commutative square

[figure: a; ψ; a′; b; ϕ; ψ′; b′; ϕ′]  (21)

in which ϕ′ is an F -generator (resp. G-generator) and ψ′ belongs to T^{T+2}. Indeed, F - (resp. G-)generators replace a K-edge by an L-edge (resp. X-edge), while the morphisms in T^{T+2} only affect X-edges. So, we can either first apply ψ and then replace the corresponding K-edge by an L-edge (resp. X-edge), or first apply ϕ and then apply the corresponding morphism in T^{T+2}.

A similar argument yields that every composite a →^{ϕ_{f}} b →^{ϕ_{g}} c of an F -generator ϕ_{f} followed by a G-generator ϕ_{g} can be rewritten

[figure: a; ϕ_{f}; b; b′; ϕ′_{g}; ϕ′_{f}; c; ϕ_{g}]  (22)

as the composite of a G-generator ϕ′_{g} followed by an F -generator ϕ′_{f}.

7.5. A final subcategory of T^{T_{f,g}}. Recall that a subcategory A of B is called final if the inclusion functor i : A ↪ B is a final functor. This means that for each object b of B, the undercategory b/A is non-empty and connected. Final subcategories have the characteristic property that for functors F : B → E with cocomplete codomain, the canonical map colim_{A}F i → colim_{B}F is an isomorphism.

The existence of a terminal object in B is equivalent either to the existence of a right adjoint for the unique functor B → 1 to the terminal category 1 or to the existence of an embedding of the terminal category 1 as a full and final subcategory of B. The following lemma is a “several component” version of this observation.

7.6. Lemma. For any category B the following three conditions are equivalent:

(i) B is a coproduct of categories with terminal object;

(ii) B has a full subcategory which is discrete and final;

(iii) The connected component functor B → π_{0}(B) has a right adjoint.

In particular, if a reflective subcategory A of B satisfies one of the equivalent conditions (i)-(iii) then so does B.

Proof. The equivalence of conditions (i)-(iii) follows like in the connected case.

For the second assertion observe that the composite of two full and final inclusions is again a full and final inclusion, and that the inclusion of a reflective subcategory is a full right adjoint (and hence final) functor. Therefore B inherits property (ii) from A.

7.7. Lemma. For any tame polynomial monad T, the categories T^{T+2}, T^{T_{f}}, T^{T_{g}} are coproducts of categories with terminal object.

Proof. The explicit descriptions of the categories T^{T+1} and T^{T+2} in Sections 6.20 and 7.4 show that T^{T+1} is the full subcategory of T^{T+2} spanned by those corolla which do not contain any L-edges. This inclusion has a retraction r : T^{T+2} → T^{T+1} which preserves the arities of the corollas as well as the distinction between X- and non-X-edges, but takes K- and L-edges of a corolla in T^{T+2} to K-edges of the image-corolla in T^{T+1}. Each morphism g : b′ → b in T^{T+2} induces a bijection between the K-edges of b′ and of b, and a bijection between the L-edges of b′ and of b. A morphism g : b′ → b is completely determined by these two bijections and its image r(g) : r(b′) → r(b) in T^{T+1}. This implies that the restriction of r to a connected component of T^{T+2} is fully faithful and bijective on objects, and takes thus a connected component of T^{T+2} isomorphically to the corresponding connected component of T^{T+1}. Therefore, since by tameness the category T^{T+1} is a coproduct of categories with terminal object, the same holds for T^{T+2}.

The category T^{T_{f}} contains a reflective subcategory isomorphic to T^{T+1}, namely the subcategory spanned by those corollas in T^{T_{f}} which have only X- and L-edges. The reflection of an object of T^{T_{f}} to this subcategory is given by successive applications of F -generators replacing all K-edges with L-edges. According to Lemma 7.6, this implies that T^{T_{f}} is a coproduct of categories with terminal object.

The category T^{T_{g}} also contains a reflective subcategory isomorphic to T^{T+1}, namely the subcategory spanned by those corollas in T^{T_{g}} which have only X- and L-edges. This time, the G-generators define the reflection. According to Lemma 7.6, this again implies that T^{T_{g}} is a coproduct of categories with terminal object.

Let t_{0} be a final discrete full subcategory of T^{T+2} obtained by choosing a terminal object in each connected component of T^{T+2} (cf. Lemma 7.7). We define t to be the full subcategory of T^{T_{f,g}} spanned by the objects of t_{0}. In other words, the composite inclusion t_{0} ↪ T^{T+2} ↪ T^{T_{f,g}} can be written as

t_{0} ↪^{H} t ↪^{E} T^{T_{f,g}}

where H is the identity on objects and E is a full inclusion.

7.8. Lemma. The category t is a final subcategory of T^{T_{f,g}}.

Proof. Since the categories T^{T+2} and T^{T_{f,g}} have the same objects, the very definition of t_{0} implies that each object a in T^{T_{f,g}} maps to a uniquely determined object t_{a} in t_{0} by a unique map a → t_{a} in T^{T+2}. Since t_{0} is a subcategory of t, this shows that the undercategory a/t contains at least a → t_{a} and is thus non-empty. We shall show that in a/t any object a → b is in the same connected component as a → t_{a} using an induction on the number of K-edges in the corolla representing a.

If a has no K-edges then all morphisms a → b belong to T^{T+2}, so that a/t contains just the canonical morphism a → t_{a}, and there is nothing to prove. Assume now that a has p K-edges with p > 0 and that we have already shown that a/t is connected for all objects a with less than p K-edges.

Consider an arbitrary object ϕ : a → b of a/t. In general, the morphisms in T^{T_{f,g}} are generated by the morphisms in T^{T+2}, the F -generators and the G-generators, see Section 7.4. If ϕ itself belongs to T^{T+2} then, since b is an object of t_{0}, one has necessarily b = t_{a} and ϕ coincides with the canonical morphism a → t_{a}.

If ϕ does not belong to T^{T+2} then ϕ = ϕ_{2}ϕ_{1} where ϕ_{1} or ϕ_{2} is an F -generator or a G-generator. The relations (21) and (22) between the different generators of T^{T_{f,g}} imply that we can assume that it is ϕ_{1} which is a F - or G-generator. Since F - and G-generators decrease the number of K-edges, the codomain of ϕ_{1} : a → a′ has less than p K-edges. Therefore, by induction hypothesis, the object ϕ_{2} : a′ → b is in the same connected component as a′ → t_{a′} in a′/t. This implies that ϕ_{2}ϕ_{1} : a → a′ → b is in the same connected component as a → a′ → t_{a′} in a/t.

Applying the relation (21) to the span t_{a} ← a →^{ϕ_{1}} a′ we get a commutative square

[figure: a; ϕ_{1}; a′; t_{a}; ϕ′_{1}; b′]

where a′ → b′ is in T^{T+2}. Since b′ is in the same connected component as a′ there is a canonical morphism b′ → t_{a′}. Hence we have a commutative square in T^{T_{f,g}}

[figure: a; ϕ_{1}; a′; t_{a}; t_{a′}]

This shows that in a/t the (arbitrarily chosen) object ϕ : a → b is in the same connected component as the canonical object a → t_{a}.

7.9. Canonical filtration. We say that an object a of t is of type (p, q) if a contains exactly p K-edges and q L-edges, and we call p + q the degree of a. We define t^{(k)} (resp. w^{(k)}) to be the full subcategory of t spanned by all objects of degree ≤ k (resp. of degree k). We define q^{(k)} (resp. l^{(k)}) to be the full subcategory of w^{(k)} spanned by all objects of type (p, k − p) such that p ≠ 0 (resp. p = 0).

Recall that the (categorical) k-cube is the category of subsets and inclusions of the set {1, …, k}. The punctured k-cube is the full subcategory of the k-cube spanned by the proper subsets of {1, …, k}.

7.10. Lemma. –

(i) Each connected component of w^{(k)} is isomorphic to a k-cube;

(ii) the category l^{(k)} is a final discrete full subcategory of w^{(k)}.

(iii) the category q^{(k)} is isomorphic to a coproduct of punctured k-cubes.

Proof. Note first that the morphisms in w^{(k)} cannot involve G-generators since the latter decrease the degree; therefore, they necessarily belong to T^{T_{f}}. Since the objects in t are terminal in their connected component in T^{T+2}, the non-identity morphisms of w^{(k)} cannot belong to T^{T+2} either; therefore, all morphisms in w^{(k)} are composites of F -generators. Recall that each F -generator replaces a K-edge with an L-edge. From this it readily follows that the connected components of w^{(k)} are k-cubes. The assertions (ii) and (iii) are immediate consequences of (i).

7.11. Theorem. For any tame polynomial monad T and any functor X : T^{T_{f,g}} → E with cocomplete codomain, the colimit of X is a sequential colimit of pushouts in E.

More precisely, for P_{k} = colimt_{(k)}X|t_{(k)}, we get

P = colimT_{T_{f,g}}X ≅ colim_{k}P_{k},

where the canonical map P_{k−1} → P_{k} is part of the following pushout square in E

[figure: Q_{k}; w_{k}; L_{k}; P_{k−1}; α_{k}; P_{k}]  (23)

in which Q_{k} (resp. L_{k}) is the colimit of the restriction of X to q^{(k)} (resp. l^{(k)}).

Proof. The finality of t implies P = colimT_{T_{f,g}}X ≅ colimtX. It is obvious that t ≅ colim_{k}t^{(k)}. Lemmas 7.8 and 7.13 then yield P ≅ colimtX|t ≅ colim_{k}P_{k}.

The inclusion q^{(k)} ↪ w^{(k)} induces the map w_{k} : Q_{k} → colimw_{(k)} X̃|w_{(k)} ≅ L_{k} where the last isomorphism is a consequence of Lemma 7.10(ii).

In order to construct the map α_{k} : Q_{k} → P_{k−1} we shall realise t^{(k−1)} as a final subcategory of a category \overline{q}^{(k)} which contains q^{(k)}. The map α_{k} is then simply induced by the inclusion q^{(k)} ↪ \overline{q}^{(k)}. This category \overline{q}^{(k)} is by definition the full subcategory of t^{(k)} spanned by the objects not contained in l^{(k)}.

To prove that t^{(k−1)} is a final subcategory of \overline{q}^{(k)} note first that each object a of \overline{q}^{(k)} comes equipped with a canonical map ξ_{a} : a → j(a), where j(a) is terminal in the connected component of a in T^{T_{g}}, and hence ξ_{a} : a → j(a) is the unique morphism in T^{T_{g}} with codomain j(a), cf. Lemma 7.7. In particular, j(a) belongs t^{(k−1)} because a contains at least one K-edge and G-generators decrease the degree.

It suffices now to show that each object a → c of a/t^{(k−1)} lies in the same connected component as ξ_{a} : a → j(a). If a → c belongs to T^{T_{g}} this holds trivially since j(a) is terminal in its connected component in T^{T_{g}}. Assume that a → c does not belong to T^{T_{g}}. We then factor a → c as a → b → c where a → b is a composite of F -generators and b → c belongs to T^{T_{g}}; in other words, we perform all replacements (inside a → c) of a K-edge with an L-edge first, and perform the replacements of a K-edge with an X-edge only afterwards. This is always possible due to relations between the generating morphisms of T^{T_{f,g}}, cf. Section 7.4.

Since b → c belongs to T^{T_{g}} and the codomain c belongs to t^{(k−1)}, the domain b cannot belong to l^{(k)} so that we have a canonical map ξ_{b} : b → j(b) whose codomain belongs to t^{(k−1)}. Since b → c belongs to T^{T_{g}} and j(b) is terminal in its connected component of T^{T_{g}} we have a factorisation of ξ_{b} as b → c → j(b). It thus suffices to construct a zig-zag in

a/t^{(k−1)} connecting a → b →^{ξ_{b}} j(b) and a →^{ξ_{a}} j(a).

It also suffices to assume that the morphism a → b is equal to one of the F -generators f_{v} : a → b which replaces a K-edge v by a L-edge. Observe that the morphism ξ_{a} : a → j(a) can be factorised as

a →^{g} a′ →^{g_{v}} a′′ →^{m} j(a),

where g is a composite of G-generators which replaces all K-edges by X-edges except the K-edge v, g_{v} is a G-generator which replaces K-edge v by an X-edge, and m belongs to T^{T+2}.

The morphism ξ_{b} : b → j(b) can also be factored as

b →^{g′} b′ →^{m′} j(b),

where g′ is a composite of G-generators which replaces all K-edges by X-edges and m′ belongs to T^{T+2}. Moreover, the following diagram commutes

[figure: a; g; a′; b; f_{v}; g′; b′; f′_{v}]

where the morphism f′_{v} is a F -generator which replaces the K-edge v by an L-edge.

Since F -generators commute with the morphism from T^{T+2} we obtain the following commutative diagram

[figure: a′; m′′; a′′′; b′; f′_{v}; m′; j(b); f′′_{v}]

in which f′′_{v} is an F -generator and m′′ belongs to T^{T+2}. Observe, that a′′′ belongs to t^{k−1} since it is obtained from j(b) by replacing an L-edge by a K-edge.

Finally we observe, that a, a′, a′′, a′′′ are in the same connected component of T^{T_{g}} by construction and since j(a) is terminal in this connected component we have a commutative diagram

[figure: a′; g_{v}; a′′; a′′′; m′′; j(a)]

Putting all these morphisms together we get a commutative diagram in a/t^{(k−1)}

a
[figure]
[figure: b; b′; a′; a′′; j(a)]
[figure]
[figure: j(b); a′′′]

which provides us with the necessary zigzag.

It follows from the preceding discussion that diagram (23) may be obtained by restricting X : T^{T_{f,g}} → E to the following commutative square of categories

[figure: q^{(k)}; w^{(k)}; \overline{q}^{(k)}; t^{(k)}]  (24)

and then computing the colimits of the corresponding restrictions. This yields commutativity of square (23) as well as a canonical map P_{k−1} ∪_{Q_{k}} L_{k} → P_{k} in E. It remains to be shown that the latter map is invertible, i.e. that square (23) is a pushout diagram in E.

A closer inspection of square (24) reveals that it is a categorical pushout of a special kind: the category t^{(k)} is obtained as the set-theoretical union of the categories \overline{q}^{(k)} and w^{(k)} along their common intersection q^{(k)}. Indeed, away from this intersection, there are no morphisms in t^{(k)} between objects of \overline{q}^{(k)} and objects of w^{(k)}. In virtue of Lemma 7.13 this implies that (23) is a pushout square in E.

7.12. Remark. In our particular situation, the inverse of P_{k−1} ∪_{Q_{k}} L_{k} → P_{k} is obtained by gluing together (along q^{(k)}) the two colimit cocones X|\overline{q}_{(k)} ⟶^{·} P_{k−1} and X|w_{(k)} ⟶^{·} L_{k} and taking the colimit of X over t^{(k)}.

We are indebted to Steve Lack for pointing out to us a proof of the following categorical fact. Let 𝔻 be a small category and let Φ : 𝔻 → Cat be a 𝔻-diagram of small categories. We denote by ℂ the colimit of this diagram, and by Φ(d) → ℂ the components of the corresponding colimit cocone. Let X : ℂ → E be a functor with cocomplete codomain. For each object d of 𝔻 we consider the restriction X_{d} : Φ(d) → ℂ → E and its colimit colim_{Φ(d)}X_{d} in E. This defines a functor colim_{Φ(−)}X_{−} : 𝔻 → E.

7.13. Lemma. The induced map colim_{𝔻}colim_{Φ(−)}X_{−} → colim_{ℂ}X is an isomorphism in E.

Proof. Consider the slice category Cat/E. There is a functor γ : Cat/E → E which takes the objects of the slice category to their colimit in E. We have to show that γ preserves colimits. We actually show that γ has a right adjoint. For this we observe that γ can be factored as follows:

Cat/E →^{i} Cat//E ⟶^{γ′} E

where Cat//E denotes the lax version of the slice category. In Cat//E the morphisms from F to G are pairs (f, ϕ) defining triangles of the following form:

𝔸  \overline{f  ^{}}𝔹
[figure: F; ⇒^{ϕ}; G]
E

The functor i is the obvious inclusion functor and γ′ is again given by taking objectwise the colimit. Both functors i and γ′ have right adjoints. The right adjoint of γ′ takes an object of E to the functor 1 → E which picks up this object. The right adjoint of i is the lax-limit functor given by a Grothendieck type construction. For a functor F : 𝔸 → E this Grothendieck construction P (F) is the category whose objects are pairs (a, α) consisting of an object a of 𝔸 and a morphism α : F (a) → x in E. The morphisms (a, α) → (b, β) in P (F) are pairs (a → a′, x → x′) such that an obvious diagram commutes. There is a functor P (F) → E which takes (a, α) to the codomain of α in E. It is straightforward to check that this construction provides a right adjoint for i.

8. Admissibility of tame polynomial monads and Quillen adjunctions

We are now ready to combine the results of Sections 2, 5, 6 and 7 so as to obtain the two main theorems of this article.

Throughout this section E denotes a monoidal model category and I a set of colours. The category E/I is then a monoidal model category in which the cofibrations, weak equivalences and fibrations are defined pointwise, and the monoidal structure as well is defined pointwise.

8.1. Theorem. Let (E, ⊗, e) be a compactly generated monoidal model category and let T be a tame polynomial monad on Set/I. Then E/I is a compactly generated monoidal model category, and the monad on E/I induced by T is

(a) relatively ⊗-adequate if E satisfies the monoid axiom;

(b) ⊗-adequate if E is strongly h-monoidal.

Therefore, the category of T -algebras in E/I admits a relatively left proper transferred model structure if E satisfies the monoid axiom (resp. a left proper transferred model structure, if E is strongly h-monoidal).

Proof. The cartesian monad morphism Φ of Proposition 7.2(iii) from T_{f,g} to T induces an adjunction

γ_{E}^{Φ} : Alg_{T_{f,g}}(E) ⇆ Alg_{T} (E) : δ_{E}^{Φ}

whose left adjoint takes the quintuple (X, K, L, f, g) to the pushout P in E. Theorem 6.17 implies that the underlying object of P can be calculated as the colimit of a functor X̃ : T^{T_{f,g}} → E. Theorem 7.11 permits us to realise this colimit as a sequential colimit of pushouts.

From a homotopical point of view it is essential that the sequential colimit presentation of P is made up by pushouts of maps w_{k} : Q_{k} → L_{k} which are easy to calculate. Indeed, the functor X̃ : T^{T_{f,g}} → E takes the values

X̃(a) = (⊗_{v∈χ(a)}X_{v}) ⊗ (⊗_{v∈κ(a)}K_{v}) ⊗ (⊗_{v∈λ(a)}L_{v}),  (25)

cf. formula (15). Here, χ(a) is the set of X-edges, κ(a) is the set of K-edges, and λ(a) is the set of L-edges in the corolla representing a. The F -generators of T^{T_{f,g}} act via the map f : K → L, the G-generators act via the map g : K → U_{T} (X), the morphisms in T^{T+2} act via the T -algebra structure on X. Note that by Lemma 7.10 the map w_{k} : Q_{k} → L_{k} is a coproduct of comparison maps. Each comparison map is obtained by taking the colimit over a punctured k-cube (a connected component of q^{(k)}) in which the edge-maps are tensor products Y ⊗ f_{v} where f_{v} : K_{v} → L_{v}.

Now we can closely follow the proof of Theorem 3.1 which describes the special case of the free monoid monad. Indeed, formula (25) indicates that the only qualitative difference between a general tame polynomial monad and the free monoid monad lies in the fact that the map w_{k} : Q_{k} → L_{k} is in general a coproduct of comparison maps while in the special case treated in Theorem 3.1 we have just a single comparison map. Since (trivial) cofibrations as well as weak equivalences between cofibrant objects are closed under arbitrary coproducts, this difference does not affect the argument establishing (a). However, to carry out the proof of (b) for a general tame polynomial monad, we need the additional property that the class of weak equivalences is closed under arbitrary coproducts. This follows from Proposition 2.5 because E is strongly h-monoidal, cf. Section 1.20.

Let Φ : S ⇒ dT c be a cartesian monad morphism, cf. Definition 5.7. Assume that the categories of S- and T -algebras in E admit transferred model structures (e.g., S and T are tame polynomial and E is compactly generated h-monoidal). By Theorem 6.17, restriction δ_{E}^{Φ} admits a left adjoint γ_{E}^{Φ}. The resulting adjoint pair

γ_{E}^{Φ} : Alg_{S}(E) ⇆ Alg_{T} (E) : δ_{E}^{Φ}

is a Quillen pair with respect to the transferred model structures on both sides. We shall see now that the total left derived functor 𝕃γ_{E}^{Φ} has an explicit formula in terms of the combinatorial data defining Φ, provided that the monoidal model category E admits a good realisation functor |−|_{E} for simplicial objects.

One way to obtain such a realisation functor is to require that E is simplicially enriched in such a way that simplicial hom E_{•}(−, −) and internal hom \underline{E}(−, −) are related by the following compatibility relation

E_{•}(X, Y) ≅ E_{•}(e, \underline{E}(X, Y)),

and moreover E equipped with these simplicial hom’s becomes a simplicial model category, cf. [36, 37]. The compatibility relation implies that the category Alg_{T} (E) of T -algebras is simplicially enriched, and that the free-forgetful adjunction is a simplicial adjunction. The simplicial hom for the category of T -algebras is given by the usual formula involving a categorical end (see for instance [5]).

More generally, in order to have a good realisation functor for simplicial objects, it is enough to assume that E has a standard system of simplices in the sense of Moerdijk and the second author, cf. [12, Appendix A]. We then have the following derived version of Theorem 6.17.

8.2. Theorem. Let E be a monoidal model category with a “good” realisation functor |−|_{E} for simplicial objects, and let Φ : S ⇒ dT c be a cartesian monad morphism between polynomial monads. Let X be an S-algebra in E whose underlying J-collection is pointwise cofibrant. Then the I-collection underlying 𝕃γ_{E}^{Φ}(X) can be calculated as the following homotopy colimit

𝕃γ_{E}^{Φ}(X)_{i} = hocolim_{b∈T_{i}^{S}}X̃(b)  (i ∈ I)  (26)

where X̃ : T^{S} → E represents the S-algebra X, cf. Section 6.16.

Proof. Let B_{•}(S, S, X) be the simplicial bar-construction of the S-algebra X. Its realisation B(S, S, X) = |B_{•}(S, S, X)|_{E} is a cofibrant resolution of the S-algebra X with respect to the transferred model structure on Alg_{S}(E). This follows from a similar argument as for [5, Theorem 5.5], once we know that the following augmented cosimplicial object in E

(27)

[figure: X; S(X); S^{3}(X); S^{2}(X); …]

is Reedy cofibrant. In this cosimplicial object the cofaces are generated by the unit of the monad S and the codegeneracies are generated by the multiplication of S.

The unit η : Id_{J} → S is a cartesian map of polynomial monads. The category of J-collections in E can be identified with the category of Id_{J}-algebras so that η induces the free-forgetful adjunction between J-collections and S-algebras, whence the monad S = U_{S}F_{S} can be rewritten as δ_{E}^{η}γ_{E}^{η}. Theorem 5.14 implies that the adjoint pair (γ_{E}^{η}, δ_{E}^{η}) is represented by the adjoint pair ((S^{η})_{!}, (S^{η})^{∗}) where S^{η} : S^{Id_{J}} → S^{S} is the functor of classifiers induced by η : Id_{J} → S, and J-collections (resp. S-algebras) are represented by functors S^{Id_{J}} → E (resp. S^{S} → E).

The category S^{Id_{J}} has the same objects as S^{S} but only identity morphisms, and the functor S^{η} : S^{Id_{J}} → S^{S} is identity on objects. The explicit formula for the left Kan extension (S^{η})_{!} produces then for any S-algebra X, represented as a functor X̃ : S^{S} → E, the following formula for the iteration of the monad S

{ \atop S^{k}(X)}(d) = ((S^{η})_{!}(S^{η})^{∗})^{k}(X̃)(d) = ∐_{d←d_{1}←··· ←d_{k}} X̃(d_{k}),

where the coproduct is taken over composable chains of morphisms in S^{S}.

Evaluating this formula at the terminal objects 1_{j} of S_{j}^{S} we obtain

S^{k}(X)_{j} = (F_{S}U_{S})^{k}(X)_{j} = ∐_{d_{1}←··· ←d_{k}} X̃(d_{k}) (d_{1}, …, d_{k} ∈ S_{j}^{S}).

The unit of the monad U_{S}F_{S} is the canonical summand inclusion X_{j} → ∐_{d} X̃(d) which takes X_{j} to X̃(1_{j}) = X_{j}. Therefore, the latching object of (27) in dimension k is the coproduct of the X̃(d_{k}) over degenerate k-simplices of the nerve of S^{S}. Since the underlying J-collection of the S-algebra X is pointwise cofibrant, all summands X̃(d) are cofibrant, and hence the inclusion of the latching object is a cofibration. It follows that B(S, S, X) is a cofibrant resolution of the S-algebra X so that the value of the total left derived functor 𝕃γ_{E}^{Φ} can be calculated as

𝕃γ_{E}^{Φ}(X) = γ_{E}^{Φ}(B(S, S, X)) = γ_{E}^{Φ}|B_{•}(S, S, X)|_{E} = |γ_{E}^{Φ}(B_{•}(S, S, X))|_{E}.

The simplicial T -algebra γ_{E}^{Φ}(B_{•}(S, S, X)) is isomorphic to

(28)

[figure: γ_{E}^{Φ}(S(X)); γ_{E}^{Φ}(S^{3}(X)); γ_{E}^{Φ}(S^{2}(X)); …]

and, by Theorem 6.17, the underlying object in dimension k is given by the formula

γ_{E}^{Φ}(S^{k}(X))_{i} = colim_{b∈T_{i}^{S}}{ \atop S^{k}(X)}(b) (i ∈ I),  (29)

where this time S-algebras are represented as functors from T^{S} to E.

To finish the proof we therefore need a presentation of the iterations of the comonad F_{S}U_{S} on Alg_{S}(E) in terms of the relative classifier T^{S}. For ease of notation, we will use the same letter S for the comonad F_{S}U_{S}.

Consider the following commutative triangle of polynomial monads

[figure: Id_{J}; T; S; η; Φ]

and use Theorem 5.15 to get

{ \atop S(X)} = { \atop γ_{E}^{η}δ_{E}^{η}(X)} = (T^{η})_{!}{ \atop δ_{E}^{η}(X)} = (T^{η})_{!}(T^{η})^{∗}(X̃)

and hence

{ \atop S^{k}(X)} = ((T^{η})_{!}(T^{η})^{∗})^{k}(X̃).

The canonical functor T^{η} : T^{Id_{J}} → T^{S} is the inclusion of the discrete subcategory of objects of T^{S}, so that we obtain (in a similar way as above) the formula

{ \atop S^{k}(X)}(b) = ∐_{b←b_{1}←···←b_{k}} X̃(b_{k})  (30)

where this time the coproduct is over composable chains of morphisms in T^{S}.

Let t_{i} : T_{i}^{S} → 1 be the unique functor to the terminal category. Putting formulas (29) and (30) together we obtain

γ_{E}^{Φ}(S^{k}(X))_{i} = colim_{b∈T_{i}^{S}}{ \atop S^{k}(X)}(b) = (t_{i})_{!}((T^{η})_{!}(T^{η})^{∗})^{k}(X̃)
= (t_{i}T^{η})_{!}(T^{η})^{∗}((T^{η})_{!}(T^{η})^{∗})^{k−1}(X̃) = ∐_{b_{1}←···←b_{k}} X̃(b_{k}).

We conclude that the simplicial object γ_{E}^{Φ}(B_{•}(S, S, X)) may be identified with the classical simplicial replacement of Bousfield-Kan for the functor X̃ : T^{S} → E representing the S-algebra X. By hypothesis, this functor is pointwise cofibrant so that the Bousfield-Kan simplicial replacement calculates the homotopy colimit of X̃ upon realisation.

8.3. Remark. The simplicial T -algebra γ_{E}^{Φ}(B_{•}(S, S, X)) is isomorphic to

[figure: T c(X); T cS^{2}(X); T cS(X); …]

where c : E/J → E/I is induced by the cartesian morphism of polynomial monads Φ from S to T (see Section 6.14). In particular, we recognise here the two-sided simplicial bar-construction B_{•}(T c, S, X), and hence we get the formula

𝕃γ_{E}^{Φ}(X) ≅ |B_{•}(T c, S, X)|_{E}.

8.4. Corollary. The simplicial nerve N(T^{S}) of the S-algebra classifier T^{S} is a cofibrant simplicial T -algebra. In fact,

N(T^{S}) = 𝕃γ_{E}^{Φ}(1)

where E is the category of simplicial sets equipped with Quillen’s model structure, and 1 is the terminal simplicial S-algebra.

8.5. Remark. Theorem 8.2 and Corollary 8.4 generalise formulas of [5, 6] where the symmetrisation functor from n-operads to symmetric operads has been studied. Theorem 8.2 is one of the main tools in the study of stabilisation phenomena in [8, 9].

8.6. Remark. Giansiracusa’s formula [27] for the derived modular envelope of a cyclic operad can be understood along similar lines. For the precise relationship with the present approach we refer the reader to [67, Example 3.4.3].

Part III

Operads as algebras over polynomial monads

Symmetric, non-symmetric, cyclic, modular operads, properads, PROP’s, the higher operads of the first author, and other types of generalised operads (see [16, 46, 44, 32]) are examples of algebras over polynomial monads. In this part we study these examples in some detail and investigate whether the corresponding polynomial monad is tame or not. We pay a particular attention to the polynomial monad for n-operads for reasons explained in the introduction to this article. This special case turns out to be the most intricate one with respect to tameness.

In each case, the definition of the generating polynomial necessitates a rigorous definition of a certain class of graphs, together with the appropriate notion of graph insertion. This graph insertion is responsible for the multiplication of the associated polynomial monad. We refer the reader to Part 4 for our terminology and conventions concerning graphs, trees and graph insertion.

9. Operads based on contractible graphs

9.1. Diagram categories. As a first example of tame polynomial monad we consider ‘linear’ monads. These are polynomial monads for which the middle map is the identity:

I ^{_{}s}  B  \overline{id ^{}}B t^{}I.

The category of linear monads is isomorphic to the category of small categories. If C is a linear monad and ℂ the corresponding small category then the category of algebras over C is the category of diagrams [ℂ, E]. To see that any linear monad is tame we need to compute the classifier C^{C+1}. Let i be an object of ℂ. The objects of C^{C+1}(i) are morphisms f : j → i coloured by two colours X or K. A (non-identity) morphism from f : j_{1} → i to g : j_{2} → i can exist only if f and g both have colour X and there is a morphism h : j_{1} → j_{2} in ℂ such that f = g · h. In other words, the semi-free coproduct classifier C^{C+1}(i) is isomorphic to a coproduct of overcategories ℂ/i together with a coproduct of as many terminal categories as there are non-identity morphisms in ℂ. Since each overcategory ℂ/i has a terminal object we conclude that the linear monad C is tame.

9.2. Monoids and non-symmetric operads. Let M be free monoid monad on Set. It is a polynomial monad generated by the following polynomial

                 1 ^{_{}s} LinearTrees^{∗} \overline{p_{}}LinearTrees  t^{}1

in which LinearTrees is the set of (isomorphism classes of finite) linear rooted trees, and LinearTrees^{∗} is the set of (isomorphism classes of finite) linear rooted trees with one marked vertex. The mapping p forgets the marking. The multiplication of M is induced by insertion of linear trees into vertices of linear trees. The category M^{M+1} can be described as follows, cf. Section 6.20.

The objects of M^{M+1} are corollas with vertex decorated by a linear tree and edges coloured by X or K. The edges of the corolla correspond to vertices of the decorating tree. Therefore, such a corolla can be considered as a linear tree with vertices labelled by X or K. The morphisms of M^{M+1} are generated by contractions of linear subtrees with X-coloured vertices to a single X-coloured vertex

[figure: K; X; X; K; X; K; X; K; X]

and insertions of a single X-coloured vertex into an edge:

[figure: K; K; X; K; X; K; X]

Obviously, every connected component of M^{M+1} contains a terminal object which is a linear tree the vertices of which have alternating colours starting with X and terminating with X:

[figure: K; X; K; X; X]

Hence, the free monoid monad M is tame and we obtain in particular formula (1) of the introduction.

Moreover, the objects of the final subcategory t of M^{M_{f,g}} (cf. Lemma 7.8) are linear trees with vertices coloured by X, K, L such that

• first and last vertex are coloured by X;

• adjacent vertices have different colours;

• no edge connects a K-vertex with an L-vertex.

Let X = (R, Y_{0}, Y_{1}, u, α) be a M_{f,g}-algebra, i.e. the data for a pushout along a free map in the category of monoids (see the proof of Theorem 3.1). Then, according to formula (25) the functor X̃ takes on a typical object of t the value

R ⊗ Y_{i_{1}} ⊗ R ⊗ Y_{i_{2}} ⊗ ⋯ ⊗ Y_{i_{k}} ⊗ R

where (i_{1}, …, i_{k}) is a vertex of a punctured k-cube. We thus obtain the Schwede-Shipley formula (6) as a special instance of Theorem 7.11 (cf. also [60, pg. 10]).

The polynomial monad for non-symmetric operads monad is generated by the following polynomial

         [figure: ℕ_{0}; s; PlanarRootedTrees^{∗}; p; PlanarRootedTrees; t; ℕ_{0}]

in which ℕ_{0} denotes the set of natural numbers including 0; PlanarRootedTrees denotes the set of isomorphism classes of planar rooted trees. The elements of PlanarRootedTrees^{∗} are elements of PlanarRootedTrees with an additional marking of one vertex. The mapping p forgets this marking. The target map takes a planar tree to the cardinality of the set of its leaves and the source map takes a tree S with marked vertex v to the cardinality of the set of leaves of the corolla cor_{v}(S) surrounding the vertex v in S. The multiplication of the polynomial monad is induced by insertion of planar rooted trees into vertices of planar rooted trees.

The polynomial monad O(1) for non-symmetric operads is tame for similar reasons as in the preceding example. The objects of O(1)^{O(1)+1} are planar rooted trees the vertices of which are coloured by X and K. Morphisms in O(1)^{O(1)+1} are generated by contractions of a subtree with X-coloured vertices to a single X-coloured vertex, and by insertion of a single X-coloured vertex into an edge. A typical terminal object in a connected component of O(1)^{O(1)+1} is a planar rooted tree with vertices coloured by X and K such that adjacent vertices have different colours, and such that vertices incident to the root or to the leaves are X-coloured. For instance, a tree of the following form is terminal in its connected component:

[figure: K; K; X; X]

There is also a corresponding description for the final subcategory t of the free nonsymmetric operad extension classifier O(1)^{O(1)_{f,g}}. As an instance of our Theorem 7.11 we obtain Muro’s formula [52] for free non-symmetric operad extensions.

9.3. Remark. We can introduce a coloured version for the polynomial monads above. For this we need to use graphs whose edges are coloured by some set of colours I. The coloured version of the free monoid monad gives the monad for categories with fixed object-set I. Algebras over this monad in a symmetric monoidal category E are precisely E-enriched categories with object-set I. Similarly, the coloured version of the monad for non-symmetric operads is the monad for multicategories with fixed object-set. These monads are tame by the same argument as for their single-coloured counterparts. A similar remark applies for all other polynomial monads of this article. We will thus not anymore mention the coloured versions.

9.4. Symmetric operads. The monad for symmetric operads [15, 49] is generated by the following polynomial

        [figure: ℕ_{0}; s; OrderedRootedTrees^{∗}; p; OrderedRootedTrees; t; ℕ_{0}]

in which OrderedRootedTrees is the set of isomorphism classes of ordered rooted trees. Such an isomorphism class is represented by a planar rooted tree together with an ordering of its leaves. The structure maps of this polynomial monad are defined in a similar fashion as those of the polynomial monad for non-symmetric operads.

9.5. Definition. A vertex v of a rooted tree is called non-degenerate (resp. normal) if the set of incoming edges of v is non-empty (resp. of cardinality at least 2).

A tree is called regular (resp. normal) if its vertices are non-degenerate (resp. normal). A tree T is called non-degenerate if the set of its leaves is non-empty and any nondegenerate vertex belongs to a linear subtree containing a leaf of the tree.

There is a polynomial monad for constant-free symmetric operads. These are symmetric operads without constant operations. The generating polynomial is

      [figure: ℕ; s; OrderedRootedTrees_{reg}^{∗}; p; OrderedRootedTrees_{reg}; t; ℕ]

where everything is defined as above except that we restrict to regular ordered rooted trees.

One can also define a polynomial monad for normal symmetric operads. These are constant-free symmetric operads with a unique unary operation, i.e. the object of operations of arity 1 is the tensor unit e of E. The generating polynomial of the monad for normal symmetric operad is

      [figure: ℕ; s; OrderedRootedTrees_{nor}^{∗}; p; OrderedRootedTrees_{nor}; t; ℕ]

everything being defined as above except that we restrict to normal ordered rooted trees.

The polynomial monad for constant-free symmetric operads is tame. In an implicit manner, this was first observed by Getzler-Jones [25, Section 1.5]. As in the nonsymmetric case one can characterise the terminal object in each connected component of the internal algebra classifier as alternating trees with two colours X and K (see Section 9.4). The polynomial monads for normal symmetric operads are also tame. However, the polynomial monad for general symmetric operads is not tame. The following tree

[figure: K; K; X]

is the only candidate for a terminal object in one of the connected components of corresponding internal algebra classifier but it has a non-trivial automorphism coming from a 𝕊_{2}-action on X_{2}, and so, it can not be terminal. There is an obstruction for the existence of model structure on symmetric operads with coefficient in chain complexes over a field of positive characteristic, similarly to (12.30), which was first described by Fresse [22].

9.6. Remark. Symmetric operads are often supposed to be 0-reduced, i.e. to have a unique constant (the monoidal unit e) in arity 0. It seems unlikely that 0-reduced symmetric operads are the algebras for a polynomial monad in sets. We are grateful to Giovanni Caviglia for having pointed this out. There is nevertheless a way of dealing with 0-reduced symmetric operads from a polynomial monad point of view.

Let us call reduced symmetric operad any algebra for the polynomial monad generated by the following polynomial

       [figure: ℕ; s; OrderedRootedTrees_{nd}^{∗}; p; OrderedRootedTrees_{nd}; t; ℕ]

where OrderedRootedTrees_{nd} is the set of isomorphism classes of non-degenerate ordered rooted trees and OrderedRootedTrees_{nd}^{∗} is the set of elements of OrderedRootedTrees_{nd} with one non-degenerate vertex marked (cf. Definition 9.5). The reader should observe that non-degenerate trees can have degenerate vertices. The structure maps of this polynomial are induced by substitution of non-degenerate trees into marked vertices of non-degenerate trees, much like above. In virtue of the existing input leaves in any non-degenerate tree, the polynomial monad for reduced symmetric operads is tame.

We denote by E/e the category of objects of E which are augmented over the monoidal unit e. The category of reduced symmetric operads in E/e contains then the category of 0-reduced symmetric operads in E as a full subcategory, cf. Fresse [23, Theorem 2.2.18]. Reduced symmetric operads have the advantage over 0-reduced symmetric operads to be algebras for a tame polynomial monad in sets. A similar observation applies to graphical PROP’s versus Adams-Mac Lane PROP’s, cf. Remark 10.5.

9.7. Planar cyclic and cyclic operads. The generating polynomial of the monad for cyclic operads is

              [figure: ℕ; s; OrderedTrees^{∗}; p; OrderedTrees; t; ℕ]

where OrderedTrees is the set of isomorphism classes of ordered (non-rooted) trees. In the generating polynomial of the monad for planar cyclic operads the set OrderedTrees has to be replaced with the set OrderedPlanarTrees of isomorphism classes of ordered planar trees. Neither of these three polynomial monads is tame for similar reasons as above. Nevertheless we have

9.8. Proposition. The polynomial monad for normal (constant-free, reduced) cyclic (resp. planar cyclic) operads is tame.

Proof. The terminal objects in the connected components of the internal algebra classifier can be characterised as alternating coloured trees much as in the case of the monad for non-symmetric operads.

9.9. Dioperads and \frac{1}{2}PROP’s. Instead of going into details we refer the reader to [46] for precise definitions. We just mention that the polynomial monad for dioperads is based on the class of contractible ordered graphs while the monad for \frac{1}{2}PROP’s is based on the class of those ordered contractible graphs, called \frac{1}{2}-graphs, which are obtained as two rooted trees glued together along the roots. Both of these polynomial monads are not tame as both contain the monad for symmetric operads as a submonad. Nevertheless, if we define a normal dioperad (resp. normal \frac{1}{2}PROP) as one which has no operations of type A(0, n) and no operations of type A(n, 0) for n ≥ 0 while A(1, 1) = e, then the following statement holds.

9.10. Proposition. The polynomial monads for normal dioperads and normal \frac{1}{2}PROP’s are tame.

The proof is similar to the one for normal symmetric or normal cyclic operads.

10. Operads based on general graphs

10.1. Modular operads. The monad for modular operads is generated by the polynomial

             [figure: ℕ; s; OrderedGraphs^{∗}; p; OrderedGraphs; t; ℕ]

in which OrderedGraphs denotes the set of isomorphism classes of ordered connected graphs (with non-empty set of vertices) and OrderedGraphs^{∗} is the set of such isomorphism classes with one vertex marked. The source and target maps and the composition operations are defined as above. The polynomial monad for modular operads is not tame even if we restrict to normal modular operads. Normality in this case means that modular operads do not have operations whose arities are corollas with less than three flags. Indeed, in the corresponding internal algebra classifier there is a connected component which contains the following ordered bicoloured graph:

[figure: 1; 3; 2; 2; 1; 3; 3; 2; 1; 2; 1; 4; 3; 1; 2; 3]

in which top and bottom vertices are X-coloured and the middle vertices are K-coloured. The isomorphism class of this graph can not be contracted further inside the internal algebra classifier but it admits a non-trivial automorphism which consists of the following renumbering of the edges incoming in into X-vertices:

[figure: 1; 3; 2; 2; 1; 3; 2; 3; 1; 2; 1; 3; 4; 1; 2; 3]

There is thus no transferred model structure on modular operads under the general assumptions of our Main Theorem 8.1.

10.2. Remark. The usual definition of modular operad uses stable graphs [26, 46], i.e. graphs decorated by genus and satisfying a stability condition. There is a polynomial monad for this version of modular operad, which is not tame by exactly the same argument as above for non-decorated graphs.

These negative results do not exclude the existence of a transferred model structure on the algebras under some more restrictive conditions on the monoidal model category E. The following proposition illustrates in which way specific properties of E can be used to establish the existence of a transfer even for algebras over non-tame polynomial monads.

10.3. Proposition. The monad for modular operads is ⊗-admissible in the monoidal model category Ch(k) of chain complexes over a field k of characteristic 0.

Proof. The generating trivial cofibrations are of the form 0 → D where D is the chain complex … ← 0 ← k ←^{id} k ← 0 ← …. It is thus enough to consider semi-free coproducts of modular operads. The underlying object of a semi-free coproduct X ∨ F (K) has a direct summand equal to X with canonical injection X → X ∨ F (K). We have to show that this injection is a quasi-isomorphism for acyclic K.

The classifier Mod^{Mod+1} contains a final subcategory the objects of which are isomorphism classes of ordered graphs with vertices coloured by X and K, such that internal edges only connect vertices of different colours. Since no further contractions of such graphs are possible the morphisms of this final subcategory are generated by insertion of corollas into X-vertices. Therefore the final subcategory is equivalent to a coproduct of finite groups. The semi-free coproduct is the colimit of a functor on this subcategory which assigns to each graph a tensor product of as many X’s and K’s as there are Xand K-vertices in the graph. The morphisms of the classifier act by permuting K-factors and through the modular operad action on X-factors. It follows that the colimit of this functor splits into one component which corresponds to the image of the canonical injection X → X ∨ F (K) and other components which correspond to graphs with at least one K-vertex. It thus suffices to show that the latter components are acyclic.

Since our chain complex K is a chain complex of k-vector spaces, acyclicity of K implies contractibility of K. Therefore, the functor on the classifier takes those graphs which have K-vertices to contractible chain complexes. Over each connected component of the final subcategory (with K-vertices) the functor can thus be considered as a chain complex in the abelian category of diagrams over this connected component. As we have seen the latter is equivalent to the category of representations of a finite group. Since k has characteristic 0 this representation category is semisimple so that every chain complex in it is cofibrant. Since taking the colimit is a left Quillen functor we conclude that the colimit of F is acyclic on each connected component containing K-vertices, as required.

10.4. Properads, PROP’s. The generating polynomials of the monad for properads and PROP’s are defined in complete analogy with the preceding section, by specifying the appropriate insertional class of graphs. We refer the reader to Markl [46] and Johnson-Yau [32] for an explicit link with the original definitions of properads by Vallette [63] and of PROP’s by Adams-Mac Lane. The insertional class of graphs for PROP’s (properads) consists of all (connected) directed loop-free graphs.

In the normal versions there are no operations of type A(0, n) and no operations of type A(n, 0) for n ≥ 0, while A(1, 1) = e.

10.5. Remark. Our definition of PROP as an algebra of a polynomial monad is slightly weaker than the classical definition as a strict symmetric monoidal category whose set of objects is the commutative monoid of natural numbers. The difference between the classical and our graphical definition of PROP concerns the structure of vertical composition. In classical PROP’s there are two a priori different compositions, horizontal and vertical:

∘_{h} : A(n, 0) × A(0, m) → A(n, m) , ∘_{v} : A(n, 0) × A(0, m) → A(n, m).

In particular A(0, 0) carries two multiplications which satisfy the middle interchange relation and thus make A(0, 0) a commutative monoid by the classical Eckmann-Hilton argument. Therefore, the symmetric group action in the coloured operad for classical PROP’s is not free so that this operad does not correspond to any polynomial monad. In graphical PROP’s however the vertical composition ∘_{v} : A(n, k) × A(k, m) → A(n, m) is represented by the directed graph

^{n} k _{m}

If k = 0 there is no such graph representing vertical composition; rather there is only a graph with two connected components which represents horizontal composition. Therefore, in the case of graphical PROP’s A(0, 0) carries only one composition (the horizontal) and is thus not necessarily a commutative monoid. It is not hard to see, however, that the coloured operad for classical PROP’s is a canonical quotient of the coloured operad for graphical PROP’s, and that for normalised PROP’s there is no difference at all between the classical and our definition.

10.6. Proposition. The polynomial monads for (normal) properads and PROP’s are not tame.

Proof. This negative result follows from the fact that both category of PROP’s and properads contain the category of symmetric operads. In the normal case observe that the following graph lives in one of the connected components of T^{T+1}:

[figure: 1; 2; 1; 2; 3; 2; 1; 1; 2; 3; 2; 1]

in which top and bottom vertices are X-couloured and the middle vertices are K-colour. The isomorphism class of this graph can not be contracted further in T^{T+1} but it admits a non-trivial automorphism consisting of the following renumbering of the edges incoming into the X-vertices:

[figure: 1; 2; 1; 2; 2; 3; 1; 1; 3; 2; 2; 1]

10.7. Wheeled operads, properads and PROP’s. There is also a “wheeled” version of the notions of operad, properad and PROP, due to Markl-Merkulov-Shadrin [48]. The polynomial monad for the wheeled version is defined by allowing certain loops in the insertional class of graphs of the “non-wheeled” version. For instance, the insertional class of graphs for wheeled operads contains rooted trees as well as graphs obtained from rooted trees by identifying the root with one of the leaves of the tree (see [48] for details).

10.8. Proposition. The polynomial monads for wheeled normal properads and PROP’s are not tame.

Proof. The classifier T^{T+1} for wheeled version of properads and PROP’s contains more objects and admit more contractions than in nonwheeled version since directed loops are allowed (see [48, Remark after Def.2.1.8]). In wheeled PROP’s case we can multiply Xvertices (something which is not allowed in properads) and contract any edges between X-vertices (which is not allowed in “unwheeled” PROP’s). Doing this operation we end up with a graph which has only one X-vertex connected to K-vertices. Nevertheless the following graph, which does not admit any further contraction, has a non-trivial automorphism in T^{T+1}:

[figure: 1; 2; 1; 2; 2; 1; 2; 3; 6; 5; 1; 4]

In this graph the central vertex is X-coloured and all the other vertices are K-coloured. The non-trivial automorphism is generated by a substitution which interchanges 2 and 6, and 5 and 3 inside the X-vertex.

On the positive side we have the following statement that tame polynomial monads based on noncontractible graphs do exist.

10.9. Proposition. The polynomial monads for normal (constant-free, reduced) wheeled operads are tame.

We leave the proof to the interested reader as it is very much analogous to the case of symmetric operads.

11. Baez-Dolan +-construction for polynomial monads

With any polynomial monad T one can associate another polynomial monad T^{+}, the so-called Baez-Dolan +-construction of T, see [3, 38, 39, 43]. If T is generated by the polynomial P

[figure: I; s; E; p; B; t; I]

then the generating polynomial P^{+} for T^{+} is

[figure: B; s^{+}; tree^{∗}(P); p^{+}; tree(P); t^{+}; B]

where tree(P) is the set of P -trees, and tree^{∗}(P) is the set of P -trees with a marked vertex. Recall [38, 39] that a P -tree is an isomorphism class of rooted trees whose edges are coloured by the elements of I, and whose vertices are decorated by T -operations in the sense of Remark 6.4, in such a way that the sources and the target of these T -operations coincide with the given edge-colouring of the P -tree.

The source map s^{+} of the generating polynomial of T^{+} returns the T -operation decorating the marked vertex, the middle map p^{+} forgets marking, and the target map t^{+} computes the composite T -operation of the whole P -tree.

The monad M for monoids is the +-construction of the identity monad on Set. The monad O(1) for non-symmetric operads is the +-construction of the monad M. In general, the characteristic property of the +-construction is that T^{+}-algebras can be identified with cartesian monads over T (i.e. T -operads in the terminology of Leinster [43]). For instance, non-symmetric operads can be identified with cartesian monads over M. In particular, there is a natural notion of algebra over a T^{+}-algebra, namely an algebra for the corresponding cartesian monad over T.

11.1. Theorem. For any polynomial monad T, the polynomial monad T^{+} is tame.

Proof. The objects of (T^{+})^{T^{+}+1} are P -trees with an additional colouring of their vertices by two colours X and K. The morphisms are generated by contraction to corolla of subtrees all of whose vertices are X-coloured, or introducing a new X-vertex on an edge coloured by an i ∈ I. The decorating element in this vertex is 1_{i} ∈ B. One can always contract an object in (T^{+})^{T^{+}+1} to an object in which the vertex colours alternate starting with X and ending with X (cf. Sections 9.2 and 9.4). Associativity and unitality of the multiplication of T imply that such a contraction represents a unique morphism in (T^{+})^{T^{+}+1}. Hence, these objects are terminal in their connected components.

This theorem permits the definition of homotopy T -algebras for any polynomial monad T and choice of monoidal model category E fulfilling the hypotheses of Theorem 8.1. Indeed, the terminal object Ass^{T} of the category of T^{+}-algebras corresponds to the identity morphism of cartesian monads id : T → T, so that the category of algebras of Ass^{T} is isomorphic to the category of algebras of T. Since T^{+} is tame polynomial we can consider a cofibrant resolution cAss_{E}^{T} → Ass_{E}^{T} in the category Alg_{T^{+}}(E) of T^{+}-algebras in E. The cAss_{E}^{T} -algebras should then be considered as homotopy T -algebras in E.

For instance, if M is the polynomial monad for monoids then Ass^{M} induces the classical non-symmetric operad Ass_{E}^{M} for monoids in E, and cAss_{E}^{M} is a cofibrant resolution in the category of non-symmetric operads in E, i.e. an A_{∞}-operad. Similarly, the cofibrant operad cAss_{E}^{M^{+}} is a coloured operad in E whose algebras can be considered as (non-symmetric) “homotopy operads” in E.

One can therefore, for any polynomial monad T and any monoidal model category E fulfilling the hypotheses of Theorem 8.1, embed the category of T -algebras in E in a larger category of homotopy T -algebras. We conjecture that in virtue of the cofibrancy of cAss_{E}^{T} in Alg_{T^{+}}(E) there exists a transferred model structure on the category of homotopy T -algebras under very mild additional hypotheses on E.

12. Higher operads

For the convenience of the reader we recall here the definition of the higher operads of the first author. In particular, we describe them as algebras over a polynomial monad, closely following [5, 6]. This subsumes Section 9.2 since 0-operads are monoids, and 1-operads are non-symmetric operads. We also define the monads for various interesting subcategories of the category of n-operads. The monads for constant-free, reduced and normal n-operads are tame polynomial, while the monad for general n-operads is polynomial, but not tame polynomial if n ≥ 2.

12.1. Complementary relations and n-ordinals. -

For all what follows n denotes a fixed positive integer.

12.2. Definition. An n-ordered set X is a set equipped with n binary antireflexive relations <_{0}, …, <_{n−1} which are complementary in the following sense:

(i) for every pair (a, b) of distinct elements of X there is one and only one relation <_{p} such that a <_{p} b or b <_{p} a.

An n-ordinal T is a finite n-ordered set such that for any a, b, c in T

(ii) if a <_{p} b and b <_{q} c then a <_{min(p,q)} c.

A map of n-ordered sets σ : X → Y is a mapping of the underlying sets such that the relation a <_{p} b in X implies one of the following three types of relations in Y:

1. σ(a) <_{q} σ(b) for p ≤ q or

2. σ(a) = σ(b) or

3. σ(b) <_{q} σ(a) for p < q.

The category of n-ordered sets and maps between them will be denoted Rel(n). The full subcategory of Rel(n) spanned by the n-ordinals will be denoted Ord(n). There is an obvious forgetful functor | − | : Rel(n) → FinSet which forgets the relations. The cardinality of an n-ordered set X is the cardinality of its underlying set |X|.

As there are no non-trivial automorphisms in Ord(n) we will assume that each isomorphism class of n-ordinals contains a single element, i.e. Ord(n) is skeletal.

Each n-ordinal can be represented as a pruned planar rooted tree with n levels (pruned n-tree for short), cf. [5, Theorem 2.1]. For example, the 2-ordinal

0 <_{0} 2, 0 <_{0} 3, 0 <_{0} 4, 1 <_{0} 2, 1 <_{0} 3, 1 <_{0} 4, 0 <_{1} 1, 2 <_{1} 3, 2 <_{1} 4, 3 <_{1} 4,

is represented by the following pruned tree

0 1 2 3 4

Figure 3: A pruned 2-tree.

The initial n-ordinal z^{n}U_{0} has empty underlying set and its representing pruned ntree is degenerate: it has no edges but consists only of the root at level 0. The terminal n-ordinal U_{n} is represented by a linear tree with n levels.

12.3. Definition. An n-ordered set X is said to dominate an n-ordered set Y if there is a map of n-ordered sets X → Y inducing the identity on underlying sets.

We also would like to consider the limiting case of ∞-ordinals.

12.4. Definition. Let T be a finite set equipped with a sequence of binary antireflexive complimentary relations <_{0}, <_{−1} …, <_{p}, <_{p−1} … for all integers p ≤ 0. The set T is called an ∞-ordinal if these relations satisfy:

• a <_{p} b and b <_{q} c implies a <_{min(p,q)} c.

The definition of morphism between ∞-ordinals coincides with the definition of morphism between n-ordinals for finite n. The category Ord(∞) denotes the skeletal category of ∞-ordinals.

For an n-ordinal R , k ≤ n we consider its vertical suspension S(R) which is an (n + 1)-ordinal with the underlying set R, and the order <_{m} equal the order <_{m−1} on R while <_{0} is empty.

For example, a vertical suspension of the 2-ordinal from Figure 3 is the 3-ordinal

0 1 2 3 4

The suspension operation induces functors S_{p} : Ord(n) → Ord(n + 1), 0 ≤ p ≤ n. We also define an ∞-vertical suspension functor Ord(n) → Ord(∞) as follows. For an n-ordinal T its ∞-suspension is an ∞-ordinal S^{∞}T whose underlying set is the same as the underlying set of T and a <_{p} b in S^{∞}T if a <_{n+p−1} b in T. It is not hard to see that the sequence

Ord(0) ⟶^{S} Ord(1) ⟶^{S} Ord(2) ⟶ … ⟶^{S} Ord(n) ⟶ … ⟶^{S^{∞}} Ord(∞),

exhibits Ord(∞) as a colimit of Ord(n).

12.5. Fox-Neuwirth stratification of configuration spaces and n-ordinals. Recall that the moduli space of configurations of k ordered, pairwise distinct points in ℝ^{n} admits a stratification which goes back to Fox-Neuwirth. Consider the following configuration space

F (ℝ^{n}, k) = {(x_{1}, …, x_{k}) ∈ (ℝ^{n})^{k} | x_{i} ≠ x_{j} if i ≠ j }

and denote S_{±}^{n−p−1}^{o} the open (n − p − 1)-hemispheres defined by

S_{+}^{n−p−1}^{o}= \{x ∈ ℝ^{n} | \begin{matrix}x_{1}^{2} + … + x_{n}^{2} = 1 \\ x_{p+1} > 0 and x_{i} = 0 for 1 ≤ i ≤ p \end{matrix} \}

and

S_{−}^{n−p−1}^{o}= \{x ∈ ℝ^{n} | \begin{matrix}x_{1}^{2} + … + x_{n}^{2} = 1 \\ x_{p+1} < 0 and x_{i} = 0 for 1 ≤ i ≤ p \end{matrix} \}.

Let u_{ij} : F (ℝ^{n}, k) → S^{n−1} be the function

u_{ij}(x_{1}, …, x_{k}) = \frac{x_{j} − x_{i}}{||x_{j} − x_{i}||}

The Fox-Neuwirth cell corresponding to an n-ordinal T of cardinality k is

F N_{T} = \{x ∈ F (ℝ^{n}, k) | \begin{matrix}u_{ij}(x) ∈S_{+}^{n−p−1}^{o} & if i <_{p} j in T \\ u_{ij}(x) ∈S_{−}^{n−p−1}^{o} & if j <_{p} i in T \end{matrix} \}.

For instance, the Fox-Neuwirth cell which corresponds to the 2-ordinal below

[figure: S =] [figure] [figure]

consists of configurations of points which seat on three parallel lines in the prescribed order

1 3 5 2 4 6

Each Fox-Neuwirth cell is a convex subspace of (ℝ^{n})^{k}, open in its closure, and we have a stratification

F (ℝ^{n}, k) = ⋃_{|T |≅{1,...,k},π∈S_{k}} πF N_{T} .

Here πF N_{T} is the space obtained from F N_{T} by renumbering points according to the permutation π.

The domination relation of Definition 12.3 induces a partial ordering of the set of n-ordinal structures on a fixed set {1, …, k} of cardinality k. Using Fox-Neuwirth stratification we can show that the nerve of this poset is homotopy equivalent to F (ℝ^{n}, k), cf. [5, Remark 2.2], [7, Theorem 5.1].

12.6. Fibres and total order. Let σ : T → S be a map of n-ordinals. For each i ∈ |S|, the set-theoretical fibre |σ|^{−1}(i) ⊂ |T | inherits from T the structure of an nordinal. This n-ordinal will be denoted σ^{−1}(i) and called the fibre of σ at i.

Observe that the underlying set |S| is totally ordered by the relation

a < b if there exists p ∈ {0, …, n − 1} such that a <_{p} b.

We call this the total order on the underlying set |S|. The fibres of a map of n-ordinals σ : T → S will accordingly be represented by an ordered list (T_{0}, …, T_{k}) of n-ordinals, the ordering being induced by the total order on |S|.

Analogously, any two composable maps of n-ordinals

[figure: T; σ; S; ω; R]

induce a family of maps of n-ordinals

(ωσ)^{−1}(i) → ω^{−1}(i)

indexed by i ∈ |R|. We thus have a list of fibres (T_{0}, …, T_{k}) for the composite map ωσ, a list of fibres (S_{0}, …, S_{k}) for ω, and a list of fibres (T_{i}^{0}, …, T_{i}^{m_{i}}) for each map (ωσ)^{−1}(i) → ω^{−1}(i) where i ∈ |R|. These notations will be used in the definition of an n-operad below.

12.7. Definition. A map of n-ordinals is a quasibijection (resp. order-preserving) if it induces a bijection between the underlying sets (resp., preserves the total orders of the underlying sets, i.e. only possibilities (1) and (2) of Definition 12.2 occur).

12.8. Definition. An n-collection in a symmetric monoidal category E is a family (A_{T})_{T ∈Ord(n)} of objects of E indexed by n-ordinals. The category of n-collections and levelwise morphisms in E will be denoted by Coll_{n}(E).

We now recall the definition of a pruned (n − 1)-terminal n-operad [5]. Since we do not need other types of n-operads we will call them simply n-operads.

12.9. Definition. An n-operad in E is an n-collection (A_{T})_{T ∈Ord(n)} in E equipped with the following structure:

- a morphism ϵ : e → A_{U_{n}} (unit);

- a morphism m_{σ} : A_{S} ⊗ A_{T_{0}} ⊗ ⋯ ⊗ A_{T_{k}} → A_{T} (multiplication) for each map of n-ordinals σ : T → S.

They must satisfy the following identities:

- for any composite map of n-ordinals

[figure: T; σ; S; ω; R]

the associativity diagram

[figure: A_{R}⊗A_{S•}⊗A_{T^{•}_{0}}⊗···⊗A_{T^{•}_{i}}⊗···⊗A_{T^{•}_{k}}; A_{R}⊗A_{S_{0}}⊗A_{T^{•}_{1}}⊗···⊗A_{S_{i}}⊗A_{T^{•}_{i}}⊗···⊗A_{S_{k}} ⊗A_{T^{•}_{k}}; ≅; A_{S}⊗A_{T^{•}_{1}}⊗···⊗A_{T^{•}_{i}}⊗···⊗A_{T^{•}_{k}}; A_{R}⊗A_{T•}; A_{T}]

commutes, where

A_{S_{•}} = A_{S_{0}} ⊗ ⋯ ⊗ A_{S_{k}},
A_{T_{i}^{•}} = A_{T_{i}^{0}} ⊗ ⋯ ⊗ A_{T_{i}^{m_{i}}}

and

A_{T_{•}} = A_{T_{0}} ⊗ ⋯ ⊗ A_{T_{k}};

- for an identity σ = id : T → T the diagram

[figure: A_{T} ⊗ A_{U_{n}} ⊗ ⋯ ⊗ A_{U_{n}}; A_{T} ⊗ e ⊗ ⋯ ⊗ e; A_{T}; id]

commutes; - for the unique morphism T → U_{n} the diagram

[figure: A_{U_{n}} ⊗ A_{T}; e ⊗ A_{T}; A_{T}; id]

commutes.

The notion of n-operad morphism is obvious and we have a category O_{n}(E) of noperads. The forgetful functor

U_{n} : O_{n}(E) → Coll_{n}(E)

has a left adjoint and is monadic whenever E is cocomplete.

12.10. Constant-free, reduced and normal n-operads.

12.11. Definition. An n-ordinal is called regular if it is not the initial n-ordinal. An n-ordinal is called normal if it is neither the initial nor the terminal n-ordinal.

There is a category structure on ROrd(n) which we will call the category of regular n-ordinals. The morphisms are those maps of n-ordinals which are surjective on the underlying sets. This forces the fibres to be regular again.

12.12. Definition. A regular n-collection in E is a family (A_{T})_{T ∈ROrd(n)} of objects of E indexed by the set ROrd(n) of regular (i.e. nonempty) n-ordinals.

A normal n-collection in E is a family (A_{T})_{T ∈ROrd(n)} of objects of E indexed by the set NOrd(n) of normal n-ordinals.

A constant-free n-operad is defined in a similar way as an n-operad by using regular n-collections and maps of regular n-ordinals. This defines the category of constant-free n-operads CF O_{n}(E) together with a forgetful functor

CF U_{n} : CF O_{n}(E) → RColl_{n}(E),

where CF Coll_{n}(E) is the category of constant-free n-collections. This functor has a left adjoint and is monadic whenever E is cocomplete.

Analogously we have a category of normal n-ordinals NOrd(n) with morphisms being surjective morphisms between normal n-ordinals. In the list of fibres of a map of normal n-ordinals we include only those fibres which are not equal to the terminal n-ordinal. We have the corresponding categories of normal n-collections NColl_{n}(E) and normal n-operads NO_{n}(E). The latter can be considered as the full subcategory of CF O_{n}(E) consisting of constant-free n-operads A such that A_{U_{n}} = e. The forgetful functor

NU_{n} : NO_{n}(E) → NColl_{n}(E),

is again monadic whenever E is cocomplete.

The category of reduced n-operads is the category of constant-free n-operads with additional structure. This structure is the structure of a contravariant functor on the category of regular n-ordinals and their injective order-preserving maps. Similar to the case of reduced symmetric operads, the category of reduced n-operads contains the category of those n-operads A such that A_{z^{n}U_{0}} = e as a full subcategory, cf. Remark 9.6.

12.13. The polynomial monad for n-operads.

12.14. Proposition. The monad O(n) for n-operads is generated by the polynomial

      [figure: Ord(n); s; nPlanarRootedTrees^{∗}; p; nPlanarRootedTrees; t; Ord(n)]

where

• Ord(n) is the set of isomorphism classes of n-ordinals;

• nPlanarRootedTrees is the set of isomorphism classes of n-planar trees;

   • nPlanarRootedTrees^{∗} is the set of elements τ ∈ nPlanarRootedTrees with one

vertex marked.

The structure maps are defined as follows:

• The middle map forgets the marking;

• The target map associates to τ the n-ordinal of its leaves;

• The source map associates to a marked vertex τ the n-ordinal τ_{v} decorating the marked vertex v.

The multiplication of the monad is induced by insertion of n-planar trees into vertices of n-planar trees and the unit of the monad assigns to an n-ordinal T a corolla decorated by T with T as an n-ordinal structure on its leaves.

Proof. We give a sketch of the proof. More details can be found in [5, 6]. First, we can show that the data above determine a polynomial monad O(n). Second, any algebra A of O(n) has the structure of an n-operad. The unit of this operad is given by an n-planar rooted tree L_{0} (see (13.2) for notations) whose target is the terminal n-ordinal U_{n} and whose set of sources is empty because L_{0} does not have vertices. To define a multiplication in A we will associate an n-planar tree [σ] with each morphism of n-ordinals σ : T → S. The set of vertices {v_{S}, v_{T_{i}}, …, v_{T_{k}}} of the tree [σ] is in one-to-one correspondence with the set {S, T_{1}, … T_{k}}, where T_{1}, …, T_{k} are fibres of σ. The outgoing edge of the vertex v_{S} is the root of the tree [σ]. The elements of |S| are incoming edges of this vertex with its n-ordinal structure. The other vertices are all above v_{S} and the outgoing edge of v_{T_{i}} is the i-th incoming edge of v_{S}. The leaves attached to the vertex v_{T_{i}} correspond to the elements of |T_{i}| and this set has T_{i} as its n-ordinal structure. Finally, the set of leaves is equipped with the n-ordinal structure of T.

1 3 σ 5 2 4 6 σ(1) = 1, σ(2) = 2, σ(3) = 1, σ(4) = 2, σ(5) = 1, σ(6) = 2. [σ] =

Figure 4: A 2-ordinal and its corresponding 2-planar tree.

The element [σ] then produces the multiplication

m_{σ} : A_{S} × A_{T_{0}} × ⋯ × A_{T_{k}} → A_{T}

in the algebra A. All axioms follow from the associativity and unitality of the operation of insertion of n-planar trees.

Conversely, if B is an n-operad one can associate with any n-planar tree τ a composite map out of the product of all B_{τ_{v}} for all vertices of τ to the set B_{t(τ)} using induction from top to the bottom of the tree (see [5, Lemma 3.2]).

12.15. The polynomial monads for normal and constant-free n-operads. The monad for normal n-operads has been computed in [5, Theorems 3.1 and 4.1]. We show now that it is a polynomial monad.

12.16. Proposition. The monad for normal n-operads is generated by the polynomial

    [figure: NOrd(n); s; nPlanarRootedTrees_{nor}^{∗}; p; nPlanarRootedTrees_{nor}; t; NOrd(n)]

where

• NOrd(n) is the set of isomorphism classes of normal n-ordinals;

• nPlanarRootedTrees_{nor} is the set of isomorphism classes of normal n-planar trees;

   • nPlanarRootedTrees_{nor}^{∗} is the set of elements of nPlanarRootedTrees_{nor} with one

vertex marked.

The structure maps of this polynomial monad NO(n) are defined in the same way as for the polynomial monad for n-operads.

Proof. The proof is analogous to the proof of Proposition 12.14. The only difference is that we construct a normal n-planar tree [σ] only for surjective maps of normal nordinals. In this construction we also do not introduce vertices for those fibres of σ which are isomorphic to the terminal n-ordinal.

σ_{σ(1) = 1, σ(2) = 2, σ(3) = 1}_{[σ] =} 1 3 2

Figure 5: A normal 2-ordinal and its corresponding normal 2-planar tree.

12.17. Proposition. The monad for constant-free n-operads is generated by the polynomial

    [figure: ROrd(n); s; nPlanarRootedTrees_{reg}^{∗}; p; nPlanarRootedTrees_{reg}; t; ROrd(n)]

where

• ROrd(n) is the set of isomorphism classes of regular n-ordinals;

• nPlanarRootedTrees_{reg} is the set of isomorphism classes of regular n-planar trees;

   • nPlanarRootedTrees_{reg}^{∗} is the set of elements of nPlanarRootedTrees_{reg} with one

vertex marked.

The structure maps of this polynomial monad CF O(n) are analogous to those of the polynomial monad for n-operads.

Proof. The proof is again similar to the proof of Proposition 12.14. The difference is that we construct a regular n-planar tree [σ] only for surjective maps of regular n-ordinals.

12.18. Definition. An n-planar tree is called non-degenerate if its underlying tree is non-degenerate in the sense of Definition 9.5. A vertex v of an n-planar tree τ is called non-degenerate if the corolla cor_{v}(τ) is non-degenerate in the tree underlying τ.

12.19. Proposition. The monad for reduced n-operads is generated by the polynomial

    [figure: ROrd(n); s; nPlanarRootedTrees_{nd}^{∗}; p; nPlanarRootedTrees_{nd}; t; ROrd(n)]

where

• ROrd(n) is the set of isomorphism classes of regular n-ordinals;

• nPlanarRootedTrees_{nd} is the set of isomorphism classes of non-degenerate n-planar trees;

   • nPlanarRootedTrees_{nd}^{∗} is the set of elements of nPlanarRootedTrees_{nd} with one

non-degenerate vertex marked.

The structure maps of this polynomial monad RO(n) are analogous to those of the polynomial monad for n-operads.

Proof. Everything is similar to the other three cases except that contraction of trees may involve dropping degenerate vertices. As a result, the underlying category of this polynomial monad is the category of regular n-ordinals and their injections.

We now prove that the polynomial monads NO(n), CF O(n) and RO(n) are tame, while the monad O(n) is not tame for n ≥ 2. We construct an obstruction for the existence of transferred model structure in the latter case. Our proof will be based on a combinatorial lemma about directed categories.

12.20. Definition. A small category C is called directed if there is a function dim (called dimension function) on objects of this category to an ordinal λ such that any non-identity morphism strictly increases the dimension.

12.21. Lemma. Let C be a finite directed category with a set of generating morphisms G which satisfies the following two conditions:

(i) Any two parallel generators in C are equal;

(ii) Any span of generators

ω ←^{ϕ} τ →^{ψ} υ

in C can be completed to a commutative square by a cospan of generators (or identities)

υ →^{ϕ^{∗}} ς ←^{ψ^{∗}} ω.

Then there is a unique terminal object in each connected component of C.

Proof. We first prove that each connected component of C has a unique weakly terminal object, i.e. an object such that there exists at least one morphism to it from any other object of the same connected component. We use an induction on the number k of objects in C. If k = 1 the unique object in C is weakly terminal. Assume now that we know that the statement is true for any for k ≤ m − 1. Observe that given a zig-zag of morphisms in C

a_{0} ← a_{1} → a_{2} ← . . . . . . → a_{n−2} ← a_{n−1} → a_{n}

one can replace it by a zig-zag

a_{0} → b_{1} ← a_{2} ← . . . . . . → a_{n−2} → b_{n−1} ← a_{n}.

Doing the same for the zig-zag of b’s and continuing we come to the conclusion that for any two objects c, c′ of the same connected component of C one can find an object c′′ and a cospan

c → c′′ ← c′.

We can now assume that there is only one connected component in C, otherwise the statement for k = m follows immediately from the inductive hypothesis. Let L be the minimum of the function dim on C. Consider the full subcategory C′ consisting of objects a such that dim(a) > L. Then C′ is obviously connected and satisfies our inductive hypothesis. Therefore, it contains a weakly terminal object t. If an object a does not belong to C′ then there must be a span

a → b ← t

where b ∈ C′. In this span b ← t must be an identity, otherwise dim(b) > dim(t) and t would not be weakly terminal. So, we have found a map from any object of C to t. This weakly terminal object is obviously unique.

The next step of the proof is to show that the weakly terminal object t is actually terminal in its connected component. We use an induction on dim to prove that there is at most one morphism to t. Indeed, the statement is true for all objects a such that dim(a) ≥ dim(t). Now, suppose we know that the morphism is unique for all objects a such that dim(a) ≥ m. Let k be the maximal integer such that k < m and there exists an object b such that dim(b) = k. Let dim(b) = k. and f, g : b → t. One can factorise f = f_{1} · f_{2} and g = g_{1} · g_{2} where f_{1} and g_{1} are generators. Now, we can complete the cospan

a_{1} ←^{f_{1}} b →^{g_{1}} a_{2}

to a span

a_{1} → c ← a_{2}.

If a_{1} ≠ a_{2} then we can use our inductive hypothesis and, therefore, there is only one morphism from c to t and we finished the proof. If a_{1} = a_{2} then f_{1} = g_{1} and f_{2} = g_{2} by the inductive hypothesis.

12.22. The normal n-operad classifier NO(n)^{NO(n)}. According to formula (10) and Proposition 12.16 the n-collection whose S-th term is the set of normal S-dominated n-planar trees is the object of objects of the classifier NO(n)^{NO(n)}. The morphisms of NO(n)^{NO(n)} are generated by insertions of n-planar trees into vertices of another n-planar tree. This allows us to describe the morphisms explicitly as certain contractions of “forests” in an n-planar tree.

Let τ be an n-planar tree. An n-ordered subtree τ′ of τ is a plain subtree of τ such that for each of its vertices the set of incoming edges carries the obvious n-ordinal structure induced from τ.

A n-ordered subtree τ′ is called an n-planar subtree if the set of leaves of τ′ is equipped with an n-ordinal structure (called target n-ordinal of τ′) such that

(i) τ′ is an n-planar tree;

(ii) the corresponding contraction C_{(τ,τ′)} (32) is a map of n-ordinals.

A forest of n-planar subtrees in τ is a set of n-planar subtrees of τ whose sets of vertices are pairwise disjoint. The source of such a forest is the tree τ itself; the target is the n-planar tree obtained from τ by contracting each subtree of the forest to a corolla, and decorating the corresponding vertex by the target n-ordinal of the contracted subtree.

The category NO(n)^{NO(n)} is generated by contractions of single n-planar subtrees. There are two types of relations:

(••) Given a forest consisting of two disjoint n-planar subtrees the morphism of contraction of this forest factorises as two consecutive contractions of its subtrees in any of the two possible orders;

(⊙ •) Given an n-planar subtree which contains itself an n-planar subtree, the morphism of contraction of the bigger subtree factorises as contraction of the smaller subtree followed by contraction of the result of the first contraction.

For an example of a generator see the left hand side tree on Figure 10. The target 2-ordinal of the subtree shown by a dash line is the 2-ordinal in the root of the contracted tree. Observe that the total order of this 2-ordinal structure on the leaves is different from the linear order induced by planar structure of the subtree.

12.23. Lemma. Any two parallel generators in NO(n)^{NO(n)} are equal.

Proof. For the proof it is enough to see that due to the planarity and normality of the underlying trees source and target of a generator permit to reconstruct entirely the nplanar subtree whose contraction defines the generator. Indeed, we know the decorating n-ordinals of the vertices of this subtree and, hence, its n-ordinal structure. The decoration of the vertex of the target tree gives us the n-ordinal structure on the set of leaves of this subtree, so that we reconstructed the entire contracted n-planar subtree.

12.24. Diamond generated by a span in NO(n)^{NO(n)}. Let now τ be an n-planar tree and let τ′, τ′′ be two n-planar subtrees of τ. These two subtrees generate a span of morphisms in NO(n)^{NO(n)}

ω ←^{ϕ} τ →^{ψ} υ  (31)

We now describe a construction which produces a cospan in NO(n)^{NO(n)}

υ →^{ϕ^{∗}} ς ←^{ψ^{∗}} ω

making the square

[figure: τ; ψ; υ; ω; ϕ; ψ^{∗}; ς; ϕ^{∗}]

commutative. We call this construction diamond generated by the span (31). We consider two cases:

(i) τ′ and τ′′ have no common vertices so they form an n-planar subforest τ ∪ τ′ in τ ;

(ii) τ′ and τ′′ have at least one common vertices, so τ ∪τ′ is a partially n-ordered subtree τ′′′ in τ.

Case (i) is easy since in this case we can take as ς the result of contraction of the subforest τ ∪ τ′. The resulting square commutes because of the relation of type (••) in NO(n)^{NO(n)}.

For the case (ii) we will now complete the partial n-ordered subtree structure on τ′′′ to an n-planar subtree structure in τ in such a way that τ′ and τ′′ both are n-planar subtrees of τ′′′. If such a structure on τ′′′ exists then we can take as ς the result of contraction of τ′′′ and we will have a morphism δ : τ → ς. We also get a morphism ϕ^{∗} : υ → ς because τ′ is a subtree of τ′′′ and relation of type (⊙ •) in NO(n)^{NO(n)} shows that δ = ψ · ϕ^{∗}. Analogously we have δ = ϕ · ψ^{∗} and the result follows.

To provide τ′′′ with an n-planar structure we need to equip the set of leaves L(τ′′′) with an n-ordinal structure and check that such an equipment satisfies the necessary condition. Observe that L(τ′′′) is a subset of L(τ′′) ∪ L(τ′). Let

C_{(τ,τ′)} : L(τ) → L(τ′) , C_{(τ,τ′′)} : L(τ) → L(τ′′)

be the corresponding contraction functions. They determine a unique function

C : L(τ) → L(τ′) ∪ L(τ′′).

For each h ∈ L(τ′′′) ⊂ L(τ′)∪F (τ′′) let us choose a leave i(h) ∈ C^{−1}(h). We have a subset

{i(h)|h ∈ L(τ′′′)} ⊂ L(τ)

and we equip it with the n-ordinal structure induced from F (τ). The tree τ′′′ is an n-planar subtree of τ. It is also clear that τ′ and τ′′ are n-planar subtrees of τ′′′ which finishes the construction.

12.25. Lemma. For each n-ordinal T the category (NO(n)^{NO(n)})_{T} is a finite directed category.

Proof. The finiteness of (NO(n)^{NO(n)})_{T} is clear. To prove the existence of an increasing dimension-function, let us construct an antireflexive and transitive relation on the objects of (NO(n)^{NO(n)})_{T} which reflects the morphisms in (NO(n)^{NO(n)})_{T}. We will write (τ, T) ≪ (τ′, T) if either the underlying rooted tree of τ′ is obtained from the underlying rooted tree of τ by contraction of some internal edges, or τ and τ′ have isomorphic underlying rooted trees but d(τ) < d(τ′).

Here d(τ) = ∑_{v∈τ} d(τ_{v}), where for an n-ordinal S the dimension d(S) is the number of edges in the level-tree representation minus n−1. This dimension d(S) of the n-ordinal S is actually the geometric dimension of the Fox-Neuwirth cell defined by S (cf. Section 12.5), while the resulting d(τ) is the geometric dimension of the Getzler-Jones cell defined by the n-planar tree τ (cf. [5]). It follows that each generator f : τ → τ′ satisfies τ ≪ τ′, because such a generator either contracts some internal edges of the underlying tree or comes from a quasibijection, in which case the dimension of the domain tree is strictly less than the dimension of codomain tree (a quasibijection corresponds to an inclusion of a Fox-Neuwirth cell into the boundary of another). We now get by induction on the number of elements that any finite set equipped with a transitive antireflexive relation possesses a dimension-function for its elements which strictly increases along this relation.

12.26. The classifier NO(n)^{NO(n)+1}. Objects of the classifier NO(n)^{NO(n)+1} consist of n-planar planar trees with an additional decoration of each vertex by colours X or K. We call such trees coloured n-planar trees. The vertices are called X-vertices or K-vertices according to their colours.

[figure: 10; 1; 7; X_{t}; 12; 11; K_{v}; K_{t}; X_{s}; 5; 8; 3; X_{p}; 4; 13; K_{v}; 2; 6; 9; X_{w}]

Figure 6: Typical coloured n-planar tree. Here v, w, p, t, s are n-ordinals decorating vertices.

The morphisms in NO(n)^{NO(n)+1} are generated by contractions of n-planar subtrees all of whose vertices are X-vertices. The resulting new vertex after such a contraction gets colour X. Relations between morphisms are the same as in NO(n)^{NO(n)}.

12.27. Theorem. The polynomial monad NO(n) is tame.

Proof. We check that the classifier (NO(n)^{NO(n)+1})_{T} satisfies the conditions of Lemma 12.21. Indeed, we use the same dimension-function as in Lemma 12.25. Property (i) of the Diamond Lemma follows from Lemma 12.23. Property (ii) follows from the fact that in such a span of generators only n-planar subtrees with X-vertices are involved and so we can repeat the construction of the diamond from 12.24 verbatim.

12.28. Theorem. The polynomial monads CF O(n) and RO(n) are tame.

Proof. The category NO(n)^{NO(n)+1} is a subcategory of CFO(n)^{CFO(n)+1} for non-terminal n-ordinals. It is not difficult to construct a terminal object in the connected component of CFO(n)^{CFO(n)+1} out of the terminal object in the corresponding connected component of NO(n)^{NO(n)+1}. Indeed, let t ∈ NO(n)^{NO(n)+1} be such an object. We construct an object t′ in CFO(n)^{CFO(n)+1} as follows: for any two K-vertices in t connected by an edge, or for a leave or root attached to a K-vertex, we replace this edge or leave with a linear tree with one vertex. We assign the colour X to this new vertex. We have a morphism from t to t′ generated by the unit of the n-operad.

[figure: K_{v}; K_{w}; K_{v}; K_{w}; Xu_{n}]

For S = U_{n} a typical terminal object in the connected component is a linear tree whose vertices are decorated by U_{n} and whose colours are alternating between X and K, starting with X and ending with X.

[figure: Ku_{n}; Xu_{n}; Ku_{n}; Xu_{n}; Xu_{n}]

We leave the proof that these objects are terminal in their connected components of CFO(n)^{CFO(n)+1} as an exercise.

The classifier RO(n)^{RO(n)+1} for reduced n-operads contains more objects than the classifier CFO(n)^{CFO(n)+1} because trees with stumps are allowed. Nevertheless it also contains morphisms of ‘dropping’ stumps. So objects which are terminal in their connected component of CFO(n)^{CFO(n)+1} are also terminal in their connected components of RO(n)^{RO(n)+1}.

12.29. Remark. The difficulties with the case of n-operads (n ≥ 2) in comparison with monoids and non-symmetric operads (and many other operad types) are closely related to the existence of the so-called “bad” cells in the Fulton-MacPherson compactification of real configurations spaces, discovered by Tamarkin [5, 40]. For instance, the object of (NO(n)^{NO(n)+1})_{S} (n = 2), represented in Figure 7, is terminal in its connected component.

[figure: S =; Y =; V =]

[figure: 3; 5; K_{V}; 1; X_{V}; X_{Y}; 6; X_{V}; 2; 4; K_{V}]

Figure 7: Terminal object in a connected component of NO(n)^{NO(n)+1} which corresponds to a Tamarkin bad cell.

It was shown in [5] that this figure corresponds exactly to the first bad cell in the Fulton-MacPherson operad fm^{2}. One can show that certain cells of maximal dimensions in fm^{n} correspond to terminal objects in NO(n)^{NO(n)+1} but in general, we don’t know an explicit characterisation of such cells and as a consequence an explicit formula for semi-free coproducts of n-operads for n ≥ 2.

12.30. The polynomial monad O(n) is not tame for n ≥ 2. Some connected components of O(n)^{O(n)+1} do not have terminal objects but do contain weakly terminal objects. This is because we have to include trees with stumps in the description of the monad for n-operads. As a consequence colimits over O(n)^{O(n)+1} are more complicated than those appearing in the monads for constant-free and normal n-operads. Weak equivalences may not be preserved by these colimits, and this creates an obstruction for the existence of transferred model structure on n-operads in an arbitrary monoidal model category E even if the latter satisfies the hypothesis of Theorem 8.1.

More precisely, for n = 2, the category (O(n)^{O(n)+1})_{z^{2}U_{0}} has as objects all coloured 2planar trees without leaves. All such trees which contain exactly two K-vertices without leaves form a full connected subcategory of (O(n)^{O(n)+1})_{z^{2}U_{0}} This subcategory contains a final subcategory consisting of two objects

[figure: K_{0}; K_{0}; X_{Y}; and; K_{0}; K_{0}; X_{V}]

where Y, V are 2-ordinals as in (12.29). There are exactly two non-trivial morphisms between these objects generated by two quasibijections σ_{0} and σ_{1} from V to Y. It follows that the z^{2}U_{0}-component of the semi-free coproduct of 2-operads contains a summand isomorphic to the coequaliser of

X_{Y} ⊗ K_{0} ⊗ K_{0} ⟶ ⟶^{d_{1}}_{d_{0}} X_{V} ⊗ K_{0} ⊗ K_{0},

where

d = X(σ_{0}) ⊗ id_{K_{0}⊗K_{0}}
d′ = X(σ_{1}) ⊗ τ_{K_{0}⊗K_{0}},

and τ is the symmetry morphism in E.

Let now E be the category of chain complexes over a field k of characteristic two. Let K be a non-reduced 2-collection such that K_{0} = C, where C is an acyclic cofibrant object in E and K_{T} = 0 for all T ≠ 0. Let X be a 2-operad with X_{T} = k for all T ∈ Ord(2). The aforementioned calculation shows that the coproduct F (K)∨X contains a summand C ⊗ C/𝕊_{2} which is not necessarily an acyclic complex, moreover, it is not hard to find a C such that 0-homology of C ⊗ C/𝕊_{2} will be k ⊕ k. Hence, X → F (K) ∨ X can not be a weak equivalence. Nevertheless, if the category of 2-operads in E admitted a transferred model structure this map would have to be a weak equivalence because trivial cofibrations are closed under pushouts. Similar obstructions for the existence of a model structure on n-operads exist for any n ≥ 2.

Part IV

Graphs, trees and graph insertion

In this last part, we give formal definitions of graphs, trees and graph insertion. Graphs have been used in an essential way in defining the polynomial monads of Part 3 whose algebras describe different types of operads. Indeed, each class of graphs, which is suitably closed under graph insertion, gives rise to a polynomial monad on sets whose multiplication is directly induced by graph insertion. The graph insertional origin of the monad multiplication is responsible for the substitutional structure of the associated algebras. This explains somewhat why these algebras are “generalised operads”.

Most important for us are the graphical properties of the so-called n-planar trees. These are higher-order generalisations of the well-known linear (n = 0) and planar (n = 1) rooted trees. Algebras for the polynomial monad defined by the class of n-planar trees are precisely pruned (n − 1)-terminal n-operads of the first author [5, 6], cf. Section 12.

Our notions of graph and graph insertion are equivalent to those used in the recent book by Johnson-Yau [32], though closer in spirit to the Feynman graphs of Joyal-Kock [33]. We are grateful to Mark Johnson and Donald Yau for pointing out that our previously used definitions omitted the “free-living loops” which naturally appear whenever “operadic algebras” are equipped with “traces”.

13. Graphs and graph insertion

13.1. Definition. A graph is a finite category G with three kinds of objects, called vobjects, f-objects and e-objects respectively.

Among non-identity arrows in G are only allowed arrows with source an f-object and target either a v- or an e-object such that the following two axioms hold:

(i) each e-object is the target of precisely two non-identity arrows;

(ii) each f-object is the source of at least one and at most two non-identity arrows, among which one at least has an e-object as target; if both targets are e-objects, the arrows must be parallel.

A morphism of graphs G → G′ is a functor of the underlying categories which takes v-, f- resp. e-objects of G to v-, f- resp. e-objects of G′.

Observe that this definition allows the set of f-objects to be empty, in which case the set of e-objects is empty as well. For ease of terminology, the v-, f- resp. e-objects of G will be called the vertices, flags resp. edges of the graph G. The reader should consider the categorical structure of G as describing the incidence relations between these three kinds of objects of G.

Each edge e of G comes equipped with a unique cospan f_{1} → e ← f_{2}. We say that the two flags f_{1} and f_{2} are adjacent. A flag f is free if f is the source of exactly one non-identity arrow. For a vertex v of G the sources of the incoming arrows are the flags attached to v, or v-flags. Each v-flag is the source of exactly one arrow with target v. An edge e is internal if the cospan f_{1} → e ← f_{2} either fulfills f_{1} = f_{2} or extends to a zigzag

v_{1} ← f_{1} → e ← f_{2} → v_{2}.

Non-internal edges will be called external.

A corolla is a graph with a unique vertex and only external edges. For each n ≥ 0 there is up to isomorphism a unique corolla with n external edges.

A free-living edge (resp. free-living loop) is a graph with no vertices and one external (resp. internal) edge.

A pointed loop is a graph with one vertex and one internal edge.

Let G, G′ be two graphs, let v be a vertex of G and let ρ be a bijection between the set of free flags of G′ and the set of v-flags of G. Then the insertion of G′ into G along ρ is the graph G ∘_{ρ} G′ defined as follows.

Let G \ v be the graph obtained by removing from G vertex v as well as all arrows with target v. Let f(G′) (resp. e(G′)) be the discrete subcategory of G′ containing only the free flags (resp. external edges) of G′. Let \overline{G′ \ e(G′)} be the category obtained by removing from G′ all external edges e as well as all arrows to such e, and by identifying each free flag with its adjacent.

Both categories f(G′) and \overline{G′ \ e(G′)} are not graphs in our sense, but there is an obvious functor (composite of inclusion and quotient) f(G′) → \overline{G′ \ e(G′)}. The bijection ρ induces a functor f(G′) → G′ \ v which takes a free flag of G′ to its image under ρ in G \ v. We define G ∘_{ρ} G′ to be the categorical pushout

[figure: f(G′); \overline{G′ \ e(G′)}; G \ v; ρ; G ∘_{ρ} G′]

which is easily seen to be a graph in our sense. This graph insertion has obvious associativity and commutativity properties. Moreover, the corollas serve as right units. Observe that G′ can be considered as a subgraph of G ∘_{ρ} G′.

Insertion of free-living edges removes vertices. More precisely, insertion of a free-living edge into the unique vertex of a pointed loop (resp. corolla with two external edges) yields a free-living loop (resp. free-living edge).

If G′′ is obtained by insertion of a graph G′ into a vertex of a graph G then we will say dually that G is the result of contracting G′ inside G′′.

13.2. Trees, forests and other special graphs. The realisation of a graph G is the geometric realisation of (the simplicial nerve of) the underlying category.

A graph G is connected (resp. a tree) if the realisation of G is connected (resp. contractible). A graph G is a forest if it is a finite coproduct of trees.

A rooted tree is a tree with a distinguished external edge called root; the other external edges of the tree are called leaves or input edges. In a rooted tree T the corolla cor_{v}(T) attached to a vertex v has a canonical structure of rooted tree. The input edges (resp. root) of this “local” tree cor_{v}(T) will be called the incoming edges (resp. outgoing edge) of v. Morphisms of rooted trees are morphisms of the underlying graphs which preserve the outgoing edges of the vertices.

A graph is called a rooted forest if it is a finite coproduct of rooted trees. There are some types of graphs which we would like to give separate names:

– A linear tree on n vertices L_{n} is a tree with n vertices and n + 1 edges two of which are external. In particular, L_{0} denotes the free-living edge.

– A linear graph on n vertices [1, n] is a tree with n vertices and n − 1 internal edges and no external edges. We will call the two vertices with only one edge attached the boundary vertices of [1, n]. A path between two vertices v_{1}, v_{2} of a graph G is a graph morphism [1, n] → G taking the boundary vertices to v_{1}, v_{2}.

A non-empty graph G without free-living edges/loops is connected (resp. a tree) if and only if for any ordered pair of vertices there is a (unique) path between them.

13.3. Ordered graphs and ordered trees. A graph is said to be partially ordered if the set of its free flags is linearly ordered. A graph G is said to be ordered if G as well as the corollas cor_{v}(G) for the vertices v of G are partially ordered.

In particular, an ordered corolla with vertex v carries two linear orderings: a linear ordering of the set of its free flags and a linear ordering the set of its v-flags:

[figure: 1; 3; 2; 3; 2; 1]

An isomorphism between ordered graphs is an isomorphism of the underlying graphs which preserves all orderings.

An ordered rooted tree is a rooted tree which is ordered as a tree in such a way that the external root and the roots (i.e. outgoing edges) of the corollas are the first elements of the respective linear orderings. This implies that we can forget about the external root and the roots of corollas and keep only the linear orderings of the input edges of the tree and of the incoming edges for each vertex of the tree.

An ordered rooted forest is a finite coproduct of ordered rooted trees.

Ordered graphs admit an operation of graph insertion which depends only on compatibility conditions between graphs. The bijection ρ between the free flags of G′ and the v-flags of G is uniquely determined by the linear orderings once the cardinalities are the same. We therefore can speak unambiguously about the insertion of G′ into the vertex v of G, the result of which shall be denoted G′ ∘_{v} G. The unit for this ordered graph insertion is given by those ordered corollas for which the linear ordering of the free flags coincides with linear ordering of the v-flags.

We can easily check that the subcategories of ordered trees (forests), ordered rooted trees (forests) are closed under graph insertion and, hence, induce a well defined graph insertion on isomorphism classes of the corresponding groupoids.

Each isomorphism class of ordered rooted trees has a unique representative by a planar rooted tree equipped with a linear ordering of its input edges.

13.4. Directed graphs and directed trees. A directed graph is a graph with a chosen arrow in each span f_{1} → e ← f_{2} for each edge e of the graph. Such a choice amounts to the choice of an orientation for this edge. Morphisms of directed graphs are required to preserve these chosen arrows.

In a directed graph the v-flags of a vertex v are subdivided into incoming and outgoing flags. The same is true for free flags. A directed ordered graph is a directed graph with a linear ordering of all outgoing and a linear ordering of all incoming free flags, as well as linear orderings of incoming v-flags and linear orderings of outgoing v-flags for each vertex v. Directed graph-insertion is defined like in the non-directed case assuming in addition that the bijection ρ is orientation-reversing.

Any rooted tree admits two canonical orientations from top to bottom or vice versa. We always orient a rooted tree from top to bottom. We also have a directed version of the linear graph [1, n] with the direction going from p to p − 1.

A loop in a directed graph G is any map of directed graphs s : [1, n] → G, n ≥ 2, for which s(1) = s(n) or any map from the free living loop l to G.

A loop-free graph is a directed graph which has no loops. Loop-free graphs are closed under graph-insertion.

14. Planar trees and n-planar trees

14.1. Planar trees. A subgraph G′ of a graph G is called plain if for each vertex v of G′, the cardinalities of the set of v-flags are the same in G′ and in G. For any pair (T, T′) consisting of a tree T and plain subtree T′ of T there is a well-defined function, called contraction

C_{(T,T′)} : e(T) → e(T′)  (32)

taking external edges of T to external edges of T′. This function is constructed as follows. For each external edge e of T there exists a unique n ≥ 0 and a unique injective map γ_{e} from the rooted tree L_{n}^{rt} to T with the following three properties:

(i) γ_{e} takes the unique input edge of L_{n}^{rt} to e;

(ii) γ_{e} takes the root rt of L_{n}^{rt} to an external edge of T′;

(iii) the image of γ_{e} does not contain any vertices of T′.

We then define C_{(T,T′)}(e) = γ_{e}(rt).

We introduce a special notation if T′ is the corolla cor_{v}(T) of a vertex v of T, namely

C_{v} = C_{(T,cor_{v}(T))} : e(T) → e(cor_{v}(T))  (33)

and call it v-contraction. If T is an ordered tree then e(T) and e(cor_{v}(T)) are linearly ordered. We will say that the ordered tree T is planar if for each vertex v of T the vcontraction preserves the linear orders up to cyclic permutation, which means that the v-contraction becomes an order-preserving map after cyclic permutation of the set of external edges of cor_{v}(T).

If T is a rooted tree then the sets e(T) and e(cor_{v}(T)) are pointed by the respective roots and the v-contraction is a map of pointed sets which restricts away from the roots. By abuse of notation we consider the v-contractions of a rooted tree as restricted to the set of input edges. Accordingly, an ordered rooted tree is planar if and only if for each vertex v the v-contraction is order-preserving.

The subcategories of planar and planar rooted trees are closed under graph insertion and there is a graph insertion on isomorphism classes of the corresponding groupoids.

14.2. Higher planar rooted trees. The notion of n-planar rooted tree generalises linear and planar rooted trees. A partially n-ordered rooted tree T is a rooted tree equipped with the structure of n-ordinal on the set of incoming edges of each vertex v of T. An n-ordered rooted tree T is a partially n-ordered rooted tree equipped with an n-ordinal structure on the set of free flags of T. Since each n-ordinal induces a linear order on its underlying set, such a tree has a canonical structure of ordered rooted tree.

We say that T is an n-planar tree if for each v the contraction function C_{v} is a map of n-ordinals. For instance, 0-planar trees are linear rooted trees and 1-planar trees are planar rooted trees as previously defined. Each isomorphism class of partially n-ordered rooted trees contains a unique planar representative. Therefore, an n-planar tree τ is a planar rooted tree with the following additional structure:

• Each vertex v is decorated by an n-ordinal τ_{v} whose underlying linear ordered set coincides with the set of incoming edges of v;

• The leaves are labelled by natural numbers from 1 to p where p is the number of leaves of τ;

Such a labelled decorated tree becomes an n-planar tree if we fix as well an n-ordinal S with underlying set |S| = {1, …, p} such that the following compatibility condition holds:

Recall (cf. [5]) that the set L(τ) of leaves of an n-ordered tree τ has a canonical structure of n-ordered set. Let k, l ∈ L(τ) be leaves of τ and let v(k, l) be the upmost vertex of τ which lies below k and l in τ. The shortest edge-path in τ which begins with k (resp. l) and ends at v(k, l) determines a unique incoming edge of v(k, l), and hence a unique element e_{k} (resp. e_{l}) of |τ_{v(k,l)}|. By definition we have k <_{r} l in L(τ) precisely when e_{k} <_{r} e_{l} in the n-ordinal τ_{v(k,l)}.

The n-planarity of the pair (τ, S) amounts then to the requirement that S dominates the n-ordered set L(τ) in the sense of Definition 12.3. This “planar” description of nplanar trees is quite efficient. For example, the decorated tree τ on the left hand side

1 3 5 2 4 7 6

Figure 8: A 2-planar tree as a labelled decorated tree with dominating 2-ordinal.

acquires an n-planar structure if we just add that the induced 2-ordered set L(τ) is dominated by the 2-ordinal as depicted on the right hand side.

14.3. Regular and normal n-planar trees and the geometry of Fulton-MacPherson operad. An n-planar tree is called regular if all its decorated ordinals are regular. An n-planar tree is called normal if all its decorated ordinals are normal.

Normal n-planar trees are closely related to the geometry of the Getzler-Jones decomposition of the Fulton-MacPherson operad of point configurations in ℝ^{n} [5, 25, 47]. Recall that the quotient of F (ℝ^{n}, k) by the Lie group generated by dilatations and translations is called the moduli space of configurations Mod^{n}(k). This moduli space has the same homotopy type as F (ℝ^{n}, k). The Fox-Neuwirth stratification descends to a stratification of Mod^{n}(k). Applying Fulton-MacPherson compactification to this stratification we obtain the k-th space of the Fulton-MacPherson operad together with its Getzler-Jones decomposition [25]. The cells of this decomposition are in one-to-one correspondence with labelled decorated trees [5]. For instance, the labelled decorated tree of Figure 4 corresponds to the following 6-dimensional Getzler-Jones cell (the so-called ‘bad’ cell of Tamarkin [5, 47]):

1 3 5 2 4 6

A normal n-planar tree τ contains extra information about the corresponding Getzler-Jones cell. Namely, the n-ordinal S on the leaves of τ expresses that the boundary of the closure of the Fox-Neuwirth cell F N_{S} has a non-empty intersection with the Getzler-Jones cell represented by τ, i.e. the latter lives in the S-space of the Getzler-Jones n-operad constructed by the first author in [5]. For example, the tree of Figure 4 is a normal 2-planar tree with leaf 2-ordinal given by the 2-ordinal S. Example 12.5 tells us that the 6-dimensional Getzler-Jones cell above contains part of the boundary of the 6-dimensional Fox-Neuwirth cell F N_{S} ⊂ Mod^{2}(6) (this part of the boundary is actually a 5-dimensional contractible manifold with corners [5, 47]).

14.4. Insertion and contraction of n-planar trees. Since n-planar trees are in particular ordered rooted trees, graph insertion of an n-planar rooted tree inside a vertex of another n-planar rooted tree is well defined. The result of this graph insertion is in general just an n-ordered rooted tree unless we require a compatibility condition of the corresponding n-ordinal structures. This compatibility condition is the following: an nplanar tree τ′ inserts into a vertex v of an n-planar tree τ if the bijection ρ_{v} induced by the n-order structures of τ and τ′ (see 13.3) is an isomorphism between the leaf n-ordinal of τ′ and the corolla n-ordinal τ_{v}. It is now easy to check that the resulting tree has a canonical n-planar structure. This operation preserves isomorphism classes of n-planar trees. Normal and regular n-planar trees are closed under graph insertion and so are their isomorphism classes.

For instance, graph insertion of the 2-planar tree of Figure 5 as shown in Figure 9

1 3 5 2 4 7 6 1 3 2

Figure 9: Insertion of a 2-planar tree to a vertex of another 2-planar tree.

yields the 2-planar tree of Figure 8.

If an n-planar tree τ′′ is obtained by an insertion of an n-planar tree τ′ into a vertex of an n-planar tree τ we will say that τ is the result of contracting τ′ inside τ′′.

For instance, the graph insertion of Figure 9 corresponds to the following contraction:

1 3 5 2 4 7 6  ^{1 3 5 2 4 7 6}

Figure 10: Contraction of a 2-planar tree.

14.5. Insertion of normal n-planar trees and multiplication in Fulton-MacPherson operad. Insertion of normal n-planar trees is closely related to the multiplication of the Fulton-MacPherson operad [5]. In fact, it can be explained in terms of infinitesimal substitutions of point configurations. For the example of Figure 9 we have two infinitesimal configurations in the Fulton-MacPherson operad

1 3 5 2 4 7 6 and 3 1 2

Then we substitute the configuration on the first line to the point 1 in the second picture, the second line to the point 2 in the second picture and the third line to the point 3 in the second picture. The resulting configuration is therefore

1 3 5 2 4 7 6

which corresponds exactly to the tree of Figure 8.

15. Other definitions of graphs

Since there are many different treatments of graphs in the literature we include several of them and describe briefly the relationship with our definition. The order is not chronological nor it is related to the importance and popularity.

15.1. Feynman graphs of Joyal-Kock. In [33] Joyal and Kock define a Feynman graph Γ as a span in finite sets:

E ←^{s} H →^{t} V

equipped with a fixed point free involution ι : E → E such that s is an injection. The elements of V are called vertices, the elements of H half-edges and the elements of E oriented edges.

To any Feynman graph Γ one can assign a graph G in our sense as follows. The set of vertices of G is the set V. The set of flags of G is the set E. The set of edges of G is the set of orbits of ι. There is a unique morphism from a flag h to a v ∈ V if h = s(h̄). The target v of this map is t(h̄). For any flag there is a unique map from it to its orbit. One checks that this construction produces a graph in our sense.

15.2. Proposition. The set of isomorphism classes of Feynman graphs embeds into the set of isomorphism classes of graphs in our sense. A graph in our sense is not a Feynman graph if and only if it contains a connected component isomorphic to a free living loop.

Proof. If a graph G does not contain free-living loops we can reconstruct a Feynman graph Γ as follows. The set of vertices of Γ will be equal to the set of vertices of G. The set of half-edges will be the set of non-free flags of G. The set of oriented edges will be equal to the set of all flags of G and the involution exchanges the adjacent flags. Since G does not contain free-living loop this involution is fixed-point free.

15.3. Getzler-Kapranov graphs. In [16, 19, 26] a slightly different definition of a graph has been used (attributed to Kontsevich-Manin by Getzler and Kapranov) : a graph Γ is a map of sets π : H → V together with an involution σ : H → H, σ^{2} = 1. We can construct a Feynman graph Γ in the sense of Joyal-Kock as follows. The set of vertices of Γ is V. The set of flags of Γ is H and t = π. The set of oriented edges of Γ is equal to H ⊔ H^{σ} where H^{σ} is the set of fixed points of σ (so we simply add to H one extra point for each fixed point of σ) and s is the first coprojection. The involution ι maps each fixed point h to its copy in H^{σ} and coincides with σ(h) if h is not a fixed point of σ.

This shows that the set of isomorphism classes of Getzler-Kapranov graphs is a subset of the set of isomorphism classes of Feynman graphs. The difference is in the treatment of graphs without vertices which exist in the latter but not in the former setting.

15.4. Johnson-Yau graphs. This type of graph was introduced in [46, 48] and studied extensively by Johnson-Yau [32] paying special attention to free-living edges and loops.

15.5. Definition. [32] A generalised graph 𝔾 is a finite set F lag(𝔾) with involution ι, together with a partition and choice of an isolated cell 𝔾_{0} such that there is a fixed-point free involution π on the set of fixed points of ι within 𝔾_{0}.

Here a partition is a presentation of a finite set as a finite coproduct of some finite sets called cells (empty cells are allowed). An isolated cell of a partition with an involution is a cell invariant under the involution.

For each Johnson-Yau graph we can construct a graph G in our sense as follows. A vertex of G is a cell of 𝔾 which is not an exceptional cell of 𝔾_{0}. The flags of G are (F lag(𝔾) \ 𝔾_{0}) ⊔ (F lag(𝔾) \ 𝔾_{0})^{ι} as well as all orbits of ι on 𝔾_{0}. For h ∈ F lag(𝔾) \ 𝔾_{0} which is not a fixed point of ι we have an edge e(h) such that e(h) = e(ιh) and a unique morphism in G from h to e. For a fixed point h of τ in (F lag(𝔾)\𝔾_{0}) its adjacent belongs to (F lag(𝔾) \ 𝔾_{0})^{ι} and we have a morphism from h and its adjacent to e.

For a non-trivial orbit h of ι in 𝔾_{0} there are an edge in G and exactly two morphisms from h to this edge in G. Finally, for each orbit of π there is one edge in G and a morphism from each element of this orbit to this edge.

15.6. Proposition. This construction determines a bijection between isomorphism classes of graphs in our sense and isomorphism classes of Johnson-Yau graphs.

15.7. Joyal-Street graphs. According to Joyal-Street [34] a topological graph is a Hausdorff space G with a discrete closed subset G_{0} (the set of vertices of G) such that G \ G_{0} is a 1-manifold without boundary (empty 1-manifold is allowed).

A graph with boundary is a pair (Γ, ∂Γ) where Γ is a compact topological graph and ∂Γ is a subset of its set of vertices such that each x ∈ ∂Γ is of degree 1. The last thing means that the space V \x has one connected component, where V is a sufficiently small connected neighbourhood of x. Morphisms between graphs with boundary are homeomorphisms taking vertices to vertices and boundary points to boundary points.

15.8. Proposition. Geometric realisation provides a bijection between isomorphism classes of graphs in our sense and isomorphism classes of Joyal-Street graphs with boundary.

Proof. Geometric realisation produces a topological graph with boundary where the boundary points correspond to free flags. For the inverse correspondence we assume that each closed edge of Γ is parametrised by a bijective continuous function from the interval [0, 1] so that it makes sense to consider t-points, t ∈ [0, 1], on the edges of Γ.

For (Γ, ∂Γ) we construct a categorical graph G by taking as its vertices the set of vertices of Γ minus the set ∂Γ of boundary points. The set of edges of G is the set of 1/2-points on the edges of the topological graph Γ. The set of adjacent flags is the set of 1/4- and 3/4-points on those edges of Γ which connect two non-boundary points. For an edge which connects a boundary point to a non-boundary point we take the non-boundary point as a flag and the middle point of the interval between the non-boundary point and the 1/2-point as its adjacent. If an edge connects two non-boundary points then we take those points as flags of G. The morphisms in G are obvious from the following example:

In this picture large dots correspond to the vertices of the topological graph and green dots correspond to the vertices of the categorical graphs, white dots correspond to the boundary points and the free flags of the categorical graph, black dots correspond to the non-free flags of the categorical graph and red dots correspond to its edges.

Proposition 15.8 justifies the representation of graphs and trees used in this paper.

Acknowledgements. We wish to express our gratitude to G. Caviglia, D.-C. Cisinski, B. Fresse, E. Getzler, M. Johnson, A. Joyal, J. Kock, S. Lack, A. Lazarev, G. Maltsiniotis, M. Markl, F. Muro, S. Schwede, R. Street, B. Vallette and D. Yau for many useful comments and conversations. Special thanks go to Mark Weber for numerous

250  M. A. BATANIN AND C. BERGER

enlightening discussions about polynomial monads and 2-dimensional monad theory, and to the referee whose careful reading helped us to eliminate several inaccuracies and to ameliorate considerably the presentation.

The authors gratefully acknowledge the financial support of Scott Russell Johnson Memorial Foundation, Max Plank Institut für Mathematik in Bonn, Newton Institute of Mathematical Science in Cambridge, the Australian Research Council (grants DP0558372, DP130101172) and the French Agence Nationale de Recherche (grant HOGT).

References

[1] Ara D., Maltsiniotis G., Towards a Thomason model structure on the category of strict n-categories, Adv. Math. 259 (2014), 557–654.

[2] Baez J., Dolan J.,Higher-dimensonal algebra and topological quantum field theory, J. Math. Phys. 36 (1995), 6073–6105.

[3] Baez J., Dolan J., Higher-dimensonal algebra III, n-categories and the algebra of opetopes, Adv. Math. 135 (1998), 145–206.

[4] Barwick C., On left and right model categories and left and right Bousfield localizations, Homology, Homotopy and Appl. 12 (2010), 245–320.

[5] Batanin M. A., The symmetrization of n-operads and compactification of real configuration spaces, Adv. Math. 211 (2007), 684–725.

[6] Batanin M. A., The Eckmann-Hilton argument and higher operads, Adv. Math. 217 (2008), 334–385.

[7] Batanin M. A., Locally constant n-operads as higher braided operads, J. Noncommut. Geom. 4 (2010), 237–263.

[8] Batanin M. A., An operadic proof of Baez-Dolan stabilization hypothesis, to appear in Proc. Amer. Math. Soc. (2017), arXiv:1511.09130.

[9] Batanin M. A., Higher braided operads and stabilization phenomena, in preparation.

[10] Bénabou J., Some remarks on free monoids in a topos, Lect. Notes Math. 1488, Springer Verlag, Berlin, 1991, 20–29.

[11] Berger C., Moerdijk I., Axiomatic homotopy theory for operads, Comment. Math. Helv. 78 (2003), 805–831.

[12] Berger C., Moerdijk I., The Boardman-Vogt resolution of operads in monoidal model categories, Topology 45 (2006), 807–849.

[13] Berger C., Moerdijk I., Resolution of coloured operads and rectification of homotopy algebras, Contemp. Math. 431 (2007), 31–58.

[14] Berger C., Moerdijk I., On the homotopy theory of enriched categories, Q. J. Math. 64 (2013), 805–846.

[15] Boardman J. M., Vogt R. M., Homotopy invariant algebraic structures on topological spaces, Lect. Notes Math. 347, Springer Verlag, Berlin, 1973.

[16] Borisov D., Manin Y., Generalized operads and their inner cohomomorphisms, Geometry and dynamics of groups and spaces. Birkhauser, Progress in Math., vol. 265 (2008), 247–308.

HOMOTOPY THEORY FOR ALGEBRAS OVER POLYNOMIAL MONADS  251

[17] Cisinski D.-C., Locally constant functors, Math. Proc. Camb. Phil. Soc. 147 (2009), 593–614.

[18] Cisinski D.-C., Moerdijk I., Dendroidal sets and simplicial operads, J. Topology 6 (2013), 705–756.

[19] Costello K, The A_{∞}-operads and the moduli space of curves, arXiv:0402015v2.

[20] tom Dieck T., Algebraic Topology, Textbooks in Math., Europ. Math. Soc., Zürich, 2008.

[21] Dundas B. I., Østvær P.-A., Röndigs O., Enriched Funtors and Stable Homotopy Theory, Doc. Math. 8 (2003), 409–488.

[22] Fresse B., PROP’s in model categories and homotopy invariance of structures, Georgian Math. J. 17 (2010), 79–160.

[23] Fresse B., Homotopy of operads & Grothendieck-Teichmüller groups I, Amer. Math. Soc., 2017.

[24] Gambino N., Kock J., Polynomial functors and polynomial monads, Math. Proc. Camb. Philos. Soc. 154 (2013), no. 1, 153–192.

[25] Getzler E., Jones J. D. S., Operads, homotopy algebras and iterated integrals for double loop spaces, hep-th/940355.

[26] Getzler E., Kapranov M., Modular operads, Compos. Math. 110 (1998), 65–126.

[27] Giansiracusa J., The framed little 2-discs operad and diffeomorphisms of hadlebodies, J. Topology 4 (2011), 919–941.

[28] Ginzburg V., Kapranov M., Koszul duality for operads, Duke Math. J. 76 (1994), 203–272.

[29] Goerss P., Jardine J. F., Simplicial homotopy theory, Progress in Math., Modern Birkhäuser Classics. Basel, 2009.

[30] Guitart R., Relations et carrés exacts, Ann. Sc. Math. Québec IV (1980), 103–125.

[31] Hackney P., Robertson M., Yau D., Relative left properness of colored operads, Algebr. & Geom. Topol. 16 (2016), 2691–2714.

[32] Johnson M. W., Yau D., A Foundation for PROP’s, Algebras, and Modules, Math. Surveys Monogr., vol. 203, Amer. Math. Soc. 2015.

[33] Joyal A., Kock J., Feynman graphs, and nerve theorem for compact symmetric multicategories (extended abstract), Electr. Notes in Theor. Comput. Sci. 270 (2011), 105–113.

[34] Joyal A., Street R., The geometry of tensor calculus I, Adv. Math. 88 (1991), 55–112.

[35] Hill M. A., Hopkins M. J., Ravenel D. C., On the non-existence of elements of Kervaire invariant

    one, arXiv:0908.3724v4.

[36] Hirschhorn P., Model Categories and their Localizations, Math. Surveys Monogr., vol. 99, Amer. Math. Soc., Providence, RI, 2003.

[37] Hovey M., Model Categories, Math. Surveys Monogr., vol. 63, Amer. Math. Soc., 1999.

[38] Kock J., Polynomial functors and trees, Int. Math. Res. Notices 3 (2011), 609–673.

[39] Kock J., Joyal A., Batanin M., Mascari J.-F., Polynomial functors and opetopes, Adv. Math. 224 (2010), 2690–2737.

[40] Kontsevich M., Operads and motives in deformation quantisation, Lett. Math. Phys. 48 (1999), 35–72.

[41] Lack S., A Quillen model structure for 2-categories, K-theory 26 (2002), 171–205.

[42] Lack S., Codescent objects and coherence, J. Pure Appl. Algebra 175 (2002), 223–241.

252  M. A. BATANIN AND C. BERGER

[43] Leinster T., Higher Operads, Higher Categories, London Math. Soc. Lect. Notes, Camb. Univ. Press, Cambridge, 2004.

[44] Loday J.-L., Vallette B., Algebraic Operads, Springer-Verlag Berlin Heidelberg, A series of Comp. Studies in Math., 2012.

[45] Lurie J., Higher Topos Theory, Annals of Math. Studies 170, Princeton University Press, Princeton, NJ, 2009.

[46] Markl M., Operads and PROP’s, in Elsevier, Handbook of Algebra vol. 5 (2008), 87–140.

[47] Markl M., An E_{∞}-extension of the associahedra and the Tamarkin cell mystery, J. Geom. Phys. 98 (2015), 446–471.

[48] Markl M., Merkulov S., Shadrin S., Wheeled PROP’s, graph complexes and master equation, J. Pure Appl. Algebra 213 (2009), 496–535.

[49] May J. P., The geometry of iterated loop spaces, Lect. Notes Math. 271, Springer-Verlag, Berlin, 1972.

[50] May J. P., Ponto K., More Concise Algebraic Topology. Localization, completion and model categories, Chicago Lect. Math., Illinois, 2012.

[51] Moerdijk I., Palmgren E., Wellfounded trees in categories, Annals of Pure and Applied Logic 104 (2000), 189-218.

[52] Muro F., Homotopy theory of non-symmetric operads, Algebr. & Geom. Topol. 11 (2011), 1541– 1599.

[53] Muro F., Homotopy theory of non-symmetric operads II: change of base category and left properness, Algebr. & Geom. Topol. 14 (2014), 229–281.

[54] Power A. J., A general coherence result, J. Pure Appl. Algebra 57 (1989), 165–173.

[55] Quillen D. G., Homotopical algebra, Lect. Notes Math. 43, Springer-Verlag, Berlin, 1967.

[56] Rezk, C., Fibrations and homotopy colimits of simplicial sheaves, arXiv:math.AT/9811038.

[57] Rezk, C., A cartesian presentation of weak n-categories, Geom. & Topol. 14 (2010), 521–571.

[58] Szawiel S., Zawadowski M., Theories of analytic monads, Math. Struct. Comp. Sci. 24 (2014).

[59] Schwede S., An untitled book project about symmetric spectra, homepage of Stefan Schwede.

[60] Schwede S., Shipley B. E., Algebras and modules in monoidal model categories, Proc. London Math. Soc. 3 (2000), 491–511.

[61] Spitzweck M., Operads and algebras in general model categories, arXiv:math/0101102.

[62] Tambara D., On multiplicative transfer, Comm. Algebra 21 (1993), 1393–1420.

[63] Vallette B., Koszul duality for props, Trans. Amer. Math. Soc. 359 (2007), 4865–4943.

[64] Weber M., Polynomials in categories with pullbacks, Theory Appl. Categ. 30 (2015), 533–598.

[65] Weber M., Operads as polynomial 2-monads, Theory Appl. Categ. 30 (2015), 1659–1712.

[66] Weber M., Internal algebra classifiers as codescent objects of crossed internal categories, Theory Appl. Categ. 30 (2015), 1713–1792.

[67] Weber M., Algebraic Kan extensions along morphisms of internal algebra classifiers, Tbilisi Math. J. 9 (2016), 65–142.

Macquarie University, North Ryde, 2109 Sydney, Australia.

Université de Nice, Lab. J. A. Dieudonné, Parc Valrose, 06108 Nice, France.

Email: michael.batanin@mq.edu.au
      cberger@math.unice.fr
This article may be accessed at http://www.tac.mta.ca/tac/

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available from the journal’s server at http://www.tac.mta.ca/tac/. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors The typesetting language of the journal is TEX, and L^{A}TEX2e is required. Articles in PDF format may be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis: cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com Valeria de Paiva: Nuance Communications Inc: valeria.depaiva@gmail.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne: kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh: Tom.Leinster@ed.ac.uk Ieke Moerdijk, Utrecht University: i.moerdijk@uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Ljubljana: Alex.Simpson@fmf.uni-lj.si James Stasheff, University of North Carolina: jds@math.upenn.edu Ross Street, Macquarie University: ross.street@mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Université du Québec à Montréal : tierney.myles4@gmail.com R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca