Collectanea Mathematica https://doi.org/10.1007/s13348-022-00386-1 Plethysms and operads Alex Cebrian1 Received: 13 December 2021 / Accepted: 8 November 2022 © The Author(s) 2023 Abstract We introduce the T-construction, an endofunctor on the category of generalized operads, as a general mechanism by which various notions of plethystic substitution arise from more ordi- nary notions of substitution. In the special case of one-object unary operads, i.e. monoids, we recover the T -construction of Giraudo. We realize several kinds of plethysm as convo- lution products arising from the homotopy cardinality of the incidence bialgebra of the bar construction of various operads obtained from the T-construction. The bar constructions are simplicial groupoids, and in the special case of the terminal reduced operad Sym, we recover the simplicial groupoid of Cebrian (Algebraic Geom Topol 21(1):421–446, 2021), a combi- natorial model for ordinary plethysm in the sense of Pólya, given in the spirit of Waldhausen S and Quillen Q constructions. In some of the cases of the T-construction, an analogous interpretation is possible. Mathematics Subject Classification 05A19 · 18B40 · 18N50 · 16T10 · 18M65 · 18M80 · 13J05 List of symbols Grpd Category of groupoids and groupoid morphisms Set Category of sets and set maps (P, μ, η) Generic strong cartesian monad (1.1.1 and 1.3.1) Id Identity monad (1.3.3) M Free monoid monad (page 8) r M Free semigroup monad (1.3.5) S Free symmetric monoidal category monad (1.3.7) r S Free symmetric semimonoidal category monad (1.3.8) L Monad A  → P1×A (page 22) Y Generic (locally finite) monoid (1.3.6) Y Monad given by A  → Y ×A, for Y a monoid (1.3.6) TY Giraudo T -construction of Y (4.1.3) D A,B Strength natural transformation (1.3.1) This work has received support from Grant Number MTM2016-80439-P of Spain. B Alex Cebrian acebrian@mat.uab.cat 1 Departament de Matemàtiques, Universitat Autònoma de Barcelona, Bellaterra, Spain 123 A. Cebrian DB Strength for A = 1 (page 22) RA Projection P1×A  → A (page 22) B Two-sided bar construction (page 16) BP Two-sided bar construction relative to a monad P (page 19) Bn n-Simplices of the two-sided bar construction B (page 16) ◦ Bn Subgroupoid of connected objects of Bn (page 49) Sym The reduced symmetric operad (1.3.8) Ass The reduced associative operad (1.3.5) E Generic ambient cartesian category, mainly Set or Grpd) (1.1) C Category internal to E (page 8) Q P-operad internal to E (page 8) Q0, Q1 Objects and operations of Q (page 8) (Q, μ Q , η Q ) Monad on E/Q 0 defined by the P-operad Q (page 14) TP C T-construction from C to a P-operad (page 22) TP Q T-construction from a P-operad to a category C (page 27) TP Q T-construction from a P -operad to a P-operad (page 32)  Set of infinite vectors λ = (λ1 , λ2 , . . . ) of natural numbers with λi = 0 for all i large enough (page 40) 1 Simplex category (page 16) TS Simplicial groupoid of [9] (page 55) Contents Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1 Monads and operads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1 P-operads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Morphisms of spans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Strong monads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 The two-sided bar construction for P-operads . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Segal groupoids and incidence coalgebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1 Segal groupoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Incidence coalgebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Homotopy cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 The T-construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 From categories to P-operads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 From P-operads to categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 The composite construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Finiteness conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 r r 4 T-construction for M and S -operads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1 The T-construction for categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 The T-construction for operads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5 Plethysms and operads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.1 The classical case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2 Overview of variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Bialgebras from Sym and Sym2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.4 Bialgebras from Ass and Ass2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.5 Y -plethysm and bialgebras from Y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6 Relation with T S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6.1 The simplicial groupoid T S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6.2 Other T S-like simplicial groupoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 A Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 A.1 Axioms for internal category . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Axioms for P-operad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 123 Plethysms and operads References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Introduction Plethysm is a substitution law in the ring of power series in infinitely many variables. It was introduced by Pólya [38] in unlabelled enumeration theory in combinatorics, motivated as a series analogue of the wreath product of permutation groups. Another notion of plethysm was defined by Littlewood [27] in the context of symmetric functions and representation theory of the general linear groups [30]. It appears also in algebraic topology, in connection with λ-rings [5] and power operations in cohomology [2]. The two notions of plethysm are closely related, as described in [4, 41]. The plethysms we deal with emerge from Pólya’s notion, which we proceed to recall. Let xQx be the ring of power series in the infinite set of variables x = (x 1 , x2 , . . . ) without constant term. Given F, G ∈ xQx, their plethystic substitution is defined as (G  F)(x1 , x2 , . . . ) = G(F1 , F2 , . . . ), where Fk (x1 , x2 , . . . ) = F(xk , x2k , . . . ). The formal power series may be expressed as  xλ F(x) = Fλ , aut(λ) λ where aut(λ) are certain symmetry factors (see Section 5 below). It is well appreciated in combinatorics that bijective proofs give a deeper understanding than algebraic manipulation, as well as a better ground for further development. The so-called objective method, pioneered by Lawvere [25], Joyal [22], and Baez and Dolan [1], provides a systematic approach to bijective proofs. One of the starting points of objective combinatorics is the theory of species, developed by Joyal [22] as a combinatorial theory of formal series. Within this context, Pólya enumeration theory of unlabelled structures, including cycle index series and their plethysm, was entirely renewed. However, a full combinatorial model of plethysm was only given a few years later by Nava and Rota [37]. They developed the notion of partitional, a functor from the groupoid of partitions to the category of finite sets, and showed that a suitable notion of composition of partitionals yields plethystic substitution of their generating functions, in analogy with composition of species and composition of their exponential generating functions. A variation of this combinatorial interpretation was given shortly after by Bergeron [3], who instead of partitionals considered permutationals, functors from the groupoid of permutations to the category of finite sets. This approach is nicely related to the theory of species and their cycle index series through an adjunction. Later on, Nava [36] studied both partitionals and permutationals from the point of view of incidence coalgebras, and added a third class of functors called linear partitionals. The bialgebras arising from the various plethystic substitutions are called plethystic bialge- bras in the present article. Here is a general definition, as given in [9]: the plethystic bialgebra is the free polynomial algebra on the linear functionals Aλ (F) = Fλ with comultiplication dual to plethystic substitution, (Aλ )(F, G) = Aλ (G  F). 123 A. Cebrian In this definition, the difference between the three bialgebras of Nava depends on the definition of the linear functionals Aλ , which in turn depend on the definition of the symmetry factors aut(λ). The present work introduces a construction on operads, called the T-construction, which establishes a relationship between ordinary substitutions and plethystic substitutions. In par- ticular, this construction produces combinatorial models for the partitional and the linear partitional (also called exponential) cases, but also for other kinds of plethysm: plethysm of power series with variables indexed by a (locally finite) monoid, introduced by Méndez and Nava [34] in the course of generalizing Joyal’s theory of colored species to an arbitrary set of colors; plethysm in two variables x, y; plethysm of series with coefficients in a noncom- mutative ring, in the style of [6], and plethysm of series with noncommuting variables. All these plethysms and their bialgebras are explained in Section 5. The T-construction relies on operads and the theory of decomposition spaces and their incidence bialgebras. The theory of operads has long been a standard tool in topology and algebra [28, 31], and in category theory [26], and it is getting increasingly important also in combinatorics [21, 33]. In the present work, for maximal flexibility, we work with operads in the form of generalized multicategories [26]. This allows us to cover simultaneously notions such as monoids, categories, nonsymmetric operads and symmetric operads. On the other hand, decomposition spaces (certain simplicial spaces) provide a general machinery to objectify the notion of incidence algebra in algebraic combinatorics. They were introduced by Gálvez, Kock and Tonks [16–18] in this framework, and they are the same as 2-Segal spaces introduced by Dyckerhoff and Kapranov [13] in the context of homological algebra and representation theory. To recover the algebraic incidence coalgebra from the categorified incidence coalgebra one takes homotopy cardinality, a cardinality functor defined from groupoids to the rationals. It was shown in [24] that the two-sided bar construction [32, 46] of an operad is a Segal groupoid, a particular type of decomposition space, and classical constructions of bialgebras arising from operads factor through this construction (see [11, 42, 43] for related construc- tions). Next we give two relevant examples of bialgebras that arise as incidence bialgebras of operads. Example Let xQx  be the ring of formal power series in x without constant term, and let F, G ∈ xQx . The Faà di Bruno bialgebra F is the free algebra Q[A1 , A2 , . . . ], where An ∈ xQx ∗ is the linear map defined by dn F An (F) = . dxn Its comultiplication is defined to be dual to substitution of power series. That is (An )(F, G) = An (G ◦ F). It is a result of Joyal [22, §7.4] that this bialgebra can be objectified by using the category of finite sets and surjections S. In the context of Segal spaces and incidence bialgebras the result reads as follows: the Faà di Bruno bialgebra F is isomorphic to the homotopy cardinality of the incidence bialgebra of the fat nerve N S of the category S. The comultiplication here is given by summing over factorizations of surjections. Example In earlier work [9] the author found a simplicial groupoid T S (like N S arising from the category of surjections cf. 6 below), which plays the same role for plethystic substitution: the homotopy cardinality of the incidence bialgebra of T S is isomorphic to the (partitional) 123 Plethysms and operads plethystic bialgebra. The comultiplication extracted from this simplicial groupoid can be interpreted as summing over certain transversals of partitions, as in the work of Nava and Rota [37]. Now, it is well-known that N S is equivalent to the two-sided bar construction of Sym, the terminal reduced symmetric operad. This equivalence takes the surjection n  1 to the unique n-ary operation, and the comultiplication of an operation runs through all possible 2-step factorizations. For example    = ⊗ +3 ⊗ + ⊗ . The starting point of the present work is the observation that also T S is equivalent to the two-sided bar construction of an operad. As we shall see, this operad can be obtained from Sym by the aforementioned T-construction, which makes sense for any (nice enough) operad. As stated above, this construction leads to many other flavors of plethysm, some of which had already been studied in various contexts. For instance, from Ass, the reduced associative operad, we obtain the exponential plethystic bialgebra, and from n-colored Sym or Ass, we obtain the n-variables plethystic bialgebra. The results relating the bialgebras to these operads are explained in Section 5. Let us give a brief introduction to the T-construction. The word T-construction comes from the simplicial T -construction [9], where T stands for transversal (in the sense of Nava–Rota [37]), and which is analogous to Waldhausen S and Quillen Q constructions. By coincidence Giraudo [20] had used the same letter T for a functor from monoids to nonsymmetric operads. The T-construction of the present work encompasses both these constructions, and the letter T has been maintained, but now in a fancier font. Let us first describe Giraudo’s T -construction [20]. Let (Y , ·, 1) be a monoid. Then  T Y := T Y (n), n≥0 where for all n ≥ 1, T Y (n) := {(x1 , . . . , xn ) | xi ∈ Y for all i = 1, . . . , n}, so that the n-ary operations are n-tuples of elements of Y . The substitution law in T Y , ◦i : T Y (n) × T Y (m) −→ T Y (n + m − 1), is defined as follows: for all x ∈ T Y (n), y ∈ T Y (m), and i = 1, . . . , n, x ◦i y := (x1 , . . . , xi−1 , xi · y1 , . . . , xi · ym , xi+1 , . . . , xn ). Our T-construction is developed in the context of P-operads (generalized multicategories in Leinster [26] terminology), for P a cartesian monad on a cartesian category E. This level of generality allows us to work with symmetric, nonsymmetric, colored and noncolored operads on the same footing. This includes also monoids and categories. A P-operad is represented by a span and two arrows m Q1 PQ 1 ×PQ 0 Q 1 Q1 s t e PQ 0 Q0 Q0 Q1, 123 A. Cebrian where Q 0 is thought of as the object of colors, Q 1 is thought of as the object of operations, s returns the P-configuration of input colors, t returns the output color, e is the unit and m is composition. All these arrows have to satisfy associativity and unit axioms. For instance, if Id is the identity monad, then an Id-operad is a category internal to E. The T-construction is in fact a composition of two constructions, one from P-operads to (internal) categories and one from categories to P-operads. The latter contains the Giraudo T -construction for the case E = Set if we consider monoids as categories with one object. However, we will mainly be interested in E = Grpd. In particular, nonsymmetric operads r r will be considered as M -operads, where M is the free semimonoidal category monad in r r Grpd, and symmetric operads as S -operads, where S is the free symmetric semimonoidal category monad in Grpd. There are two main reasons for working over Grpd: on the one hand, note that unlike nonsymmetric operads, symmetric operads cannot be portrayed as P-operads in Set, because the free commutative monoid monad is not cartesian; on the other hand, working in Grpd adapts better with the theory of decomposition spaces and incidence coalgebras. This theory uses weak notions of simplicial groupoids, slice categories, and pullbacks, but by keeping track of fibrancy we can stay within strict notions and strict monads in the style of [45]. In order for the T-construction to work, it is necessary to assume that the monads come equipped with a strength. This notion goes back to work of A. Kock [23] in enriched cate- gory theory, but it has turned out to be fundamental for the role monads play in functional programming [35, 44]. In Section 1 we recall the theory of generalized operads, the notion of strong monad, and the two-sided bar construction in this context. In Section 2 we briefly explain Segal groupoids, incidence coalgebras and homotopy cardinality. Section 3 is devoted to the T-construction, and Section 4 to some examples. Next, in Section 5 we introduce the bialgebras and state and prove the main results: the equivalence between the homotopy cardinality of the incidence bialgebras of the two-sided bar constructions of operads obtained from the T-construction and the plethystic bialgebras, as well as the Faà di Bruno bialgebra and some of its variations. Finally, in Section 6 we prove the equivalence between T S and B Sym, and we characterize some of the two-sided bar constructions as simplicial groupoids similar to T S. 1 Monads and operads As mentioned in the introduction, the T-construction fits neatly within the context of gener- alized operads and strong monads. The following discussion of generalized operads is taken from [26]. Let us start by expressing the notions of category and of plain operad in this setting. A small category C can be described by sets and functions m C1 C1 ×C0 C1 C1 s t e C0 C0 C0 C1 s t where the pullback is taken along C1 − → C0 ← − C1 , satisfying associativity and identity axioms, which can be expressed with commutative diagrams in Set (see “Appendix A.1”). The set C0 is the set of objects and C1 is the set of arrows of C. The map s returns the source of an arrow and t returns its target. The maps m and e represent composition and identities. A nonsymmetric operad can be defined in a similar way. Let M : Set → Set be the free monoid monad: it sends a set A to n∈N An (see Example 1.3.4 below). Then a nonsymmetric 123 Plethysms and operads colored set operad can be described as consisting of sets and functions m Q1 MQ 1 ×MQ 0 Q 1 Q1 s t (1.0.1) e MQ 0 Q0 Q0 Q1 satisfying associativity and identity axioms, which can be expressed with commutative diagrams in Set (see “Appendix 1”) and involve the monad structure on M. The set Q 0 is the set of objects (or colors) and Q 1 is the set of operations of Q. The map s assigns to an operation the sequence of objects constituting its source, and t returns its target. The maps m and e represent composition and identities. Operations of classical operads, such as nonsymmetric operads or symmetric operads are pictured as x , where the different types of lines represent objects or colors of Q 0 . 1.1 P-operads The above characterization of nonsymmetric Set operads can be generalized to any ambient category and any monad P as long as they are cartesian. The classical case is Set; we shall be concerned also with Grpd. Definition 1.1.1 A category is cartesian if it has all pullbacks. A functor is cartesian if it preserves pullbacks. A natural transformation is cartesian if all its naturality squares are pullbacks. A monad (P, μ, η) is cartesian if P is cartesian as a functor and μ and η are cartesian natural transformations. Given a cartesian category E and a cartesian monad (P, μ, η), we define E(P) as the bicategory whose 0-cells are the objects E of E, whose 1-cells E → E  are spans PE ← M → E  , and 2-cells are the usual morphisms M → N between spans: M d c PE E q p N. Given two 1-cells M M d c d c PE E PE  E  123 A. Cebrian the composite is given by taking a pullback and using the multiplication μ of P, and the 1-cell identity is given by η and id. They are shown in the following diagram: N  PM M Pd Pc d c E ηE id 2 P E PE  E  μE PE E PE Composition and identity of 2-cells are obvious. Since composition assumes a global choice of pullbacks, and since the pasting of two chosen pullbacks is not generally a chosen pullback, composition is associative up to coherent isomorphism. The coherence 2-cells are defined using the universal property of the pullback. Definition 1.1.2 (Burroni [7]) Let P be a cartesian monad in a cartesian category E. A P- operad is a monad in the bicategory E(P) . This means that a P-operad Q consists precisely of objects Q 0 and Q 1 of E together with maps s, t, composition m and identities e as in Diagram (1.0.1) satisfying associativity and identity axioms (“Appendix 1”). A morphism Q → Q  of P-operads is defined as a pair of f0 f1 → Q 0 , Q 1 − arrows Q 0 − → Q 1 , satisfying the following diagrams, Q1 m Q0 e Q1 PQ 1 ×PQ 0 Q 1 Q1 PQ 0 f1 Q0 f0 f1 P f 1 ×P f 0 f 1 f1 (1.1.1) P f0 Q 1 f0 Q 0 e Q 1 , PQ 1 ×PQ 0 Q 1 m Q 1 , PQ 0 Q 0 , regarding compatibility with the spans, identities and composition maps. Notice that this is not an arrow in E(P) . The category of P-operads is denoted P-Operad. 1.2 Morphisms of spans In Section 3 we will deal with morphisms between long horizontal composites of spans. It is thus worth to set up a framework for such morphisms: consider the following diagrams, named blocks, made of maps in E, · · · (1.2.1) · · · · · · · · · · · (1.2.2)   · · · · · · · · 123 Plethysms and operads · · · · · · · · · · (1.2.3) · · · · · · Notice that (1.2.2) induce isomorphisms of spans if the vertical maps are isomorphisms, since in this case they represent horizontal composition of spans. Diagram (1.2.1) is an isomorphism when all the vertical arrows are isomorphisms, and (1.2.3) are isomorphisms when all the vertical arrows and the span projected away are isomorphisms. Besides, the blocks can be horizontally and vertically attached in the obvious way to get morphisms of longer spans, with the only restriction that the diagrams (1.2.3) can be attached to the right and to the left respectively. Lemma 1.2.1 Any pasting of blocks defines a morphism between the limit of the top row and the limit of the bottom row. Moreover, such a morphism is an isomorphism if it can be constructed from blocks that are isomorphisms. The morphisms between long spans are pictured with diagrams · · · ... · · . . . . . . · · · ... · · where the left bold part is the limit of the diagram: the upper dot is the limit of the upper row, and same for the bottom row. Observe that the decomposition of a morphism into blocks is not unique, and there may be decompositions of isomorphisms whose blocks are not necessarily isomorphisms. Here is an example that will be used later on. Example 1.2.2 The following diagram represents an isomorphism of composites of spans: a b c · · · · ·  (1.2.4) f g · · · · · a b c Indeed, it can be expressed by pasting isomorphism blocks: a b c · · · · · f b  a b g c · · · · · · · (1.2.5) c  · · · · · a b c 1.3 Strong monads We now recall the notion of strong monad [23], which is central in the T-construction. From now on the ambient category E is required to have a terminal object, hence all finite limits. Definition 1.3.1 Let (P, μ, η) be a monad on E. A strength for P is a natural transformation with components D A,B : A×PB → P(A×B), satisfying the following two axioms concern- ing tensoring with 1 and consecutive applications of D, 123 A. Cebrian D1,A 1×PA P(1×A) P p2 (1.3.1a) p2 PA A×D B,C (A×B)×PC A×(B×PC) A×P(B×C) D A×B,C D A,B×C (1.3.1.b) P((A×B)×C) P(A×(B×C)) and two axioms concerning compatibility with monad unit and multiplication, A×η B A×B A×PB D A,B (1.3.2a) η A×B P(A×B) D A,PB PD A,B A×P2 B P(A×PB) P2 (A×B) A×μ B μ A×B (1.3.2b) A×PB P(A×B) D A,B Before seeing some examples of P-operads and strong monads, we prove the following lemma, which will be useful in Section 3. Lemma 1.3.2 Let u be the unique morphism u : P1 → 1. Then the square A×Pu A×P2 1 A×P1  D A,P1 D A,1 (1.3.3) P(A×P1) P(A×1) P(A×u) is a pullback. Proof Observe that if we project the bottom rows of this square to the first component, A×Pu A×P2 1 A×P1  D A,P1 D A,1 P(A×u) P(A×P1) P(A×1) P p2 P p2 P2 1 P1 Pu then the lower square is a pullback because P is cartesian, and the outer square is a pullback because it is a projection, by (1.3.1a). Therefore the upper square is a pullback too. 123 Plethysms and operads Let us see some examples of strong monads. Example 1.3.3 Obviously the identity monad is strong. If we take the identity monad Id on any cartesian cartesian category E then a Id-operad is the same as a category internal to E, and a non colored Id-operad is a monoid in E. In particular if E = Set they are small categories and monoids, respectively. Example 1.3.4 Let (M, μ, η) be the free monoid monad on the category E=Set. As mentioned above, a M-operad is the same thing as a colored nonsymmetric set operad. Here is the full explicit description of M. Let A be a set and a0 , . . . , an ∈A, then  MA = An , n∈N η A (a0 ) = (a0 ),   μ A (a1 , . . . , ai ), . . . , (a j , . . . , an ) = (a1 , . . . , an ). (1.3.4) The free monoid monad is strong with the following strength: D A,B : A×MB M(A×B)     a, (b1 , . . . , bn ) (a, b1 ), . . . , (a, bn ) . It is straightforward to check that the diagrams (1.3.2b) and (1.3.2a) are satisfied and clear that D A,B is injective. This last feature is relevant because to define the T-construction, in Section 3, it will be necessary that D1,C0 is a monomorphism. r Example 1.3.5 The free semigroup monad M on  Set is defined in the same way as the free r r monoid monad, except that in this case M A = n≥1 An . This means that a M -operad is r a nonsymmetric operad without nullary operations. The terminal M -operad is denoted Ass, r which is of course the reduced associative operad. Notice that M is also a strong cartesian r monad on Grpd. In this sense the operad Ass can also be considered as an M -operad in Grpd, with discrete groupoid of objects and discrete groupoid of operations. The context will suffice to distinguish between Set and Grpd, but in the main applications (Section 5) we work over Grpd. Example 1.3.6 Let Y be a monoid. Denote by Y the monad on Set given by YA = Y ×A with unit and multiplication given by those of Y . Then Y is strong with strength given by the associator of the cartesian product. Therefore in this case the strength is an isomorphism. The same holds if Y is a monoid in Grpd and Y is then a monad on Grpd. Example 1.3.7 Let (S, μ, η) be the free symmetric monoidal category monad on Grpd. An S-operad is an operad internal to groupoids, so that it has a groupoid of colors and a groupoid of operations. Let A be a groupoid and Sn the symmetric group on n elements. The monad S acts on A by  SA = An //Sn , n∈N where // means homotopy quotient [1, 15]. Hence it is analogous to M, but we add an arrow σ (a1 , . . . , an ) −−→ (aσ 1 , . . . , aσ n ) 123 A. Cebrian for every element σ ∈ Sn . The multiplication and unit natural transformations are defined as in (1.3.4) for both objects and operations. Notice that any symmetric operad Q is in particular an S-operad, where the groupoid of objects Q 0 is discrete and the groupoid Q 1 has only the arrows coming from the permutations of its source sequence. In other words, a symmetric operad is an S-operad s t SQ 0 ←−− Q 1 −→ Q 0 such that Q 0 is discrete and s is a discrete fibration. The strength for S is defined the same way as for M, D A,B : A×SB S(A×B)     a, (b1 , . . . , bn ) (a, b1 ), . . . , (a, bn ) , and it is again a monomorphism, since it is injective both on objects and morphisms. Observe that symmetric operads cannot be expressed as P-operads in Set, since the actions of the symmetric groups have to be encoded necessarily as morphisms in Q 1 . Also, the only monad P one could attempt to use to define them is the free commutative monoid monad, but it is not cartesian. r Example 1.3.8 As for M and M , we can remove the empty sequence from S to get a monad r S on Grpd whose operads do not have nullary operations. We denote by Sym the terminal r S -operad, which is the reduced commutative operad. 1.4 The two-sided bar construction for P-operads The two-sided bar construction for operads is standard [32]. In this section we introduce the construction in the more general setting of P-operads by using induced monads. Any P-operad Q defines a monad (Q, μQ , ηQ ) on the slice category of E over Q 0 Q : E/Q 0 −→ E/Q 0 , f given by pullback and composition, as shown in the following diagram for an element X − → Q 0 of E/Q 0 QX  PX Q1 (1.4.1) t Pf s PQ 0 Q0. The image of f is thus the dashed composite. The multiplication μQ and the unit ηQ are defined by the following morphisms P2 f Ps Pt s t Q2 X P2 X P2 Q 0 PQ 1 PQ 0 Q1 Q0 s t  P2 f μQX P2 X P2 Q 0 PQ 1 × Q 1 Q0 (1.4.2) PQ 0 μX μQ0 m Pf QX PX PQ 0 s Q1 t Q0, 123 Plethysms and operads f X X Q0 Q0 Q0 ηQ ηX η Q0 e (1.4.3) X PQ X X PQ 0 s Q1 t Q0. Pf Definition 1.4.1 An algebra over the P-operad Q is an algebra over the monad Q. 1 Notice that the category E/Q 0 has a terminal object, Q 0 − → Q 0 , so that there is an algebra over Q given by the unique arrow q : Q1 → 1. Moreover, since E has a terminal object, the P-operad P : E/1 → E/1 itself can be represented by the span P1 ←− P1 −→ 1, and is the terminal P-operad. Now, the terminal arrow u : Q 0 → 1 induces, by postcompo- sition, a functor u ! : E/Q 0 → E/1. The diagram PQ 0 Q1 Q0 Pu u (1.4.4) P1 P1 1. φ represents a natural transformation u ! Q ⇒ Pu ! which is compatible with the comultiplica- tions and units of Q and P, meaning that φ2 μu u ! μQ φ u ! Q2 ⇒ P2 u ! ⇒! Pu ! = u ! Q2 ⇒ u ! Q ⇒ Pu ! and u! ηQ φ ηu u! ⇒ u ! Q ⇒ Pu ! = u ! ⇒! Pu ! or, equivalently, μQ μQ 0 2 0 2 P Q0 P Q0 PQ1 PQ0 Q1 Q0 P Q0 P Q0 PQ1 PQ0 Q1 Q0 Pu P2 u Pu u  Pu P1 μ P2 1 P2 1 P1 P1 1 Q2 1 = (1.4.5)  Pu P Q0 Q1 Q0 P2 1 μ1 Pu u P1 P1 1 P1 P1 1, Q0 Q0 Q0 Q0 Q0 Q0 η Q0 e u u u PQ 0 Q1 Q0 = 1 1 1 (1.4.6) Pu u η1 η1 P1 P1 1. P1 P1 1. 123 A. Cebrian Lemma 1.4.2 The natural transformation φ is cartesian. Proof Let us describe the naturality squares of φ. Let H be a map in E/Q 0 , that is, a com- mutative triangle h X Y f g Q0. Consider the diagram u ! QH PX × Q 1 PY × Q 1 Q1 PQ 0 PQ 0  s φX φY PX PY PQ 0 . Pu ! H Pg From (1.4.1) it is clear that the pullback square on the right is precisely the definition of u!Qg. From (1.4.1) and (1.4.4) we have that the square on the left is the naturality square for φ at H , and moreover that φ X and φY are projections. But Pu ! H = Ph and Pg ◦ Ph = P f , so that the composite square is precisely the definition of u!Q f , which is a pullback. As a consequence, the naturality square is a pullback too. Given a P-operad Q, we define its two-sided bar construction [24, 32, 46] BQ : 1op −→ E as the two-sided bar construction of Q, φ and the terminal algebra 1. This means that the space of n-simplicies Bn Q is given by Pu ! Qn 1, the inner face maps are given by the monad multiplication μQ , the bottom face map is given by c : Q1 → 1 and the top face maps are given by φ and μ. Similarly, the degeneracy maps are given by ηQ . Diagrams (1.4.5) and (1.4.6) and the monad axioms for P and Q guarantee that the simplicial identities are satisfied. In practice, the bar construction of Q is simply PQ 0 PQ 1 PQ 2 PQ 3 ··· , (1.4.7) where (i) Q 2 := PQ 1 × Q 1 and Q 3 := P2 Q 1 × PQ 1 × Q 1 , etc.; PQ 0 P2 Q 0 PQ 0 (ii) the bottom face maps d0 are induced by t; (iii) the top face maps dn are induced by s and μ; (iv) the inner face maps are induced by m and μ, and (v) the degeneracy maps are induced by e and η. Henceforth we may indiscriminately use this simplicial notation. Let us see some examples. 123 Plethysms and operads Example 1.4.3 Let C be a small category. Hence C is a Id-operad in Set. Then BC is the nerve of C. Moreover, we can consider C as a category internal to Grpd whose groupoid of objects has as morphisms the isomorphisms of C, and whose groupoid of arrows has as morphisms the isomorphisms of the arrow category of C. In this case BC is the fat nerve of C, whose groupoid of n-simplices is the groupoid Map([n], C). In the theory of incidence coalgebras, this is often more interesting than the ordinary nerve, cf. [9, 17, 18] Example 1.4.4 If Q is a symmetric operad, as in Example 1.3.7, then BQ is the usual operadic two-sided bar construction. Its n-simplices have as objects forests of n-level Q-trees, and as morphisms permutations at each level. For example, the following picture x1 x1 x1 x1 x2 x3 x3 y1 y1 y2 y1 is an object of PQ 2 with (2! · 2!2 · 3!4 ) · (2!) · (2! · 2!2 ) automorphisms. The following result is a reformulation of [46, Proposition 4.4.1] and [24, Proposition 3.3] in the context of P-operads. Proposition 1.4.5 The simplicial object BQ is a strict category object. Proof We have to check that the squares d0 Bn+2 Q Bn+1 Q dn+2 dn+1 (1.4.8) Bn+1 Q Bn Q. d0 are pullbacks for n ≥ 0. We show the case n = 0, the rest are similar. The square is given by Pu ! Qc Pu ! QQ1 Pu ! Q1 P(φQ1 ) P(φ1 ) PPu ! c (1.4.9) PPu ! Q1 PPu ! 1 μPu!Q1 μPu!1 Pu ! Q1 Pu ! 1. Pu ! c The bottom square is cartesian because it is a naturality square for μP , and P is a cartesian monad. The top square is P applied to a naturality square of φ, which is cartesian, by Lemma 1.4.2. Since P preserves pullbacks, the square is cartesian. This allows to obtain the following result, in the special case where E = Grpd. 123 A. Cebrian Proposition 1.4.6 Let P : Grpd → Grpd be a cartesian monad that preserves fibrations. Let Q be a P-operad such that Q 0 is a discrete groupoid. Then the simplicial groupoid BQ is a Segal groupoid. Proof It is enough to see that the strict pullbacks 1.4.8 are also homotopy pullbacks. For Pu ! c Pm n = 0, notice that Pu ! Q1 −−→ Pu ! 1 is precisely the map PQ 1 −→ PQ 0 . But since Q 0 is discrete m is a fibration, which means that Pm is a fibration, because P preserves fibrations. This implies that the square is also a homotopy pullback. Moreover, since pullbacks preserve Pu ! Qc fibrations the map Pu ! QQ1 −−−→ Pu ! Q1 is again a fibration. The same argument then implies that the square for n = 1 is also a homotopy pullback, and so on. Suppose now that R : E → E is another cartesian monad and that there is a cartesian ψ monad map P ⇒ R. Then we can take the bar construction over R BR Q : 1op −→ E whose n-simplices are given by Ru ! Qn 1 (or RQ n ). In this case all the face maps coincide with the previous ones except the top face map, which is given by R(φ Q1 ) R(ψu ! Qn 1 ) μRu Qn 1 ! Ru ! Qn+1 1 −−−−→ RPu ! Qn 1 −−−−−→ RRu ! Qn 1 −−−−→ Ru ! Qn 1. Since ψ is cartesian the simplicial object BR is also a strict category object. Moreover, if R preserves fibrations, it is a Segal groupoid, for the same reason as BQ in Proposition 1.4.6. The main examples of this bar construction that we use come from the natural transformations r r r M ⇒ S, S ⇒ S and M ⇒ M, as in [24]. 2 Segal groupoids and incidence coalgebras Throughout this section, pullbacks and fibers of groupoids refer to homotopy pullbacks and homotopy fibers. A brief introduction to the homotopy approach to groupoids in combina- torics can be found in [15, §3]. 2.1 Segal groupoids A simplicial groupoid X : 1op −→ Grpd is a Segal space [17, §2.9, Lemma 2.10] if the following square is a pullback for all n > 0: d0 X n+1 Xn  (2.1.1) dn+1 dn Xn X n−1 . d0 Segal spaces arise prominently through the fat nerve construction: the fat nerve of a category C is the simplicial groupoid X = N C with X n = Fun([n], C) , the groupoid of functors [n] → C. In this case the pullbacks above are strict, so that all the simplices are strictly 123 Plethysms and operads determined by X 0 and X 1 , respectively the objects and arrows of C, and the inner face maps are given by composition of arrows in C. In the general case, X n is determined from X 0 and X 1 only up to equivalence, but one may still think of it as a “category” object whose composition is defined only up to equivalence. Remark 2.1.1 Despite the Segal conditions (2.1.1) require the squares to be homotopy pull- backs, if the top or bottom face maps are fibrations, the ordinary pullbacks are also homotopy pullbacks. In the present work, homotopy pullbacks mostly arise in this way. 2.2 Incidence coalgebras Let X be a simplicial groupoid. The spans d1 (d2 ,d0 ) s0 t X 1 ←−− X 2 −−−−→ X 1 × X 1 , X 1 ←−− X 0 − → 1, define two functors  : Grpd/X 1 −→ Grpd/X 1 ×X 1 : Grpd/X 1 −→ Grpd s s S−→ X 1  −→ (d2 , d0 )! ◦ d1∗ (s), S−→ X 1  −→ t! ◦ s0∗ (s). Recall that upperstar is homotopy pullback and lowershriek is postcomposition. This is the general way in which spans interpret homotopy linear algebra [16]. Segal spaces are a particular case of decomposition spaces [17, Proposition 3.7], simplicial groupoids with the property that the functor  is coassociative with the functor as counit (up to homotopy). In this case  and endow Grpd/X 1 with a coalgebra structure [17, §5] called the incidence coalgebra of X . Note that in the special case where X is the nerve of a poset, this construction becomes the classical incidence coalgebra [39, 40] construction after taking cardinality, as we shall do shortly. The morphisms of decomposition spaces that induce coalgebra homomorphisms are the so- called CULF functors [17, §4], standing for conservative and unique-lifting-of-factorisations. A Segal space X is CULF monoidal if it is a monoid object in the monoidal category (DcmpCULF , ×, 1) of decomposition spaces and CULF functors [17, §9]. More concretely, it is CULF monoidal if there is a product X n × X n → X n for each n, compatible with the degeneracy and face maps, and such that for all n the squares g×g X n ×X n X 1 ×X 1  (2.2.1) Xn g X1 are pullbacks [17, §4]. Here g is induced by the unique endpoint-preserving map [1] → [n]. For example the fat nerve of a monoidal extensive category is a CULF monoidal Segal space. Recall that a category C is monoidal extensive if it is monoidal (C, +, 0) and the natural functors C/A × C/B → C/A+B and C/0 → 1 are equivalences. If X is CULF monoidal then the resulting coalgebra is in fact a bialgebra [17, §9], with product given by ∼ +!  : Grpd/X 1 ⊗ Grpd/X 1 −→ Grpd/X 1 ×X 1 −−→ Grpd/X 1 (G → X 1 ) ⊗ (H → X 1 )  −→ G × H → X 1 × X 1  −→ G × H → X 1 . Briefly, a product in X n compatible with the simplicial structure endows X with a product, but in order to be compatible with the coproduct it has to satisfy the diagram (2.2.1) (i.e. it has to be a CULF functor). 123 A. Cebrian 2.3 Homotopy cardinality A groupoid X is finite if π0 (X ) is a finite set and π1 (x) = Aut(x) is a finite group for every point x. If only the latter is satisfied then it is called locally finite. A morphism of groupoids is called finite when all its fibers are finite. The homotopy cardinality [1], [16, §3] of a finite goupoid X is defined as  1 |X | := ∈ Q, | Aut(x)| x∈π0 X p and the homotopy cardinality of a finite map of groupoids A − → B is  |Ab | | p| := δb , | Aut(b)| b∈π0 B in Qπ0 B , the vector space spanned by π0 B. In this sum, Ab is the homotopy fiber and δb is a formal symbol representing the isomorphism class of b. A simple computation shows that b |1 −−→ B| = δb . A Segal space X is locally finite [18, §7] if X 1 is a locally finite groupoid and both s0 : X 0 → X 1 and d1 : X 2 → X 1 are finite maps. In this case one can take homotopy cardinality to get a comultiplication  : Qπ0 X 1 −→ Qπ0 X 1 ⊗ Qπ0 X 1 s → X 1 |  −→ |(d2 , d0 )! ◦ d1∗ (s)| |S − and similarly for (cf. [18, §7]). Moreover, if X is CULF monoidal then Qπ0 X 1 acquires a bialgebra structure with the product · = |  |. In particular, if we denote by + the monoidal a b product in X , then δa · δb = δa+b for any |1 −−→ X 1 | and |1 −−→ X 1 |. The following result gives a closed formula for the computation of the comultiplication when X is a Segal space. Lemma 2.3.1 ([9, 19]) Let X be a Segal space. Then for f in X 1 we have   | Iso(d0 a, d1 b) f | (δ f ) = δa ⊗ δb , | Aut(b)|| Aut(a)| b∈π0 X 1 a∈π0 X 1 where Iso(d0 a, d1 b) is the set of morphisms from d0 a to d1 b and Iso(d0 a, d1 b) f is its homo- topy fiber along d1 . 3 The T-construction Throughout this section (P, μ, η) is a cartesian strong monad on a cartesian category E, and category means a category internal to E. As mentioned in the introduction, the T-construction consists of two constructions, one from internal categories to P-operads and another from P-operads to categories. With the purpose of reducing the diagrams and fiber products, we use the following notation for the endofunctors and natural transformations featuring in this 123 Plethysms and operads section, L:E E F : Id L id×η1 A A×P1, FA : A×1 LA, D:L P R:L Id p1 D A : A×P1 PA, R A : A×P1 A. Observe that L is cartesian as a functor. Also, notice that R and F are cartesian natural transformations. Finally, by monomorphism we refer to the 1-categorical notion. In the case of most interest where E is Set or Grpd, this means injective on objects and injective on arrows. The material of this section is highly technical. The casual or application-oriented reader might wish to regard it as a black box and take on faith the well-definedness of the construc- tions, and still be able to appreciate the examples worked out in Chapters 4 and 5. 3.1 From categories to P-operads Let C be a category such that DC0 : P1×C0 → PC0 is a monomorphism. It is convenient in this section to adopt a simplicial nomenclature. Hence C is represented by the span d1 C1 C1 ×C0 C1 =:C2 C1 d1 d0 e C0 C0 C0 C1 , with the only inconvenience that some of the face maps share their names. Notice that we still denote by e the degeneracy map s0 . We now construct a P-operad TP C from the category C. To keep notation short, the simplicial nomenclature for TP C is Ci for the simplices and di for the face maps. The span defining the objects and operations of TP C is given by the pullback C1 i1 d1 d0  PC1 LC0 (3.1.1) Pd0 DC0 Pd1 RC 0 PC0 PC0 C0 . Observe that C0 = C0 , so that TP C has the same objects as C. Besides, the morphism i 1 is a monomorphism, since monomorphisms are preserved by pullbacks and DC0 is a monomorphism. d1 To define composition we need to specify a map C2 − → C1 , where C2 := PC1 ×C1 , PC0 satisfying the axioms of “Appendix A.1”. However, to describe it we have to express C2 in a way we can naturally use composition d1 in the original category C2 − → C1 . The following diagram represents an isomorphism C2 ∼ = P2 C1 × PLC1 × (C0 ×P2 1)=:C2 , P2 C 0 PLC0 123 A. Cebrian P2 d1 P2 d0 PLd0 DP1,C0 p1 P2 C0 P2 C 1 P2 C 0 PLC1 PLC0 C0 ×P2 1 C0 .   PLd1 PRC1 PRC0 (B) id×Pu (A) P2 C0 P2 C 1 P2 C 0 PLC0 PC0 PC1 PC0 LC0 C0 P2 d1 P2 d0 PDC0 PRC0 Pd1 Pd0 DC0 RC 0 (3.1.2) It is clear that all the squares in (3.1.2) commute. Moreover, the square (A) is cartesian because R and P are cartesian, and the square (B) is the same as (1.3.3) of Lemma 1.3.2. d1 Definition 3.1.1 The composition of TP C is given by the following arrow C2 − → C1 , P2 d1 Pd0 PLd0 DP1,C p1 C2 P2 C0 P2 C1 P2 C0 PLC1 PLC0 0 C0 ×P2 1 C0 PDC (A) PDC (B) 1 0 P2 d1 P2 d0 P2 d1 p1 P2 C0 P2 C1 P2 C0 P2 C1 P2 C0 C0 ×P2 1 C0 P2 d0 2 DC 0 P2 d2 P2 d0  d1 (C) P2 C2 (D) P2 d1 (G) id×μ1 P2 d1 P2 d0 P2 C0 P2 C1 P2 C0 μC (E) μC (F) μC 0 1 0 Pd1 d0 DC RC C1 PC0 PC1 PC0 0 LC0 0 C0 . (3.1.3) It is clear that the diagram commutes: (A) is P applied to a naturality square of D; (B) is the definition of D 2 ; (C) and (D) are P2 applied to axioms (A.1.1a) and (A.1.1b) for composition in C; (E) and (F) are naturality squares of μ, and (G) is again axiom (1.3.2b) for strong monads. The remaining squares are trivial. Notice that from this definition it is clear that d1 satisfies axioms (A.2.1a) and (A.2.1b). Furthermore, there is a map i 2 C2 P2 C 2 , given by the diagram P2 d1 Pd0 PLd0 DP1,C 0 P2 C0 P2 C1 P2 C0 PLC1 PLC0 C0 ×P2 1 C0 PDC PDC 1 0 P2 d1 P2 C0 P2 C1 P2 C0 P2 C 1 P2 C 0 , P2 d0 P2 d1 P2 d0 123 Plethysms and operads which clearly makes the square i 2 C2 i2 P2 C 2 C2 P2 C 2 P2 d1 P2 d1 and therefore d1 P2 C 1 d1 P2 C 1 (3.1.4) also the square μC1 μC1 C1 PC1 , C1 PC1 , i1 i1 commute, for the corresponding arrow i 2 . This says, roughly speaking, that composition in TP C is “the same” as composition in P2 C, as it is also clear in most of the examples. We have to check that composition is associative (A.2.3). We state first the following lemma. We omit its proof since it is long and unenlightening; it can be found in [10]. i3 Lemma 3.1.2 There is a map C3 −−→ P3 C3 such that the following diagrams commute i3 i3 C3 P3 C3 C3 P3 C3 P3 d1 P 3 d2 d1 P3 C2 d2 P3 C2 (3.1.5) PμC2 μPC2 C2 P C2 , 2 C2 P2 C2 . i2 i2 Proposition 3.1.3 Composition is associative. Proof In view of Lemma 3.1.2 there is a diagram d1 C3 C2 i3 i2 P3 d1 PμC2 P3 C3 P3 C2 P2 C 2 P3 d2 (A) P3 d1 (B) P2 d1 P3 d1 PμC1 d2 P3 C2 P3 C1 P2 C 1 d1 μPC2 (C) μPC1 (D) μC1 P2 d1 μC1 2 2 P C2 P C1 PC1 i2 i1 d1 C2 C1 , where the four trapeziums are diagrams (3.1.4) and (3.1.5) of Lemma 3.1.2. The inner squares are the following: (A) is P3 applied to associativity of C; (B) is P applied to naturality of μ at d1 ; (C) is naturality of μ at Pd1 and (D) is the associativity law of μ. Since i 1 is a monomorphism (3.1.1) and all the inner diagrams commute, so does the outer square, as we wanted to see. The unit morphism of TP C is easier to obtain than composition. Recall that the unit is a morphism e : C0 → C1 such that the following diagram (1) commutes, 123 A. Cebrian C0 ηC0 id e PC0 C1 C0 . d1 d0 Definition 3.1.4 The unit of TP C is given by the following arrow: C0 PC0 ηC0 C0 C0 C0 C0 ηC0 e (A) PC0 (B) ηC0 (C) FC0 (D) (3.1.6) Pe C1 PC0 PC1 PC0 LC0 C0 . Pd1 Pd0 DC0 RC 0 It is clear that all the diagrams commute: (A) and (B) come from P applied to (A.1.2a) and (A.1.2b), this is d1 ◦ e = id = d0 ◦ e; (C) is the compatibility between D and η (1.3.2a), and (D) is obvious from the definitions of R and F. We have to verify now that composition with the unit morphism is the identity (1). To prove it we follow the same strategy as for associativity. That is, we project the diagrams into diagrams in the original category C containing the corresponding unit axioms. Again, the proof of the following lemma can be found in [10]. Recall first that C2 := C1 ×C0 C1 and C2 := PC1 ×C1 . PC0 Lemma 3.1.5 We have commutative squares i 1l i 1r PC0 ×C1 PC0 ×PC1 C1×C0 PC1 ×PC0 PC0 PC0 C0 PC0 Pe×id id id×id Pe (3.1.7a) ηC ×ηC e (3.1.7b) Pe×id id PC2 1 0 PC2 PηC2 ηPC2 C2 P C2 , 2 C2 P2 C2 , i2 i2 where i 1l and i 1r are the morphisms corresponding to i 1 . Proposition 3.1.6 The unit morphism e of TP C satisfies the left and right composition axioms (1). 123 Plethysms and operads Proof For the left composition (A.2.4a), the required commutative triangle is the outline of the diagram Pe×id id PC0 × C1 C2 PC0 i 1r i2 (B) Pe×id id PηC PC0 × PC1 PC2 2 P2 C 2 PC0 (C)id (E) μC P2 d1 2 (A) p2 PC2 P2 C 1 (D) Pd1 μC (F) PC1 1 d1 i1 C1 (3.1.8) We have that Diagram (A) commutes by definition of i 1l ; (B) is precisely (3.1.7a) of Lemma 3.1.5; (C) is P applied to the left composition with the unit axiom in the category C (A.1.4a); (D) is naturality of μ at d1 ; (E) is P of the unit axiom of P applied to C2 , and (F) is the same as (3.1.4). Since i 1 is a monomorphism and all the inner diagrams commute so does the outer triangle, as we wanted to see. For the right composition (A.2.4b), the required commutative triangle is the outline of the diagram ηC ×ηC e 1 0 C1 × C0 C2 C0 i 1l (B) i2 id×id Pe ηPC PC1 × PC0 PC2 2 P2 C2 PC0 (C)id (E) μC P2 d1 2 (A) PC2 P2 C1 (D) Pd1 μC (F) PC1 1 i1 d1 C1 (3.1.9) We have that Diagram (A) commutes by definition of i 1r , (B) is precisely (3.1.7a) of Lemma 3.1.5, (C) is P applied to the right composition with the unit axiom in the category C (A.1.4b); (D) is again naturality of μ at d1 , (E) is the unit axiom of P applied to PC2 and (F) is the same as (3.1.4), as before. Since i 1 is a monomorphism and all the inner diagrams commute so does the outer triangle, as we wanted to see. The last thing to check is that the construction is functorial. First of all we have to specify f how the construction acts on morphisms. Let C and C  be two categories and C − → Ba functor, that is a diagram d1 d0 C0 C1 C0 f0 f1 f0 d1 d0 B0 B1 B0 123 A. Cebrian satisfying the commutative squares of 1.1.1. Then TP f is the morphism given by Pd1 Pd0 DC0 RC 0 TP C PC0 PC1 PC0 LC0 C0 TP f P f0 P f1 P f0 L f0 f0 Pd1 Pd0 D B0 R B0 TP B PB0 PB1 PB0 LB0 B0 . It is a bit tedious but not difficult to see that f satisfies again the commutative squares of 1.1.1 g [10]. Moreover, given another morphism B − → A it is clear that TP (g ◦ f ) = TP g ◦ TP f , just because of the functoriality of P and L. Since the construction is functorial, if the strength D A is a monomorphism for every object A ∈ E then TP is in fact a functor from P-operads to categories internal to E. 3.2 From P-operads to categories This construction has a similar structure as the construction above, so we follow the same steps. Let Q be a P-operad, d1 Q1 PQ 1 × Q 1 := Q 2 Q1 PQ 0 d1 d0 PQ 0 Q0 Q0 e Q1, and assume that D Q 0 : P1×Q → PQ is a monomorphism. We construct a category TP Q from the P-operad Q. In this case, the simplicial nomenclature for TP Q is Q i for the simplices and d i for the face maps. The following pullback defines the objects and arrows of TP Q: C1 j1 d1 d0  LC0 C1 (3.2.1) DC0 d1 RC 0 d0 C0 PC0 C0 . Observe that Q 0 = Q 0 , so that again TP Q has the same objects as Q. Besides, the morphism j1 is a monomorphism, since monomorphisms are preserved by pullbacks and D Q 0 is a monomorphism. d1 To define composition we need to define a map Q 2 −→ Q 1 , where Q 2 := Q 1 × Q 0 Q 1 , satisfying the axioms of “Appendix 1”. However, to specify this map we need to express it in d1 a way we can naturally use composition in the original P-operad Q 2 − → Q 1 . The following diagram represents an isomorphism  Q2 ∼ = L2 Q 0 × LQ 1 × Q 1 =:Q 2 , PLQ 0 PQ 0 123 Plethysms and operads LD Q Ld1 d1 d0 Q0 L2 Q 0 0 LPQ 0 LQ 1 PQ 0 Q1 Q0 .   RQ Ld0 RLQ (A) RPQ 0 1 0 (B) Q0 LQ 0 PQ 0 Q1 Q0 LQ 0 PQ 0 Q1 Q0 RQ DQ d1 d0 RQ DQ d1 d0 0 0 0 0 (3.2.2) It is clear that all the squares in (3.2.2) commute. Moreover, the squares (A) and (B) are cartesian because so is R.   d1 Definition 3.2.1 The composition of Q is given by the following arrow Q 2 −→ Q 1 , LD Q Ld1 d1 d0  0 Q2 Q0 L2 Q 0 LP Q 0 L Q1 PQ0 Q1 Q0 id×DP1 (A)DPQ (B) D Q 1 0 Pd0 d1 Q 0 ×P 2 1 P2 Q 0 P Q1 PQ0 Q1 Q0 D 2Q Pd1 d0 0 d2 d0  id×μ1 (C) μQ (D) Q2 (E) 0 d1 Q1 Q0 PQ0 PQ0 Q1 PQ0 . RQ DQ d1 d0 0 0 (3.2.3) Let us see that all the diagrams commute: (A) is a combination of natuarlity of D applied to D Q 0 and axiom (1.3.1.b) concerning consecutive applications of the strength, (B) is naturality of D at d1 , (C) is axiom (1.3.2b) for strong monads and (D) and (E) are respectively axioms (A.2.1a) and (A.2.1b) for composition in Q. The remaining diagrams are clear. Notice that from this definition it is clear that d 1 satisfies axioms (A.1.1a) and (A.1.1b). Furthermore, there is a morphism  j2 Q2 Q2, given by the diagram LD Q 0 Ld1 d1 d0 Q0 L2 Q 0 LPQ 0 LQ 1 PQ 0 Q1 Q0 DPQ 0 D Q1 Pd0 d1 P2 Q 0 PQ 1 PQ 0 Q1 Q0, Pd1 d0 which clearly makes the square  j2 j2 Q2 Q2 Q2 Q2 and therefore d1  d1 d1 d1 (3.2.4) also the square Q1 Q1, Q1 Q1, j1 j1 123 A. Cebrian commute, for the corresponding j2 . This says, roughly speaking, that composition in Q is “the same” as composition in Q, as is also clear in most of the examples. We have to check that composition is associative (A.1.3). As in the previous subsection, the proof of the following lemma is omitted; it can be read in [10]. j3 Lemma 3.2.2 There is a morphism Q 3 −−→ Q 3 such that the following diagrams commute j3 j3 Q3 Q3 Q3 Q3 d1 d1 d 2 d2 (3.2.5) Q2 Q2, Q2 Q2. j2 j2 Proposition 3.2.3 Composition is associative. Proof In view of Lemma 3.2.2 there is a diagram d2 C3 C2 j3 d2 j2 C3 C2 d1 d1 d1 d1 C2 C1 d1 j2 j1 C2 C 1. d1 The four trapeziums are the commutative diagrams (3.2.4) and (3.2.5) of Lemma 3.2.2 respectively, and the inner square is associativity of composition in C (A.2.3). Since j1 is a monomorphism and all the inner diagrams commute, so does the outer square, as we wanted to see. The unit morphism of the new category is easier to obtain than composition. Recall that the unit is a morphism e : Q 0 → Q 1 such that this diagram (1) commutes Q0 id e id Q0 Q1 Q0. d1 d0 Definition 3.2.4 The unit of Q is given by the following arrow: Q0 Q0 Q0 Q0 Q0 id (A) FQ 0 (B) η Q 0 (C) e (D) id (3.2.6) Q0 LQ 0 PQ 0 Q1 Q0. R Q0 D Q0 d1 d0 It is clear that all the diagrams commute: (A) is obvious from the definitions of R and F, (B) is axiom (1.3.2a) for strong monads, and (C) and (D) are respectively the unit axioms (A.2.2b) and (A.2.2a) of Q. 123 Plethysms and operads We have to check that composition with the unit morphism is the identity (1). To prove it we follow the same strategy as for associativity. That is, we project the diagrams into diagrams in the original P-operad Q containing the corresponding unit axioms. The proof of the following lemma can be found in [10]. Recall first that Q 2 := PQ 1 × Q 1 and Q 2 := Q 1 × Q 0 Q 1 . PQ 0 Lemma 3.2.5 We have commutative squares j1l Q0× Q1 PQ 0 × Q 1 j1r Q0 PQ 0 Q1× Q0 Q1× Q0 Q0 Q0 (3.2.7a) (3.2.7b) e×id id Pe×id id id×id e η Q 1 ×η Q e 0 Q2 Q2, Q2 Q2, j2 j2 where j1l and j1r are the morphisms corresponding to j1 . Proposition 3.2.6 The unit morphism e of Q satisfies the left and right composition axioms (1). Proof For the left composition (A.1.4a), the required commutative triangle is the outline of the diagram e×id id Q0 × Q1 Q2 Q0 j1l (B) j2 Pe×id id PQ 0 × Q 1 PQ 1 × Q 1 PQ 0 PQ 0 (C) d1 Q1 (A) (D) j1 d1 Q1 , (3.2.8) We have that Diagram (A) commutes by definition of j1l , (B) is precisely (3.2.7a) of Lemma 3.2.5, (C) is the left composition with unit axiom in the P-operad C (A.2.4a) and (D) is the same as (3.2.4). Since j1 is a monomorphism and all the inner diagrams commute, so does the outer triangle, as we wanted to see. For the right composition (A.1.4b), the required commutative triangle is the outline of the diagram id×id e Q1 × Q0 Q2 Q0 j1r (B) η Q ×η Q e j2 1 0 Q1 × Q0 PQ 1 × Q 1 Q0 PQ 0 (C) d1 Q1 (A) (D) j1 d1 Q1 , (3.2.9) We have that Diagram (A) commutes by definition of j1r , (B) is precisely (3.2.7b) of Lemma 3.2.5, (C) is the right composition with unit axiom in the P-operad Q (A.2.4b), and (D) is the same as (3.2.4), as before. Since j1 is a monomorphism and all the inner diagrams commute so does the outer triangle, as we wanted to see. 123 A. Cebrian The last thing to check is that the construction is functorial. First of all we have to specify f how the construction acts on morphisms. Let Q and Q  be two P-operads and Q − → Ba morphism, that is a diagram d1 d0 PQ 0 Q1 Q0 P f0 f1 f0 d1 d0 PB0 B1 B0 satisfying the commutative squares of 1.1.1. Then TP f is the functor given by TP Q Q0 LQ 0 PQ 0 Q1 Q0 R Q0 D Q0 d1 d0 TP f f0 L f0 P f0 P f1 f0 TP B B0 LB0 PB0 B1 B0 . R B0 D B0 d1 d0 It is a bit tedious but not difficult to see that TP f satisfies again the commutative squares of g 1.1.1 [10]. Moreover, given another morphism B − → A it is clear that TP (g ◦ f ) = TP g ◦TP f , just because of the functoriality of P and L. Since the construction is functorial, if the strength D A is a monomorphism for every object A ∈ E then TP is in fact a functor from P-operads to categories internal to E. 3.3 The composite construction Since we have defined a construction from P-operads to categories and a construction from categories to P-operads, we obtain a composite construction from P -operads to P-operads, for P and P not necessarily the same monad. In particular, since a category is the same as an Id-operad, the composite construction for P = Id is the same as the functor from categories to P-operads. From now on we call T-construction any of the three constructions, the context will suffice to distinguish, but we are mainly interested in landing on a P-operad, rather than a category. To keep notation short, we denote by  TP Q := TP TP Q the composite construction that produces a P-operad from the P -operad Q. The monad P will be always clear from the context. 3.4 Finiteness conditions In Section 5 we will be interested in computing the incidence bialgebra of the bar construction of several P-operads in E = Grpd. Recall that to be able to take the homotopy cardinality, the bar construction has to be locally finite as a simplicial groupoid (in the sense of [18]). We now define the notion of locally finite operad (in the sense of ( [24]) in the setting of P-operads, which is the sufficient condition for its bar construction to be locally finite, and we give sufficient conditions on the T-construction to preserve locally finiteness. Definition 3.4.1 A natural transformation is finite if all its components are finite. A monad (P, μ, η) on Grpd is locally finite if μ and η are finite natural transformations. A P-operad Q is locally finite if Q 1 is locally finite, and the maps d1 and e are finite. 123 Plethysms and operads In the special case of P = Id, P-operads are just categories, and the notion of locally finite agrees with the standard notion. Notice that Q can be locally finite even if P is not. The condition of P being locally finite appears in the T-construction. Example 3.4.2 For a classical symmetric or nonsymmetric operad, the locally finiteness con- dition amounts to saying that every operation can be expressed as a composition of operations in a finite number of ways. For instance, the operads Ass and Sym are locally finite. For this it is important that nullary operations are excluded. The non-reduced versions, where there is a nullary operation, are not locally finite. The bar construction of Q is locally finite if Q is locally finite and P preserves locally finite groupoids and finite maps (see Section 1). Also, given another locally finite monad R on E that preserves locally finite groupoids and finite maps, if there is a cartesian monad map ψ P ⇒ R with ψ finite then the bar construction BR is also locally finite. Let us see that the T-construction interacts well with finiteness, as long as some simple conditions are satisfied. Lemma 3.4.3 Let P : Grpd → Grpd be a locally finite strong monad that preserves locally finite groupoids, finite maps and fibrations. Assume moreover that the strength D is finite. Consider a locally finite category C in Grpd such that C0 is discrete and DC0 is a monomor- phism. Then the P-operad TP C is locally finite. Proof Recall from Diagram (3.1.1) that C1 is defined as the pullback C1 LC0  DC0 PC1 PC0 . Pd0 Notice that the pullback and the monomorphism refer to the 1-categorical notions, while the finite map condition is a homotopy notion. Let us see first that C1 is locally finite. Since C1 is locally finite and P preserves locally finite groupoids, PC1 is locally finite. Now, an automorphism in C1 is a pair of automorphisms ( f , g) ∈ PC1 ×LC0 coinciding at PC0 , but there is only a finite number of f ’s, since PC1 is locally finite, and for each f at most one g, since DC0 is a monomorphism. We have to prove also that d1 and e are finite maps. This follows from their definitions, 3.1.1 and 3.1.4: since C0 is discrete, we have that d0 is a fibration, and because P (and also L) preserves fibrations, all the right arrows in diagrams (3.1.3) and (3.1.6) are fibrations. As a consequence their limit is equivalent to their homotopy limit. Finally, notice that all the vertical maps involved in these two diagrams are finite. This implies that their homotopy limit, and hence their limit, is also finite. Lemma 3.4.4 Let P : Grpd → Grpd be a locally finite strong monad that preserves locally finite groupoids, finite maps and fibrations. Assume moreover that the strength D is finite. Consider a locally finite P-operad Q such that Q 0 is discrete and D Q 0 is a monomorphism. Then the P-operad TP C is locally finite. Proof The proof is analogous to the proof of Lemma 3.4.3. In particular these results imply of course that if P and P are monads satisfying the conditions of Lemmas 3.4.3 and 3.4.4 and Q is a locally finite P -operad then TP Q is locally finite. 123 A. Cebrian r Remark 3.4.5 In the sequel, we deal with the free semigroup monad M and the free symmetric r semimonoidal category monad S , which preserve locally finite groupoids, finite maps and fibrations, as required by Lemmas 3.4.3 and 3.4.4. Moreover, their strength is finite, as can be easily seen from its definition (see Examples 1.3.4 and 1.3.7). Also, we use the reduced operads Ass and Sym, as well as their colored versions. They are all locally finite and have discrete groupoid of colors. r r 4 T-construction for M and S -operads In this section we unravel the T-construction with some of the main examples. We begin r r discussing the construction from categories to M -operads and S -operads. When the category is just a monoid we get the Giraudo T -construction, which we recall next. Lastly we treat symmetric and nonsymmetric operads. The choice of working with the reduced version of the operads (excluding nullary opera- tions), is irrelevant for the sake of the T-construction itself, which is abstract enough to work with any operad. The reason for preferring the reduced version is to stay within the realm of locally finite operads, as mentioned in Example 3.4.2 and Remark 3.4.5. Moreover, it is also r r r easy to see that the cartesian monad maps M ⇒ S, S ⇒ S and M ⇒ M are finite. 4.1 The T-construction for categories Let C be a category internal to Set, represented by the span C0 ← C1 → C0 , and take the r free semigroup monad M . The set of objects of T r C is again C0 , while C1 is given by M C1 d1 d0  r (4.1.1) M C1 LC0 Pd0 DC0 Pd1 RC 0 r r M C0 M C0 C0 . Recall from Example 1.3.7 that the strength is given by r DC0 : LC0 M C0 (4.1.2)     c, (1, . . . , 1) (c, 1), . . . , (c, 1) . Therefore, the pullback condition means that the elements in C1 that have input c1 , . . . , cn and output c are the sequences of n arrows in C whose sources are c1 , . . . , cn and whose targets are all c. Hence  n C1 = Hom(ci , c). (c1 ,...,cn ;c) i=1 123 Plethysms and operads Substitution in T r C, M k k ni ◦: Hom(ci , c) × Hom(d ij , ci ) −→ Hom(d ij , c), i=1 i=1 j=1 1≤i≤k 1≤ j≤n i k goes as follows: for an operation x ∈ i=1 Hom(ci , c) and a sequence of k operations ni y ∈ j=1 Hom(d j , ci ), with i = 1, . . . , k, i i x ◦ (y 1 , . . . , y k ) = (x1 ◦ y11 , . . . , x1 ◦ yn11 , . . . , xk ◦ y1k , . . . , xk ◦ ynkk ) ∈ Hom(d ij , c). 1≤i≤k 1≤ j≤n i Note that now the composition inside the parenthesis is composition of morphisms of C, r while the composition on the left-hand side of the equation is composition in M C. It is not difficult to see that the composition we get from 3.1.1 agrees with the one defined above: both r r use the fact that C2 is a subset of (M )2 C together with (M )2 ◦ and the monad multiplication. The identity elements of this operad are given by the identity morphisms of C. If the category C has coproducts (+) then n Hom(ci , c) = Hom(c1 + · · · + cn , c), i=1 so that the operations of T r C are in fact arrows of C. M Since C can be considered as a category internal to Grpd, we can also compute T r C to get S a symmetric operad. It is clear that T r C1 = T r C1 //S, where the action of the symmetric M M group Sn is given by permutation of tuples, that is n n Sn × i=1 Hom(ci , c) −→ i=1 Hom(cσ (i) ; c) (σ, (x1 , . . . , xn ))  −→ (xσ (1) , . . . , xσ (n) ). It is useful to picture elements (c1 , . . . , cn ; c) as (picturing n = 3) c3 c2 c1 c Under this representation, composition in T r C (or T r C) looks like S M c32 c31 c21 c13 c12 c11 c32 c31 c21 c13 c12 c11 c3 c2 c1 = c c Example 4.1.1 Take C = { 0 1 } . For any pair of objects of C there is exactly one morphism between them. Hence T r C has one operation for each given sequence of inputs M and output, so that it is the 2-colored associative operad Ass2 . In the same way T r C is the S 2-colored symmetric operad Sym2 . In fact it is straightforward to see that the T-constructions of the discrete connected groupoid of n elements are Assn and Symn . 123 A. Cebrian Example 4.1.2 Consider the category C = {0 −→ 1}. Note that in this case there is either one or no morphism between two objects of C. Thus clearly (c → c1 , . . . , c → cn ) if c = 0 or c = c1 = · · · = cn = 1 T r C(c1 , . . . , cn ; c) = S ∅ otherwise. Of course this operad is a suboperad of the previous one, since this category is a subcategory of the previous one. In particular composition is obvious. Example 4.1.3 We now specialize to the case of categories with only one object, that is monoids, recovering the T -construction of Giraudo. This construction was introduced by Giraudo [20] as a generic method to build combinatorial operads from monoids. Since a monoid is just a category with one object, it is represented by the span 1 ← Y → 1, D1 r and because the morphism L1 −→ M 1 is an isomorphism, we have that T r Y is given by M r MY  r r MY r L1 M s M t D1 r r M1 M1 1. It is easy to see that this gives the same operad T Y defined in the introduction, since T Y is r r precisely M Y , and both compositions are defined by using composition in (M )2 Y and the monad multiplitcation. Example 4.1.4 If Y1 is the singleton monoid, then T r Y1 = Ass, the associative operad, and M T r Y1 = Sym, the commutative operad. S 4.2 The T-construction for operads r We now unravel the full T-construction from nonsymmetric operads to S -operads. As we r r already know, the first ones are the same as M -operads in Set, but we view them as M - operads in Grpd with discrete groupoids of objects and arrows. At the end we will comment r on other variations similar to this case, such as from symmetric operads to S -operads. r r Let Q be an M -operad represented by the span M Q 0 ← Q 1 → Q 0 . Recall that elements of Q 1 are depicted as x r We apply first the T-construction to get a category TM Q: 123 Plethysms and operads Q1  LQ 0 Q1 R Q0 D Q0 s t Q0 S Q0 Q0. The strength morphism is the same as in (4.1.2). Therefore the elements of Q 1 are the elements of Q 1 such that all the input objects coincide, x r so that x is an arrow in the category TM Q. Notice that Q 2 is a subset of Q 2 . Therefore r composition in TM Q is the same as composition in Q. For example x x y = = y ◦ (x, x) x ◦ y (4.2.1) where y ◦ (x, x) is composition in Q. Hence the recipe is to repeat x for each input of y and use composition in Q. r r r It is not difficult to see that the categories TM Ass and TM Sym (as well as TS Ass and r TS Sym) are self dual (see Examples 4.2.1 and 4.2.2 below). An obvious consequence of this self duality is that we get equivalent operads by applying the T-construction to their opposite categories. Nevertheless, when dealing with plethysm it is in fact more natural, from a combinatorial point of view, to apply the T-construction to the opposite categories. This is particularly apparent when we interpret the simplicial groupoid T S [9] as an operad (see Examples 6.1.7 and 6.2.6). For this reason, before applying the T-construction again r we take the opposite category TM Q op . The arrows of this category are depicted as inverted r arrows of TM Q: x (4.2.2) 123 A. Cebrian r r Now we finally apply the T-construction to get a S -operad T r Q op from the category TM Q op . S This step was made above for any category: the objects of Q 1 are sequences (x1 , . . . , xn ) of arrows xi ∈ Q 1 with the same output. For instance the pair x y is an operation (x, y) in T r Q op . Clearly T r Q op is a symmetric operad, since the groupoid of objects is discrete S S and the morphisms in the groupoid Q 1 are given by permutation of tuples. We show once and for all an example of composition in T r Q op : S x1 x2 y1 x1 x2 y1 x x x y y y y x y (4.2.3) and then of course we compose in Q, as in (4.2.1). Since in all the examples we are interested in the step of taking the opposite category does not affect the result (by self duality), we will drop the op indication from now on, but be aware that all the representations of operations follow this convention. r Example 4.2.1 If the starting M -operad is Ass, which is a noncolored operad, then it is easy r to see that the monoid TM Ass is isomorphic to (N+ , ×). Therefore the operations of T r Ass S are sequences of natural numbers and composition is given by multiplication. For example   (2, 3), (4, 7) ◦ (5, 9) = (5 · 2, 5 · 3, 9 · 4, 9 · 7) = (10, 15, 36, 63). r r If the starting M -operad is Ass2 the 2-colored associative operad, then the category TM Ass2 n has two objects and a morphism − → for every pair of objects and positive natural number n. Composition is given by multiplication. The operations of T r Ass2 are thus sequences of S such arrows with the same output. Suppose we start instead from a symmetric operad Q. Recall from Example 1.3.7 that r s a symmetric operad is an S-operad in Grpd such that Q 0 is discrete and S Q 0 ← − Q 1 is r discrete fibration. The T-construction to get another S -operad is completely analogous to the previous case, but in this case the groupoid Q 1 inherits morphisms from Q, so that for instance the element 123 Plethysms and operads x x y has 2! · 3!2 · 2! automorphisms, corresponding to 2! invariant permutations on (x, x, y) and permutations of the inputs. The latter contribution did not appear in the previous case, since Q was a planar operad. Notice that this means that T r Q op (also T r Q) is not a symmetric r S S operad, but just an S -operad in Grpd. r Example 4.2.2 If the starting S -operad is Sym, which is a noncolored symmetric operad, then r it is easy to see that the monoid TS Sym is isomorphic to the monoid (N+ , ×) internal to groupoids where Aut(n) ∼ = Sn . The objects of TSr Sym are the same as the objects in TSr Ass, and the morphisms are given by permutation of tuples (as in T r Ass) plus the ones given by S Aut(n) for each n. The colored case is analogous. 5 Plethysms and operads Let us present the relation between the several plethystic bialgebras, operads and the T- construction. Some proofs are omitted, since most of them are similar. The operads involved are the reduced symmetric operad Sym, the reduced associative operad Ass and their 2-colored versions. Also, playing the same role as these operads, we have a locally finite monoid Y . r r On the other hand, the T-constructions are taken with respect to the monads S and M , as in Section 4, and everything is internal to E = Grpd. Let us stress again that by Proposition 1.4.6, Lemmas 3.4.3 and 3.4.4 and the discussion of Section 4 all the bar constructions featuring in the present section are locally finite Segal groupoids, so that we can take cardinality to arrive at their incidence bialgebra in the classical sense of vector spaces. It is appropriate to begin with the classical bialgebras, which are the main cases. The following standard notation is used: • x = (x1 , x2 , . . . ), • : set of infinite vectors of natural numbers with λi = 0 for all i large enough and λ j  = 0 for some j, •   λ = (λ1 , λ2 , . . . ), • xλ = x1λ1 x2λ2 · · · , • aut(λ) = 1!λ1 λ1 ! · 2!λ2 λ2 ! · · · , • λ! = λ1 ! · λ2 ! · · · , • W : set of nonempty finite words of positive natural numbers, • W  ω = ω 1 . . . ωn , • xω = xω1 · · · xωn , • ω! = ω1 ! · · · ωn !. 5.1 The classical case The classical Faà di Bruno bialgebra F [12, 22] is obtained from the substitution of power series in one variable. Let xQx  be the ring of formal power series with coefficients in Q 123 A. Cebrian without constant term. Elements of xQx  are written  Fn F(x) = xn. n! n≥1 The set xQx  forms a (noncommutative) monoid with substitution of power series. The Faà di Bruno bialgebra F is the free polynomial algebra Q[A1 , A2 , . . . ] generated by the linear maps Ai : xQx  Q F Fi together with the comultiplication induced by substitution, meaning that (An )(F, G) = An (G ◦ F), and counit given by (An ) = An (x). The comultiplication of the generators can be explic- itly described through the (exponential) Bell polynomials Bn,k , which count the number of partitions of an n-element set into k blocks:  n (An ) = Ak ⊗ Bn,k (A1 , A2 , . . .). k=1 Theorem 5.1.1 (Joyal, cf. modern reformulation in [15]) The Faà di Bruno bialgebra F is isomorphic to the homotopy cardinality of the incidence bialgebra of BSym. Note that Sym is of course the same as TId Sym and, as explained in Section 4, it is also T r of the trivial monoid. This connects the Faà di Bruno bialgebra to the T-construction in S an analogous way as the plethystic bialgebras. Let us recall how the classical plethystic substitution works [22, 37, 38]. Let xQx be the ring of power series in infinitely many variables without constant term and coefficients in Q. Elements of xQx are written  Fλ λ F(x) = x . aut(λ) λ∈ Given two power series F, G ∈ xQx, their plethystic substitution is defined as (G  F)(x1 , x2 , . . . ) := G(F1 , F2 , . . . ), where Fk (x1 , x2 , . . . ) := F(xk , x2k , . . . ). (5.1.1) The set xQx forms a (noncommutative) monoid with plethystic substitution.  The plethys- tic bialgebra P [9, 36] is the free polynomial algebra P = Q {Aλ }λ generated by the set maps Aλ : xQx Q F Fλ together with the comultiplication induced by substitution, meaning that (Aλ )(F, G) = Aλ (G  F), 123 Plethysms and operads and counit given by (Aλ ) = Aλ (x1 ). The comultiplication of the generators can be explicitly described through the polynomials Pσ,λ , a plethystic version of the Bell polynomials which, in the terminology of Nava–Rota [37], count transversals of partitions.    (Aσ ) = Aλ ⊗ Pσ,λ {Aμ }μ . λ Example 5.1.2   P(0,0,0,1,0,2),(1,2) {Aμ }μ = 6!2 2!4! · 2! 6!2 2!4! · 2! = A(0,0,0,1) A2(0,0,1) + 2 A(0,0,0,0,0,1) A(0,0,1) A(0,1) . 2! 2! · 4!3! 2! 2 2 2! 2! · 6!3!2! (5.1.2) We can give a heuristic explanation of this. Define the k-th Verschiebung operator V k :  →  as  λi/k if k | i (V λ)i = k (5.1.3) 0 otherwise, Then Equation 5.1.2 indicates that the vector (0, 0, 0, 1, 0, 2) can be obtained in the following two ways, (0, 0, 0, 1, 0, 2) = V 1 (0, 0, 0, 1) + V 2 (0, 0, 1) + V 2 (0, 0, 1), (0, 0, 0, 1, 0, 2) = V 1 (0, 0, 0, 0, 0, 1) + V 2 (0, 0, 1) + V 2 (0, 1), where the Verschiebung operators used are determined by λ: one V 1 and two V 2 . The coefficients are given by the automorphisms of the vectors involved. See [9] for a detailed explanation. Theorem 5.1.3 The plethystic bialgebra P is isomorphic to the homotopy cardinality of the incidence bialgebra of BT r Sym. S Proof The comparison between these two incidence bialgebras was made in [9], where the simplicial interpretation of plethysm was established. In Section 6 we will see that indeed BT r Sym is equivalent to T S, the simplicial groupoid of [9]. S   Example 5.1.4 Let us see the interpretation of P(0,0,0,1,0,2),(1,2) {Aμ }μ (see Examples 5.1.2) from the point of view of BS T r Sym. The vectors σ = (0, 0, 0, 1, 0, 2) and λ = (1, 2) are S represented by and respectively. What we want to count is, roughly speaking, the number of ways we can obtain σ as a composition of λ with three operations. It is straightforward to see that there are essentially two choices: 123 A. Cebrian and which clearly coincide with the ones of Example 5.1.2. This example could be misleading, in the sense that each operation above contains only one operation of Sym. This happens of course because |σ | = |λ|. For instance, if we take instead λ = (1, 1) we obtain three possible choices: , and 5.2 Overview of variations We proceed to introduce the variations of the plethystic bialgebra we explore. For the set of variables (x1 , x2 , . . . ), there are three sources of variations. At the level of power series they are the following: (i) Commuting or noncommuting variables: of course in the classical case the variables commute. When the variables do not commute we will index them by ω ∈ W , rather than λ ∈ . (ii) Commuting or noncommuting coefficients. (iii) Two types of automorphisms: aut(λ) or λ! for commuting variables, and ω! or 1 for noncommuting variables. These variations are not independent: if the variables commute then the coefficients commute. Analogous variations can be obtained of the Faà di Bruno bialgebra, except in this case there is only one variable. At the objective level, these three variations correspond (respectively) to the following choices: r r (i) T-construction over S or over M . r r (ii) Bar construction over S or over M . (iii) Taking Sym or Ass as input operads. The reason why they are not independent is clear here: there is a cartesian natural trans- r r r r formation M ⇒ S that allows taking BS of a M -operad (see Section 1), but no natural transformation in the opposite direction. 123 Plethysms and operads Let us give a brief justification of these correspondences. Consider the following sequence of operations: a= This could be either an operation in one of the following operads: (i) T r Sym: in this case each operation has automorphisms, coming from the action of the S r symmetric group on Sym, and since the T-construction is over S we can permute the operations. This means that the isomorphism class of a is given by λ = (0, 3, 1, 2), since the order of the operations does not matter, and it has aut(λ) = 2!3 3! · 3!1 1! · 4!2 2! automorphisms. The corresponding bialgebra is thus P and this particular operation corresponds to A(0,3,1,2) , the linear map returning the coefficient of x23 x3 x42 / aut(λ). (ii) T r Sym: in this case the operations have automorphisms again, but since the T- M r construction is over M we cannot permute them. This means that the isomorphism class of a is given by ω = (3, 2, 4, 2, 2, 4), so that it corresponds to noncommut- ing variables. Clearly it has 3!2!4!2!2!4! automorphisms. Now, depending on the bar construction it corresponds to commuting or noncommuting coefficients. This partic- ular operation corresponds to A(3,2,4,2,2,4) , the linear map returning the coefficient of x3 x2 x4 x2 x2 x4 /ω!. (iii) T r Ass: in this case the operations do not have automorphisms, and since the T- M r construction is over M we cannot permute them. This means that the isomorphism class of a is given by ω = (3, 2, 4, 2, 2, 4), so that it corresponds to noncommuting variables, and it has no automorphisms. Now, depending on the bar construction it corresponds to commuting or noncommuting coefficients, as in the previous case. This particular operation corresponds to a(3,2,4,2,2,4) , the linear map returning the coefficient of x3 x2 x4 x2 x2 x4 . (vi) T r Ass: in this case the operations do not have automorphisms, and since the T- S r construction is over S we can permute them. This means that the isomorphism class of a is given by λ = (0, 3, 1, 2), and it has λ! = 3! · 1! · 2! automorphisms. There- fore it corresponds to commuting variables and coefficients. This particular operation corresponds to a(0,3,1,2) , the linear map returning the coefficient of x23 x3 x42 /λ!. The cases of Sym and Ass are developed in Subsections 5.3 and 5.4 respectively. In Subsection 5.5 we generalize Pexp to power series in the set of variables (xm | m ∈ Y ) indexed over a locally finite monoid. In Subsections 5.3 and 5.4 we also study the Faà di Bruno bialgebra in two variables and the plethystic bialgebra in the two sets of variables (x1 , x2 , . . . ), (y1 , y2 , . . . ). For the plethystic case we only consider commuting variables and coefficients. Let us give a similar digression as above for the plethystic cases. Consider the following 2-colored operation: 123 A. Cebrian a=   The isomorphism class of this operation is given by (λ1 , λ2 ) = (0, 2, 0, 2), (0,1,1,1) (since everything commutes now), and it can either be an operation in T r Ass2 or T r Ass2 . It thus S S corresponds to A  ∈ P2 or to a (0,2,0,2),(0,1,1,1)  ∈ P2 , the linear maps (0,2,0,2),(0,1,1,1) exp returning the coefficients of x22 x42 y2 y3 y4 / aut(λx ) aut(λ y ). 5.3 Bialgebras from Sym and Sym2 We have already seen two bialgebras arising from Sym in Subsection 5.1, the Faà di Bruno bialgebra F and the plethystic bialgebra P. Let us see the aforementioned variations. Replace xQx by xQx, that is, noncommuting variables. Elements of xQx are written  Fω F(x) = xω , ω! ω∈W Substitution of power series in xQx is defined in the same way as before (5.1.1). The ♦  with noncommuting variables P is defined as the free polynomial plethistic bialgebra algebra Q {Aω }ω on the set maps Aω and comultiplication and counit as usual. Theorem 5.3.1 The plethystic bialgebra with noncommuting variables P♦ is isomorphic to r the homotopy cardinality of the incidence bialgebra of BS T r Sym. M If we take xRx with R a noncommutative unital ring, then we get the noncommuta- tive plethystic bialgebra with noncommuting variables P♦,nc , which is the free associative unital algebra Q{Aω }ω  together with the usual comultiplication and counit. In this case, substitution of power series is defined in the same way but it is not associative. However the comultiplication is still associative. A proof of this can be found in [6] for the one variable case, which is obtained below. Theorem 5.3.2 The noncommutative plethystic bialgebra with noncommuting variables P♦,nc is isomorphic to the homotopy cardinality of the incidence bialgebra of BT r Sym. M Let us move forward to power series in two variables. All the results are also valid for any number of variables, but for simplicity and notation we have chosen to show the two variables case. Also, for the bivariate plethystic bialgebras, we do not enter into noncommutativity of the variables or of the coefficients. Let xQx, y  + yQx, y  be the ring of formal power series in the variables x and y with coefficients in Q without constant term. We will denote this ring by Q in the following lines, for the sake of notation. Elements of Q are written  Fn,m F(x, y) = x n ym . n!m! n+m≥1 123 Plethysms and operads The set Q×Q forms a (noncommutative) monoid with substitution of power series:     ◦ Q×Q × Q×Q Q×Q  1 2    (F , F ), (G 1 , G 2 ) G 1 (F 1 , F 2 ), G 2 (F 1 , F 2 ) . We define the Faà di Bruno bialgebra in two variables F2 as the free polynomial algebra i=1,2  Q {An,m }n+m≥1 generated by the set maps i Ain,m : Q×Q Q (F 1 , F 2 ) i Fn,m together with the comultiplication induced by substitution, meaning that     (Ain,m ) (F 1 , F 2 ), (G 1 , G 2 ) = Ain,m (G 1 , G 2 ) ◦ (F 1 , F 2 ) , and counit given by (Ain,m ) = Ain,m (x, y). Theorem 5.3.3 The Faà di Bruno bialgebra in two variables F2 is isomorphic to the homotopy cardinality of the incidence bialgebra of BSym2 . The same holds for n variables and Symn . Notice that Sym2 is the same as TId Sym and, as explained in Example 4.1.1, it is also T r C, where C = { 0 1 } . This connects the Faà di Bruno bialgebra in two variables to S the T-construction in an analogous way as the plethystic bialgebras. We can do the same with the power series ring in two sets of infinitely many variables xQx, y + yQx, y with coefficients in Q. We shall write X = (x, y), λ = (λ1 , λ2 ) ∈ 2 , aut(λ) = aut(λ1 ) aut(λ2 ), Xλ = xλ yλ , and XQX = xQx, y + yQx, y, 1 2 so that elements of XQX are written  Fλ F(X) = Xλ . aut(λ) λ The set XQX×XQX forms a (noncommutative) monoid with plethystic substitution of power series:      XQX×XQX × XQX×XQX XQX×XQX  1 2    (F , F ), (G 1 , G 2 ) G 1 (F 1 , F 2 ), G 2 (F 1 , F 2 )  bialgebra in two variables P is defined as the free polynomial algebra 2 The plethystic Q {Aλ } i i=1,2 generated by the set maps Aiλ : XQX×XQX Q (F 1 , F 2 ) Fλi together with the comultiplication induced by substitution, meaning that     (Aiλ ) (F 1 , F 2 ), (G 1 , G 2 ) = Aiλ (G 1 , G 2 ) ◦ (F 1 , F 2 ) , and counit given by (Aiλ ) = Aiλ (x, y). 123 A. Cebrian Theorem 5.3.4 The plethystic bialgebra in two variables P2 is isomorphic to the homotopy cardinality of the incidence bialgebra of BT r Sym2 . S   Example 5.3.5 We could define polynomials Pσ,λ 2 {A }i to express the comultiplication of μ μ  2 {A }i ,  Aiσ , in analogy to the univariate case. Let us see again the interpretation of Pσ,λ μ μ     for σ = (0, 0, 0, 0, 0, 1), (0,0,0,1,0,1) and λ = (1, 1), (0,1) , from the point of view of BS T r Sym2 . These two vectors are represented by S and respectively. The output color depends on whether we are computing the comultiplication of A1σ or A2σ . We assume the former, without loss of generality. It is easy to see that there are essentially three options, which are the only possible colorings of the solutions for the analogous case of Example 5.3.5: , and 5.4 Bialgebras from Ass and Ass2 Take again xQx , but write now elements of xQx  as  F(x) = fn x n . n≥1 The ordinary Faà di Bruno bialgebra Ford is the free polynomial algebra Q[a1 , a2 , . . . ] generated by the linear maps ai (F) = f i together with the comultiplication induced by substitution and counit given by (an ) = an (x), as before. Theorem 5.4.1 The ordinary Faà di Bruno bialgebra Ford is isomorphic to the homotopy r cardinality of the incidence bialgebra of BS Ass. It is clear that F and Ford are isomorphic bialgebras, since we have only changed the basis. r r However their combinatorial meaning is slightly different, and indeed BS Sym and BS Ass 123 Plethysms and operads are not equivalent. Note that Ass is of course the same as TId Ass and, as explained in Section 4, it is also T r of the trivial monoid. This connects the ordinary Faà di Bruno bialgebra to M the T-construction. If we replace above Q by R (a noncommutative unital ring), we obtain the noncommuta- tive Faà di Bruno bialgebra Fnc [6, 14, 29], the free associative unital algebra Qa1 , a2 , . . .  generated by the set maps ai (F) = f i , together with the comultiplication induced by substi- tution and counit (an ) = an (x), as before. In this case, substitution of power series is not associative, but the comultiplication is still coassociative [6]. It is clear that F and Ford are the abelianization of Fnc [6]. Theorem 5.4.2 The noncommutative Faà di Bruno bialgebra Fnc is isomorphic to the homo- r topy cardinality of the incidence bialgebra of BM Ass. We now move to the plethystic bialgebras. The exponential plethystic bialgebra Pexp is the same bialgebra as P, but in this case aut(λ) = λ! = λ1 !λ2 ! · · · [36]. The generators of this bialgebra are denoted by aλ . Theorem 5.4.3 The exponential plethystic bialgebra Pexp is isomorphic to the homotopy cardinality of the incidence bialgebra of BT r Ass. S ♦ The linear plethystic bialgebra with noncommuting variables Plin is the same bialgebra ♦ as P but without automorphisms of ω. The generators for this bialgebra are denoted aω . ♦ Theorem 5.4.4 The linear plethystic bialgebra with noncommuting variables Plin is isomor- r phic to the homotopy cardinality of the incidence bialgebra of BS T r Ass. M ♦,nc The noncommutative linear plethystic bialgebra with non-commutating variables Plin is the same as P♦,nc but without automorphisms on ω. We write aω for its generators. Contrarily to what it may seem, the noncommutativity simplifies the explicit formula for the comultiplication of the generators. Denote by |w| the length of a word. Let also WnW be the set of length n words of words of W . Finally, for k ∈ N and ω = ω1 . . . ωn ∈ W , define the kth Verschiebung operator as kω = (kω1 ) . . . (kωn ). Proposition 5.4.5 The comultiplication of P♦,nc is given by ⎛ ⎞   |ω| κ ⎝ (aν ) = Tν,ω aκi ⎠ ⊗ aω , ω∈W κ∈W W i=1 |ω| where  n κ 1 if ν = i=1 ωi κi Tν,ω = 0 otherwise. This proposition is analogous to [9, Proposition 3.3]. Theorem 5.4.6 The noncommutative linear plethystic bialgebra with noncommuting vari- ♦,nc ables Plin is isomorphic to the homotopy cardinality of the incidence bialgebra of BT r Ass. M 123 A. Cebrian Proof Notice that B1 T r Ass is discrete. Its elements are given by sequences of tuples M (m 11 , . . . , m 1n 1 ), . . . , (m k1 , . . . , m kn k ) of positive natural numbers (see Example 4.2.1), but there is only the identity morphisms between them. Thus juxtaposition of sequences gives BT r Ass a (nonsymmetric) monoidal M structure. Sequences containing one tuple are called connected, and form an algebra basis of ◦ the incidence bialgebra. The subgroupoid of connected sequences is denoted B1 T r Ass. It is ◦ ◦ M clear that π0 B1 T r Ass = B1 T r Ass is isomorphic to W , and that π0 B1 T r Ass = B1 T r Ass M M M M is isomorphic to W W . Although π0 B1 T r Ass = B1 T r Ass we keep using the notation δω for M M the isomorphism class of ω ∈ B1 T r Ass. It only remains to compute the comultiplication: M  (δν ) = | Iso(d0 κ, d1 ω)ν |δκ ⊗ δω . ω κ By the discussion above we only have to check that κ | Iso(d0 κ, d1 ω)ν | = Tν,ω , but this is clear because there is only one morphism between d0 κ and d1 ω and fibering over ν means taking the subset of those morphisms that give ν after composing, hence κ . | Iso(d0 κ, d1 ω)ν | = 1 if d1 (κ, ω) = ν and 0 otherwise, exactly as Tν,ω Let us move forward to power series in two variables. Again, all the results are also valid for any number of variables, but for simplicity and notation we have chosen to show the two variables case. Let Qx, y be the ring of formal power series in the noncommutative variables x and y with coefficients in Q without constant term. Elements of Qx, y are written  F(x, y) = f ω ω, ω where ω is a nonempty word in x and y. The set Qx, y forms a noncommutative monoid with substitution of power series. We define the Faà di Bruno  bialgebra in two noncommuting variables F2 as the free polynomial algebra Q {aω } generated by the set maps i aωi : Qx, y×Qx, y Q (F 1 , F 2 ) f ωi together with the counit given by (aωi ) = aωi (x, y) and the comultiplication induced by substitution. Theorem 5.4.7 The Faà di Bruno bialgebra in two noncommuting variables F2 is isomor- r phic to the homotopy cardinality of the incidence bialgebra of BS Ass2 . We obtain the noncommutative Faà di Bruno bialgebra in two noncommuting variables F2,nc by taking above power series with coefficients in R. Theorem 5.4.8 The noncommutative Faà di Bruno bialgebra in two noncommuting variables F2,nc is isomorphic to the homotopy cardinality of the incidence bialgebra of BAss2 . 123 Plethysms and operads Finally, the exponential plethystic bialgebra in two variables Pexp 2 is the same as P2 but with exponential automorphisms aut(λ) = λ1 !λ2 ! · · · . The generators of this bialgebra are denoted aλi . Theorem 5.4.9 The exponential plethystic bialgebra in two variables Pexp 2 is isomorphic to the homotopy cardinality of the incidence bialgebra of BT r Ass2 . S 5.5 Y-plethysm and bialgebras from Y In Subsection 5.4 we could have taken the locally finite monoid (N, ×) instead of Ass, since r TM Ass = (N, ×) (Example 4.2.1). In fact, we have indirectly done so in the proof of Theorem 5.4.6. It is the case that the three plethystic bialgebras of Subsection 5.4 can be generalized to any locally finite monoid. In this section we explain the generalization of Pexp , which arises from Y -plethysm, introduced by Méndez and Nava [34] in the context of colored species. Let Y be a locally finite monoid; this means that any m ∈ Y there has a finite number of two-step factorizations m = nk. This is the same as the finite decomposition property of Cartier–Foata [8]. Consider the set of variables x = {xm }m∈Y , and the ring of formal power series xQx, following the same conventions as above. Elements of xQx are written  fλ F(x) = xλ , λ! λ∈ where now the sum is indexed by the subset  ⊆ HomSet (Y , N) of maps with finite support, and xλ is the obvious monomial, for λ ∈ . In this case λ! = λm !. The monoid structure of Y defines an operation x n  xm = xmn , which extends to a binary operation on xQx as (G  F)(xm |m ∈ Y ) := G(Fm |m ∈ Y ), where Fm (xn |n ∈ Y ) := F(xmn |n ∈ Y ). This substitution operation was introduced in [34] in the context of species colored over a monoid, although their conditions on the monoid are more restrictive. The main example comes from the monoid (N+ , ×), which gives ordinary plethysm. Another relevant example is (N, +), which gives Fk (x) = F(xk , xk+1 , . . . ), which appears in [33]. The power series Fm can be described by using the Verschiebung operators: for each m ∈ Y we define the mth Verschiebung operator V m on HomSet (Y , N) as follows: for each λ ∈ HomSet (Y , N) and n ∈ Y,  V m λ(n) = λk . mk=n Clearly if Y = (N+ , ×)this gives the usual Verschiebung operators [9, 36, 37]. The power series Fm can be expressed as  fλ xV λ . m Fm (x) = aut(λ) λ  As usual, we define the Y -plethystic bialgebra PY as the polynomial algebra Q {aλ }λ on the set maps aλ : xQx → Q defined by aλ (F) = f λ , with comultiplication dual to plethystic substitution, that is (aλ )(F, G) = aλ (G  F), 123 A. Cebrian and counit given by (aλ ) = aλ (x1 ). What follows is devoted to express the comultiplication of PY . Consider a list μ ∈ n of n infinite vectors, regarded as a representative element of a multiset μ ∈ n /Sn . We denote by R(μ μ) ⊆ Sn the set of automorphisms that maps the list μ to itself. For example μ) has 2! · 1! · 3! elements. Notice that if μ , μ ∈ n are if μ = {α, α, β, γ , γ , γ } then R(μ representatives of the same multiset then there is an induced bijection R(μ μ) ∼ = R(μμ ). We may thus refer to R(μ μ) for a multiset μ ∈  /Sn by taking a representative, since we are n only interested in its cardinality. Fix two infinite vectors, σ, λ ∈ , and a list of infinite vectors μ ∈ n , with n = |λ|. We define the set of (λ, μ )−decompositions of σ as  μ ∼   Tσ,λ := p : μ −−→ {1, . . . , λm } | σ = V q(μ) μ , m∈Y μ μ∈μ where p is a bijection of n-element sets and q returns the index of p(μ) in the sum. A useful way to visualize an element of this set is as a placement of the elements of μ over a grid with λm cells in the mth column such that if we apply V m to the mth column and sum the cells the result is σ . For example, if λ = (λm 1 , λm 2 , λm 3 ) = (2, 1, 3) and μ = {α, α, β, γ , γ , γ } the placement γ α β γ γ α V m1 V m2 V m3 μ belongs to Tσ,λ if σ = V m 1 (γ +α)+V m 2 (γ )+V m 3 (α +β +γ ), where the sum is a pointwise μ vector sum in . Note that each such placement appears | R(μ μ)| times in Tσ,λ . Observe also  that if μ , μ ∈  are representatives of the same multiset then there is an induced bijection n μ μ μ Tσ,λ ∼= Tσ,λ . We may thus refer to Tσ,λ for a class μ ∈ |λ| /S|λ| by taking a representative, since we are only interested in its cardinality. Proposition 5.5.1 The comultiplication of PY is given by μ   aut(σ ) · |Tσ,λ | (σ ) = aμ . (5.51) μ) μ∈μ aut(λ) · aut(μ μ λ μ This proposition is analogous to [9, Proposition 3.3]. Theorem 5.5.2 The Y -plethystic bialgebra PY is isomorphic to the homotopy cardinality of the incidence bialgebra of BT r Y . S Proof of 5.5.2 Let us compute the homotopy cardinality of the incidence bialgebra of BT r Y . r S First of all, notice that the elements of B1 T r Y = S T r Y are sequences of tuples S S (m 11 , . . . , m 1n 1 ), . . . , (m k1 , . . . , m kn k ) of elements of Y . Juxtaposition of sequences gives BT r Y a symmetric monoidal structure. S Sequences containing only one tuple are called connected, and form an algebra basis of the 123 Plethysms and operads incidence bialgebra. Since the morphisms between tuples are given by permutations, it is ◦ clear that the set of isomorphism classes of connected elements π0 B1 T r Y is isomorphic to S , the subset of HomSet (Y , N) consisting of maps with finite support. The isomorphism class λ δλ of a connected element λ is given by the map Y −→ N such that λm is the number of times m appears in λ. Be aware that the same notation is used for either the connected elements of B1 T r Y and the maps representing their isomorphism class. Moreover, S  π0 B1 T r Y ∼ = n //Sn , S n so that an element τ ∈ π0 B1 T r Y may be identified with a multiset μ of maps. With these S identifications we clearly have μ), | Aut(λ)| = λ! and | Aut(τ )| = aut(μ for λ connected and τ not necessarily connected. The left hand sides refer to the automor- phisms groups in B1 T r Y , while the right hand sides were introduced above. S The assignment Qπ0 B1 T r Y −→ Pexp S δλ  −→ aλ δλ+μ = δλ δμ  −→ aλ aμ , for λ and μ connected, defines an isomorphism of algebras. Notice that λ + μ is the monoidal sum in B1 T r Y , which does not correspond to the pointwise sum of their corresponding infinite S vectors, since it has two connected components. We have to compute the coproduct in Qπ0 B1 T r Y . It is enough to compute it for connected S elements. From Lemma 2.3.1 we have, for σ connected,   | Iso(d0 τ, d1 λ)σ | (δσ ) = δτ ⊗ δλ . (5.52) τ | Aut(λ)|| Aut(τ )| λ In view of the discussion above, it only remains to show that μ | Iso(d0 τ, d1 λ)σ | = aut(σ ) · |Tσ,λ |. Consider representatives for τ and λ,   τ = (m 11 , . . . , m 1n 1 ), . . . , (m k1 , . . . , m kn k ) λ = (m 1 , . . . , m k ), then d0 τ = d1 λ = (1, . . . , 1), k times. This means that Iso(d0 τ, d1 λ) = Aut(1, . . . , 1) ∼ = Sk . Any element φ ∈ Iso(d0 τ, d1 λ) induces a map between sequences  1  φ (m 1 , . . . , m 1n 1 ), . . . , (m k1 , . . . , m kn k ) −→ (m 1 , . . . , m k ). We express it as a permutation on τ and write  φ(1) φ(k)  φ(τ ) = (m 1 , . . . , m φ(1) φ(k) n φ(1) ), . . . , (m 1 , . . . , m n φ(k) ) . Now, consider the subset     φ ∈ Iso(d0 τ, d1 λ) | d1 (φ(τ ), λ)  σ . 123 A. Cebrian It is straightforward to see that this subset is isomorphic to  μ ∼   Tσ,λ := p : μ −−→ {1, . . . , λm } | σ = V q(μ) μ , m∈M μ μ∈μ under the identifications τ → μ and φ → p. The summation of the Verschiebung operators is precisely composition of φ(τ ) and λ. Finally, since Iso(d0 τ, d1 λ)σ is a homotopy fiber we have that     μ Iso(d0 τ, d1 λ)σ ∼ = Aut(σ ) × φ ∈ Iso(d0 τ, d1 λ) | d1 (φ(τ ), λ)  σ ∼ = Aut(σ ) × Tσ,λ and therefore μ | Iso(d0 τ, d1 λ)σ | = aut(σ ) · |Tσ,λ |, as we wanted to see. This proves also Theorem 5.4.3 by taking the monoid (N+ , ×). 6 Relation with TS We end this work by exploring the relations between the T-construction and the simplicial groupoid T S of [9]. We first recall what this simplicial groupoid looks like. Then we prove that T S and BT r Sym are equivalent simplicial groupoids. This proves in particular Theorem S 5.1.3. Finally we show that the operads of Section 5 arising from Ass or Sym are also equivalent to similar simplicial groupoids. 6.1 The simplicial groupoid TS It can be defined through a general construction [9], but we content ourselves with a brief description: objects in T1 S and T2 S (1 and 2-simplices of T S) are, respectively, diagrams of finite sets and surjections t02 t01  t01 t12 t00 t11 , t00 t11 t22 . ∼ → ti j compatible with the diagram. In Morphisms of such shapes are levelwise bijections ti j − general Tn S is an analogous pyramid, with t0n in the peak, all of whose squares are pullbacks of sets. The face maps di remove all the sets containing an i index, and the degeneracy maps si repeat the ith diagonals. Diagrams whose last set is singleton are called connected. It is not difficult to see that T S is a Segal groupoid [9]. We now prove that T S  BT r Sym. We prove the equivalence by constructing an inter- S mediate simplicial groupoid. More precisely, we find a subsimplicial groupoid of T S which is equivalent to T S and isomorphic to BT r Sym. First of all we need some notation and S elementary results. 123 Plethysms and operads Definition 6.1.1 Consider the category of finite ordinals [n] = {1, . . . , n} and set maps. We say that a square q [m] [n] p  f (6.1.1) [l] g [k] is monotone if it is a pullback of sets, p is monotone and q is monotone at each fiber over p, that is, q| p−1 (i)| is monotone for all i ∈ [l]. Lemma 6.1.2 Consider the category of finite ordinals and set maps. (i) The class of monotone pullback squares is closed under composition of squares. g f (ii) Given a diagram [l] − → [k] ← − [n], there is a unique monotone square as 6.1.1. Proof (i) is clear, and (ii) follows fom the fact that we can totally order the pullback,  P= [l]i × [n]i , i∈[k] by using the orders of [l] and [n]. That is, given a, b ∈ P, then a < b if p(a) < p(b) or p(a) = p(b) and q(a) < q(b). Consider the full subsimplicial groupoid V ⊆ T S containing only the simplices whose entries are the finite ordinals [k], whose left-down-arrows and right-arrows are monotone surjections and whose left-down arrows are fiber-monotone in the sense of Definition 6.1.1, and whose pullback squares are monotone. Note that Lemma 6.1.2 ensures that V is well defined, meaning that the inclusion V → T S is a morphism of simplicial groupoids. Lemma 6.1.3 V → T S is an equivalence of simplicial groupoids. Proof Given an element of Tn S, t01 tn−1,n t00 t11 tn−1,n−1 tnn , it is clear we can choose an ordering of the tii and the ti,i+1 such that all the arrows between them are monotone. Then by Lemma 6.1.2 there exists a unique ordering on the rest of the ti j ’s making the pullback squares monotone. Hence the inclusion is essentially surjective. Since we have taken the full inclusion, the automorphism group of any elment of Vn is equal to to its automorphism group as an element of Tn S. Hence the inclusion is an equivalence. Note that in V the uniqueness of the monotone squares implies that the Segal maps are in fact isomorphisms, Vn ∼ = V1 ×V0 · · · ×V0 V1 . In other words, there is a well-defined composition d1 : V1 ×V0 V1 → V1 . In view of this we may drop the elements ti j with j ≥ i + 2 from the diagrams. 123 A. Cebrian Lemma 6.1.4 Let V be the operad whose n-ary operations are diagrams [m] [n] 1 where [m]  [n] is monotone, whose morphisms are entrywise bijections, and whose com- position is given by monotone pullback squares. Then V ∼ = BV. Proof The isomorphism is given by [m 1 ] [m k ] [m 1 + · · · + m k ] → [n 1 ] 1, , [n 2 ] 1, [n 1 + · · · + n k ] [k] at the level of 1-simplices and similarly in general. Lemma 6.1.5 V is isomorphic to T r Sym. S Proof An operation of T r Sym is a family of operations of Sym, which is equivalent to a S monotone surjection [m]  [n]. It is also clear that morphsims between operations of T r Sym S are the same as morphisms in V. Thus we only need to see that composition coincides. Let us denote by x the unique x-ary operation of Sym. Thus a general element of T r Sym is a S tuple (x1 , . . . , xn ). By definition of the T-construction (x1 , . . . , xn )  ((y11 , . . . , yk11 ), . . . , (y1n , . . . , yknn )) = (y11 · x1 , . . . , yk11 · x1 , . . . , y1n · xn , . . . , yknn · xn ), which is nothing but the pullback   i, j y ij xi      i, j y ij i xi  i  i ki 1, the composition of their corresponding operations in V. Proposition 6.1.6 The simplicial groupoids T S and BT r Sym are equivalent. S Proof It is direct from Lemmas 6.1.2, 6.1.3 and 6.1.4. 123 Plethysms and operads Example 6.1.7 Consider the following 2-simplex of BS T r Sym: S , or (6.1.2) We use colors here only to make the comparison more pleasant, but of course this is not a colored operad. This 2-simplex corresponds, in T S, to 17  7 5 (6.1.3) 3 2 1. It is opportune in this example to show that indeed the convention of drawing the operations upside down (or taking the opposite category before applying T r , see Diagram (4.2.2) and S the preceding digression) comes out more naturally in order to interpret T S as an operad. First of all, observe that at the level of finite sets and surjections the Verschiebung operators 5.1.3 can be regarded as a scalar multiplication, V S (X → B) = S × X → X → B, in the sense that if λ represents the class of X → B, then V |S| λ represents the class of V S (X → B). Under this perspective we can write the information on (6.1.3) as 17  3 = (9  2) + (8  1) = V 3 (3  2) + V 2 (4  1) = (3 × 3  2) + (2 × 4  1), (6.1.4) We can clearly see this in (6.1.2). On the contrary, it is not difficult to check that without this convention Equation (6.1.4) would rather appear as   17  3 = (9  2) + (8  1) = (2 × 3  1) + (1 × 3  1) + (4 × 2  1). 6.2 Other TS-like simplicial groupoids We now present other equivalences between variations of T S and some of the bar construc- tions treated before. First of all we introduce some notation: monotone surjections between ordered sets are denoted a • b. We call linear surjection a ◦ b a surjection between finite sets f : a  b with an order on f −1 (r ) for each r ∈ b. Notice that the composite of two monotone surjections is again a monotone surjection, and the composite of two linear surjections is again a linear surjection, with the obvious 123 A. Cebrian order. Moreover, given pullback squares p•  and  , •f q◦ ◦g we say that p and f are compatible if the order of p is induced by the order of f , in the sense of Lemma 6.1.2. Similarly, we say that q and g are compatible if the order of q is induced by the order of g. The proofs of all the following results are similar to the one of Proposition 6.1.6. To avoid repetitiveness we give only intuitive explanations. Example 6.2.1 The simplicial groupoid BS T r Ass is equivalent to the simplicial groupoid S constructed as T S but with the additional structure that all the left-down surjections are linear and compatible. Morphisms are order-preserving levelwise bijections. Hence the 1-simplices are diagrams t01 ◦ t00 t11 . The isomorphism classes of connected diagrams are again infinite vectors λ = (λ1 , λ2 , . . . ) as in T S, and the number of automorphisms of a connected element of class λ is precisely λ1 ! · λ2 ! · · · , since t01 is fixed. Example 6.2.2 The simplicial groupoid BS T r Ass is equivalent to the simplicial grou-poid M constructed as T S but with the additional structure that the left-down surjections and the right surjections are linear and compatible. Morphisms are order-preserving levelwise bijections. Hence the 1-simplices are diagrams t01 ◦ t00 ◦ t11 . Observe that for a connected element, t00 is totally ordered. Thus the isomorphism classes of connected elements are given by words ω = ω1 ω2 . . . ωn where ωi is the size of the ith fiber. It does not have any automorphisms, since t01 and t00 are fixed. Example 6.2.3 The simplicial groupoid BS T r Sym is equivalent to the simplicial groupoid M constructed as T S but with the additional structure that the right surjections are linear and compatible. Morphisms are order-preserving levelwise bijections. Hence the 1-simplices are diagrams t01 t00 ◦ t11 . Observe that for a connected element, t00 is totally ordered. Thus the isomorphism classes of connected elements are given by finite words ω = ω1 ω2 . . . ωn where ωi > 0 is the size of the ith fiber. It has ω! := ω1 !ω2 ! · · · ωn ! automorphisms, since t00 is fixed. 123 Plethysms and operads Example 6.2.4 The simplicial groupoid BM T r Sym is equivalent to the simplicial groupoid M constructed as T S but with the additional structure that the right surjections are monotone. Morphisms are order-preserving levelwise bijections. Hence the 1-simplices are diagrams t01 t00 • t11 . Observe that for a connected element, t00 is totally ordered. Thus the isomorphism classes of connected elements are given by finite words ω = ω1 ω2 . . . ωn where ωi > 0 is the size of the ith fiber. It has ω! := ω1 !ω2 ! · · · ωn ! automorphisms, since t00 is fixed. The difference between this simplicial groupoid and the one of Example 6.2.3 is that in this case t11 is also ordered. As a consequence the monoidal structure is not symmetric, so that the resulting incidence bialgebra is not commutative. Example 6.2.5 The simplicial groupoid BM T r Ass is equivalent to the simplicial groupoid M constructed as T S but with the additional structure that the left-down surjections and the right surjections are monotone and compatible. Morphisms are order-preserving levelwise bijections. Hence the 1-simplices are diagrams t01 • t00 • t11 . Observe that for a connected element, t00 is totally ordered. Thus the isomorphism classes of connected elements are given by words ω = ω1 ω2 . . . ωn where ωi is the size of the ith fiber. It does not have any automorphisms, since t01 and t00 are fixed. Again, the difference between this simplicial groupoid and the one of Example 6.2.2 is that in this case t11 is ordered. Example 6.2.6 Finally, the simplicial groupoid BS T r Sym2 is equivalent to the simplicial S groupoid constructed as T S but with the additional structure that the objects are 2-colored and the right-down surjections are color preserving. Morphisms are color-preserving levelwise bijections. For instance, the following 2-simplex of BS T r Sym2 , S , or (6.2.1) 123 A. Cebrian where now the colors do refer to the input and output colors, corresponds to the following 2-simplex: 17  3+4 5 (6.2.2) 1+2 1+1 1. Observe that indeed the right-down surjections are color-preserving. Funding Open Access Funding provided by Universitat Autonoma de Barcelona. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. A Appendices A.1 Axioms for internal category Let E be a cartesian category. A category C internal to E can be described by objects and arrows of E m C1 C1 ×C0 C1 C1 s t e C0 C0 C0 C1 s t where the pullback is taken along C1 −→ C0 ←− C1 , satisfying the following commutative diagrams: m m C1 ×C0 C1 C1 C1 ×C0 C1 C1 p1 s p2 t (A.1.1a) (A.1.1b) C1 s C0 C1 t C0 e e C0 C1 C0 C1 s (A.1.2a) t (A.1.2b) id id C0 C0 123 Plethysms and operads m×C0 C1 (C1 ×C0 C1 )×C0 C1 C1 ×C0 C1 C1 ×C0 (C1 ×C0 C1 ) m (A.1.3) C1 ×C0 m C1 ×C0 C1 m C1 e×C0 C1 C1 ×C0 e C0 ×C0 C1 C1 ×C0 C1 C1 ×C0 C0 C1 ×C0 C1 p2 m p1 m C1 C1 (A.1.4a) (A.1.4b) Axioms for P-operad Let E be a cartesian category and (P, μ, η) a cartesian monad. A P-multicategory Q can be described by objects and arrows of E m Q1 PQ 1 ×PQ 0 Q 1 Q1 s t e PQ 0 Q0 Q0 Q1 t s where the pullback is taken along PQ 1 − → PQ 0 ← − Q 1 , satisfying the following commutative diagrams: p1 PQ 1 ×PQ 0 Q 1 PQ 1 m Ps PQ 1 × Q 0 Q 1 Q1 m P Q02 (A.2.1a) p2 t (A.2.1b) μQ0 Q1 Q0 t Q1 s PQ 0 e e Q0 Q1 Q0 Q1 s (A.2.2a) t (A.2.2b) η Q0 id PQ 0 Q0 123 A. Cebrian Pm× Q 0 Q 1 (P2 Q 1 ×P2 Q 0 PQ 1 )×PQ 0 Q 1 PQ 1 ×PQ 0 Q 1 P2 Q 1 ×P2 Q 0 (PQ 1 ×PQ 0 Q 1 ) m (A.2.3) μ Q 1 ×μQ 0 m PQ 1 ×PQ 0 Q 1 m Q1 Pe× Q 0 Q 1 Q1 ×Q0 e PQ 0 ×PQ 0 Q 1 PQ 1 ×PQ 0 Q 1 Q 1 × Q 0 Q 0 PQ 1 ×PQ 0 Q 1 p2 m p1 m Q1 Q1 (A.2.4a) (A.2.4b) References 1. Baez, J.C., Dolan, J.: From finite sets to Feynman diagrams. In: Mathematics Unlimited—2001 and Beyond, pp. 29–50. Springer, Berlin (2001) 2. Bauer, T.: Formal plethories. Adv. Math. 254, 497–569 (2014). arXiv:1107.5745 3. Bergeron, F.: Une combinatoire du pléthysme. J. Combin. Theory Ser. A 46, 291–305 (1987) 4. Bergeron, F.: A combinatorial outlook on symmetric functions. J. Combin. Theory Ser. A 50, 226–234 (1989) 5. Borger, J., Wieland, B.: Plethystic algebra. Adv. Math. 194, 246–283 (2005). arXiv:math/0407227 6. Brouder, C., Frabetti, A., Krattenthaler, C.: noncommutative Hopf algebra of formal diffeomorphisms. Adv. Math. 200, 479–524 (2006). arXiv:math/0406117 7. Burroni, A.: T-catégories (catégories dans un triple). Cah. Topol. Géom. Différ. Catég. 12, 215–321 (1971) 8. Cartier, P., Foata, D.: Problèmes combinatoires de commutation et réarrangements. No. 85 in Lecture Notes in Mathematics. Springer-Verlag, Berlin, New York (1969). Republished in the “books” section of the Séminaire Lotharingien de Combinatoire 9. Cebrian, A.: A simplicial groupoid for plethysm. Algebr. Geom. Topol. 21(1), 421–446 (2021) 10. Cebrian, A.: Combinatorics of plethysm via Segal groupoids and operads. Ph.D. thesis. Universitat Autònoma de Barcelona (2020) 11. Chapoton, F., Livernet, M.: Relating two Hopf algebras built from an operad. Int. Math. Res. Notices 2007 (2007). arXiv:0707.3725 12. Doubilet, P.: A Hopf algebra arising from the lattice of partitions of a set. J. Algebra 28, 127–132 (1974) 13. Dyckerhoff , T., Kapranov, M.: Higher Segal Spaces. Lecture Notes in Mathematics 2244 (2019). arXiv:1212.3563 14. Ebrahimi-Fard, K., Lundervold, A., Manchon, D.: Noncommutative Bell polynomials, quasideterminants and incidence Hopf algebras. Int. J. Algebra Comput. 24, 671–705 (2014). arXiv:1402.4761 15. Gálvez-Carrillo, I., Kock, J., Tonks, A.: Groupoids and Faà di Bruno formulae for Green functions in bialgebras of trees. Adv. Math. 254, 79–117 (2014). arXiv:1207.6404 16. Gálvez-Carrillo, I., Kock, J., Tonks, A.: Homotopy linear algebra. Proc. R. Soc. Edinb. A. 148, 293–325 (2018) 123 Plethysms and operads 17. Gálvez-Carrillo, I., Kock, J., Tonks, A.: Decomposition spaces, incidence algebras and Möbius inversion I: basic theory. Adv. Math. 331, 952–105 (2018) 18. Gálvez-Carrillo, I., Kock, J., Tonks, A.: Decomposition spaces, incidence algebras and Möbius inversion II: completeness, length filtration, and finiteness. Adv. Math. 333, 1242–1292 (2018) 19. Gálvez-Carrillo, I., Kock, J., Tonks, A., Corrigendum to “Decomposition spaces, incidence algebras and Möbius inversion II: completeness, length filtration, and finiteness” [Adv. Math. 333,: 1242–1292]. Adv. Math. 371(2020), 107267 (2018) 20. Giraudo, S.: Combinatorial operads from monoids. J. Algebra Combin. 41, 493–538 (2015) 21. Giraudo, S.: Nonsymmetric Operads in Combinatorics. Springer Nature Switzerland AG (2018) 22. Joyal, A.: Une théorie combinatoire des séries formelles. Adv. Math. 42, 1–82 (1981) 23. Kock, A.: Strong functors and monoidal monads. Arch. Math. 23, 113–120 (1972) 24. Kock, J., Weber, M.: Faà di Bruno for operads and internal algebras. J. Lond. Math. Soc. 99, 919–944 (2019) 25. Lawvere, F.W., Menni, M.: The Hopf algebra of Möbius intervals. Theory Appl. Categ. 24, 221–265 (2010) 26. Leinster, T.: Higher Operads. Higher Categories. London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge (2004) 27. Littlewood, D.E.: Invariant theory, tensors and group characters. Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 239, 305–365 (1944) 28. Loday, J.-L., Vallette, B.: Algebraic Operads. Grundlehren der mathematischen Wissenschaften 346. Springer-Verlag, Berlin (2012) 29. Lundervold, A., Munthe-Kaas, H.: Hopf algebras of formal diffeomorphisms and numerical integration on manifolds. Contemp. Math. 539, 295–324 (2011). arXiv:0905.0087 30. Ian, G.: Macdonald. Symmetric Functions and Hall Polynomials. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York (1979) 31. Markl, M., Shnider, S., Stasheff, J.: Operads in Algebra, Topology and Physics. Mathematical Surveys and Monographs 96. American Mathematical Society (2002) 32. May, J.P.: The Geometry of Iterated Loop Spaces. Lecture Notes in Mathematics, vol. 271. Springer- Verlag, Berlin (1972) 33. Méndez, M.: Set Operads in Combinatorics and Computer Science. SpringerBriefs in Mathematics. Springer, Cham (2015) 34. Méndez, M., Nava, O.: Colored species, c-monoids, and plethysm. J. Combin. Theory Ser. A 64, 102–129 (1993) 35. Moggi, E.: Notions of computation and monads. Inform. Comput. 93, 155–92 (1991) 36. Nava, O.: On the combinatorics of plethysm. J. Combin. Theory Ser. A 46, 212–251 (1987) 37. Nava, O., Rota, G.-C.: Plethysm, categories, and combinatorics. Adv. Math. 58, 61–88 (1985) 38. Pólya, G.: Kombinatorische Anzahlbestimmungen für Gruppen. Graphen und chemische Verbindungen. Acta Math. 68, 145–254 (1937) 39. Rota, G.-C.: On the foundations of combinatorial theory. I. Theory of Möbius functions. Z. Wahrschein- lichkeitstheorie und Verw. Gebiete 2, 340–368 (1964) 40. Schmitt, W.R.: Incidence Hopf algebras. J. Pure Appl. Algebra 96, 299–330 (1994) 41. Stanley, R.P.: Enumerative Combinarorics. Cambridge Studies in Advanced Mathematics, vol. 2. Cam- bridge University Press, Cambridge (1999) 42. van der Laan, P.: Operads and the Hopf Algebras of Renormalisation. arXiv:math-ph/0311013 43. Van der Laan, P., Moerdijk, I.: The Renormalisation Bialgebra and Operads. arXiv:hep-th/0210226 44. Wadler, P.: Comprehending Monads. Special issue of selected papers from 6’th Conference on Lisp and Functional Programming, 2, 461–493 (1992) 45. Weber, M.: Operads as polynomial 2-monads. Theory Appl. Categ. 30, 1659–1712 (2015). arXiv:1412.7599 46. Weber, M.: Internal algebra classifiers as codescent objects of crossed internal categories. Theory Appl. Categ. 30, 1713–1792 (2015) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123