Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 31, 2014

Operads and Trees

Posted by John Baez

Nina Otter is a master’s student in mathematics at ETH Zürich who has just gotten into the PhD program at Oxford. She and I are writing a paper on operads and the tree of life.

Anyone who knows about operads knows that they’re related to trees. But I’m hoping someone has proved some precise theorems about this relationship, so that we don’t have to.

By operad I’ll always mean a symmetric topological operad. Such a thing has an underlying ‘symmetric collection’, which in turn has an underlying ‘collection’. A collection is just a sequence of topological spaces O nO_n for n0n \ge 0. In a symmetric collection, each space O nO_n has an action of the symmetric group S nS_n.

I’m hoping that someone has already proved something like this:

Conjecture 1. The free operad on the terminal symmetric collection has, as its space of nn-ary operations, the set of rooted trees having some of their leaves labelled {1,,n}\{1, \dots, n\}.

Conjecture 2. The free operad on the terminal collection has, as its space of nn-ary operations, the set of planar rooted trees having some of their leaves labelled {1,,n}\{1, \dots, n\}.

Calling them ‘conjectures’ makes it sound like they might be hard — but they’re not supposed to be hard. If they’re right, they should be easy and in some sense well-known! But there are various slightly different concepts of ‘rooted tree’ and ‘rooted planar tree’, and we have to get the details right to make these conjectures true. For example, a graph theorist might draw a rooted planar tree like this:

while an operad theorist might draw it like this:

If the conjectures are right, we can use them to define the concepts of ‘rooted tree’ and ‘rooted planar tree’, thus side-stepping these details. And having purely operad-theoretic definitions of ‘tree’ and ‘rooted tree’ would make it a lot easier to use these concepts in operad theory. That’s what I want to do, ultimately. But proving these conjectures, and of course providing the precise definitions of ‘rooted tree’ and ‘rooted planar tree’ that make them true, would still be very nice.

And it would be even nicer if someone had already done this. So please provide references… and/or correct mistakes in the following stuff!

Rooted Trees

Definition. For any natural number n=0,1,2,n = 0, 1, 2, \dots, an nn-tree is a quadruple T=(V,E,s,t)T=(V,E,s,t) where:

  • VV is a finite set whose elements are called internal vertices;
  • EE is a finite non-empty set whose elements are called edges;
  • s:EV{1,,n}s: E \to V\sqcup \{1,\dots, n\} and t:EV{0}t: E \to V \sqcup\{0\} are maps sending any edge to its source and target, respectively.

Given u,vV{0}{1,,n}u,v\in V \sqcup\{0\} \sqcup \{1,\dots, n\}, we write uevu \stackrel{e}{\longrightarrow} v if eEe\in E is an edge such that s(e)=us(e)=u and t(e)=vt(e)=v.

This data is required to satisfy the following conditions:

  • s:EV{1,,n}s : E \to V\sqcup \{1,\dots, n\} is a bijection;
  • there exists exactly one eEe\in E such that t(e)=0t(e)=0;
  • for any vV{1,,n}v \in V\sqcup\{1,\dots , n\} there exists a directed edge path from vv to 00: that is, a sequence of edges e 0,,e ne_0, \dots, e_n and vertices v 1,,v nv_1 , \dots , v_n such that ve 0v 1,v 1e 1v 2,,v ne n0. v \stackrel{e_0}{\longrightarrow} v_1 , \; v_1 \stackrel{e_1}{\longrightarrow} v_2, \; \dots, \; v_n \stackrel{e_n}{\longrightarrow} 0 .

So the idea is that our tree has V{0}{1,,n} V \sqcup\{0\} \sqcup \{1,\dots, n\} as its set of vertices. There could be lots of leaves, but we’ve labelled some of them by numbers 1,,n1, \dots, n. In our pictures, the source of each edge is at its top, while the target is at bottom.

There is a root, called 00, but also a ‘pre-root’: the unique vertex with an edge going from it to 00. I’m not sure I like this last bit, and we might be able to eliminate this redundancy, but it’s built into the operad theorist’s picture here:

It might be a purely esthetic issue. Like everything else, it gets a bit more scary when we consider degenerate special cases.

I’m hoping there’s an operad TreeTree whose set of nn-ary operations, Tree nTree_n, consists of isomorphism classes of nn-trees as defined above. I’m hoping someone has already proved this. And I hope someone has characterized this operad TreeTree in a more algebraic way, as follows.

Definition. A symmetric collection CC consists of topological spaces {C n} n0\{C_n\}_{n \ge 0} together with a continuous action of the symmetric group S nS_n on each space C nC_n. A morphism of symmetric collections f:CCf : C \to C' consists of an S nS_n-equivariant continuous map f n:C nC nf_n : C_n \to C'_n for each n0n \ge 0. Symmetric collections and morphisms between them form a category STop{STop}.

(More concisely, if we denote the groupoid of sets of the {1,,n}\{1, \dots, n\} and bijections between these as SS, then STopSTop is the category of functors from SS to TopTop.)

There is a forgetful functor from operads to symmetric collections

U:OpSTop U : Op \to STop

with a left adjoint

F:STopOp F: STop \to Op

assigning to each symmetric collection the operad freely generated by it.

Definition. Let CommComm be the terminal operad: that is, the operad, unique up to isomorphism, such that Comm nComm_n is a 1-element set for each n0n \ge 0.

The algebras of Comm\Comm are commutative topological monoids.

Conjecture 1. There is a unique isomorphism of operads

ϕ:F(U(Comm))Tree \phi : F (U (Comm)) \stackrel{\sim}{\longrightarrow} Tree

that for each n0n \ge 0 sends the unique nn-ary operation in CommComm to the corolla with nn leaves: that is, the isomorphism class of nn-trees with no internal vertices.

(When I say “the unique nn-ary operation in CommComm”, but treating it as an operation in F(U(Comm))F(U(Comm)), I’m using the fact that the unique operation in Comm n\Comm_n gives an element in U(Comm) nU(\Comm)_n, and thus an operation in F(U(Comm)) nF(U(\Comm))_n.)

Planar Rooted Trees

And there should be a similar result relating planar rooted trees to collections without symmetric group actions!

Definition. A planar nn-tree is an nn-tree in which each internal vertex vv is equipped with a linear order on the set of its children, i.e. the set t 1(v)t^{-1}(v).

I’m hoping someone has constructed an operad PTreePTree whose set of nn-ary operations, PTree nPTree_n, consists of isomorphism classes of planar nn-trees. And I hope someone has characterized this operad PTreePTree as follows:

Definition. A collection CC consists of topological spaces {C n} n0\{C_n\}_{n \ge 0}. A morphism of collections f:CCf :C \to C' consists of a continuous map f n:C nC nf_n : C_n \to C'_n for each n0n \ge 0. Collections and morphisms between them form a category Top\mathbb{N}Top.

(If we denote the category with natural numbers as objects and only identity morphisms between as \mathbb{N}, then Top\mathbb{N}Top is the category of functors from \mathbb{N} to TopTop.)

There is a forgetful functor

ϒ:OpTop \Upsilon : Op \to \mathbb{N}Top

with a left adjoint

Φ:TopOp \Phi : \mathbb{N}Top \to Op

assigning to each collection the operad freely generated by it. This left adjoint is the composite

TopGSTopFOp \mathbb{N}Top \stackrel{G}{\longrightarrow} STop \stackrel{F}{\longrightarrow} Op

where the first functor freely creates a symmetric collection G(C)G(C) from a collection CC by setting G(C) n=S n×C nG(C)_n = S_n \times C_n, and the second freely generates an operad from a symmetric collection, as described above.

Conjecture 2. There is a unique isomorphism of operads

ψ:Φ(ϒ(Comm))PTree \psi : \Phi(\Upsilon (Comm)) \stackrel{\sim}{\longrightarrow} PTree

that for each n0n \ge 0 sends the unique nn-ary operation in CommComm to the corolla with nn leaves ordered so that 1<<n1 &lt; \cdots &lt; n.

Have you seen a proof of this stuff???

Posted at March 31, 2014 9:02 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2710

15 Comments & 0 Trackbacks

Re: Operads and Trees

For the planar case, there’s something like this in Appendix E of my higher category theory book. Inevitably, my combinatorial definition of tree is not identical to yours, but I hope it would be easy to see that they’re equivalent.

In the appendix, I only sketched the proof, because although I’d written it out in full in private notes, it was so fantastically dull that I didn’t want to inflict it on anyone else.

Posted by: Tom Leinster on March 31, 2014 12:33 PM | Permalink | Reply to this

Re: Operads and Trees

Some version of this result can be found in Markl, Shnider, and Stasheff’s Operads in Algebra, Topology and Physics (section 1.9) as well as in Loday and Vallette’s Algebraic Operads (section 5.6). I think the fact that you’re working in topological spaces isn’t essential; just use the left adjoint the forgetful functor from topological spaces to sets.

Posted by: Qiaochu Yuan on April 1, 2014 12:35 AM | Permalink | Reply to this

Re: Operads and Trees

Thanks! I’m aware of the result in Operads in Algebra, Topology and Physics, but I’m a bit wary because the definition of operad in this book is wrong (it’s missing one of the axioms relating the symmetric group actions and composition). I doubt this actually affects the truth of results in this book, but it makes it less than definitive. I hope this problem can be fixed in a future edition.

Posted by: John Baez on April 1, 2014 6:10 AM | Permalink | Reply to this

Re: Operads and Trees

The book Algebraic Operads is available online:

http://math.unice.fr/~brunov/Operads.pdf

See Section 5.5.1 for some references and a recurrence relation for the free operad based on the ‘definition’ of the set of trees

TreeS(Tree)Tree \cong S(Tree)

where SS is the free commutative monoid functor. For planar trees SS can be replaced with TT, the free tensor algebra.

John and Nina, do you have any applications of this operad structure in mind? Billera, Holmes and Vogtmann made use of CAT(0) geometry to give an algorithm to compute geodesics in these spaces of trees, which even allows one to average a finite set of metric trees. It’s one of my favourite pieces of applied maths. I’d love to see a practical application of operads on the same space!

Posted by: James Griffin on April 1, 2014 11:35 AM | Permalink | Reply to this

Re: Operads and Trees

Thanks, James! I’m not sure “application” is the best term for what we’re doing with the operad structure on the space of phylogenetic trees — and I’m quite sure “practical application” is the wrong way of describing it. You can see an overview of what we’ve done here. I hope there will be applications to reconstructing phylogenetic trees, but our work so far is more foundational in character.

I like the idea you allude to, of defining planar trees as the least fixed point of

PTree1+PTree+PTree 2+ PTree \cong 1 + PTree + PTree^2 + \cdots

and similarly for trees without planar structure

Tree1+Tree+Tree 22!+ Tree \cong 1 + Tree + \frac{Tree^2}{2!} + \cdots

This could be very helpful in getting a clean treatment.

Posted by: John Baez on April 1, 2014 10:12 PM | Permalink | Reply to this

Re: Operads and Trees

Dear John,

Did you look at example 2.14 in Mark Weber’s paper [Familial 2-functors and parametric right adjoints, TAC 18 (2007), 665-732]? It asserts your conjecture 1 about trees in terms of symmetric operads and in fact, in some sense defines trees in the way you seem you want to see them. Mark’s description is compatible with the one used by Weiss and Moerdijk: the theory of the dendroidal nerve is a particular case of a result of Tom, which is generalized by Mark’s theorem 4.10 in loc. cit., thanks to the example cited above. You may also find the paper of Nicolas Gambino and Joachim Koch [Polynomial functors and polynomial monads, Math. Proc. Cambridge Phil. Soc. 154 (2013), 153-192] useful: in some sense, it is a paper which is completely devoted to trees!

Posted by: Denis-Charles Cisinski on April 5, 2014 12:19 AM | Permalink | Reply to this

Re: Operads and Trees

Thanks! Those references are quite helpful!

Part of my problem is finding the best definition of tree for what I’m doing. This paper, a reference in one you mentioned, is helpful:

• Ieke Moerdijk and Ittay Weiss, Dendroidal sets.

It describes a category Ω\Omega of rooted trees. It describes the morphisms quite precisely, as maps between colored operads associated to these trees. But it doesn’t define the trees themselves in a very precise way: we need to understand the concept by virtue of our pre-exisitng familiarity with it.

There should be a very beautiful and precise ‘conceptual’ definition of these trees, which then can be expanded to a more ‘combinatorial’ definition a bit like the one I gave here. (The definition I gave here is not probably not perfect, but it illustrates what I mean.)

Another way to put it is this. Ω\Omega is supposed to be like Δ\Delta. Δ\Delta has a very quick ‘conceptual’ definition as the category of nonzero finite ordinals and order-preserving maps. What about Ω\Omega?

Posted by: John Baez on April 5, 2014 10:53 PM | Permalink | Reply to this

Re: Operads and Trees

One approach to answering that question would be to understand concretely what theory the topos of dendroidal sets classifies; once that is known, (the Cauchy completion of) Ω\Omega will be recognised as the category of finitely presented models of that theory.

For instance, already in the 1970s it was observed that the topos of simplicial sets classifies inhabited linearly ordered sets. Unsurprisingly, Δ\Delta is equivalent to the category of inhabited finite linearly ordered sets.

Posted by: Zhen Lin on April 6, 2014 2:03 AM | Permalink | Reply to this

Re: Operads and Trees

Yes, that’s a good strategy. Can anyone here implement it?

Posted by: John Baez on April 6, 2014 6:43 AM | Permalink | Reply to this

Re: Operads and Trees

I believe Ieke Moerdijk was trying for a while to describe the theory classified by the topos of dendroidal sets. We talked about this in 2009. I don’t know whether he found an answer in the end.

Posted by: Tom Leinster on April 6, 2014 3:02 PM | Permalink | Reply to this

Re: Operads and Trees

I see now that — just as Denis-Charles said — Weber’s paper Familial 2-functors and parametric right adjoints gives, in section 2.14, a kind of formalization of the notion of tree used in Moerdijk and Weiss’ work on dendroidal sets. There are some mild wrinkles, though:

One reconciles the above discussion of trees with that of [Moerdijk-Weiss, 2007a], in which non-planar trees are used, by observing that in an obvious way one can associate a non-planar tree to any multi-edge of T1, and pp and qq have the same associated non-planar tree iff E TpE TqE_T p \cong E_T q. Thus one has a bijection between non-planar trees and isomorphism classes of multigraphs in the image of E TE_T.

I wish there were treatments of the category of trees that were as elementary, accessible yet precise as those one can find for Δ\Delta! Of course it’s not as simple, but I feel it should be simpler than what people say so far.

Posted by: John Baez on April 6, 2014 7:31 AM | Permalink | Reply to this

Re: Operads and Trees

Here is an elementary description of Ω\Omega (which I took from Ittay Weiss’thesis). The idea is that there is an elementary notion of “dendroidal finite ordinals” and that Ω\Omega is the category of the non-empty such things. This still requires a bunch of definitions though.

Given a set AA, denote by A *A^\ast the free monoid on AA. In otherwords, A *A^\ast is the disjoint union of the cartesian products A nA^n, n0n\geq 0. Elements of A nA^n might be thought of as words of length nn. The multiplication on A *A^\ast is defined by concatenation. Note also, that, for any non-negative integer nn, the symmetric group Σ n\Sigma_n acts (on the right) on the set A nA^n, by permuting the factors in tuples.

A broad relation on a set AA is a subset RA×A *R\subset A\times A^\ast. Given aAa\in A and αA n\alpha\in A^n, we write aRαaR\alpha if (a,α)R(a,\alpha)\in R.

A broad partially ordered set is a pair (A,)(A,\leq), where AA is a set and \leq is a broad relation on AA which satisfies the following properties.

Reflexivity: aaa\leq a for any aAa\in A.

Transitivity: if a(a 1,,a n)a\leq(a_1,\ldots,a_n) and a iβ ia_i\leq\beta_i for 1in1\leq i\leq n, then aβa\leq\beta where β=β 1β n\beta=\beta_1\cdots\beta_n is the product (=concatenation) of the β i\beta_i’s.

Anti-symmetry: If α,βA n\alpha,\beta\in A^n and if aβa\leq\beta and bαb\leq\alpha for any aa and bb occuring in the words α\alpha and β\beta respectively, then α=β\alpha=\beta.

Permutability: If aαa\leq\alpha with αA n\alpha\in A^n, then, for any permutation σΣ n\sigma\in\Sigma_n, we have aασa\leq\alpha\sigma.

A morphism of broad posets f:ABf:A\to B is a map ff such that

aαf(a)f(α)a\leq\alpha \Rightarrow f(a)\leq f(\alpha)

where we have put f(a 1,,a n)=(f(a 1),,f(a n))f(a_1,\ldots,a_n)=(f(a_1),\ldots,f(a_n)) for nn-tuples.

The category Ω\Omega is a full subcategory of the category of broad partially ordered sets: we just have to express what are finite rooted trees in the language of broad partially ordered sets.

Consider a broad partially ordered set AA.

There is a partial order d\leq_d on AA, defined by a da 1a\leq_d a_1 whenever a(a 1,,a n)a\leq(a_1,\ldots,a_n). We then say that aa is dominated by a 1a_1. A root of AA is a minimal element of AA with respect to the domination preorder.

An element aa in AA the set a¯\bar a consists of those αA *\alpha\in A^\ast such that aa<α\alpha. We say that aa is a leaf if a¯\bar a is empty. We say that aa has a successor if the set a¯\bar a has a minimal element (which is then unique up to symmetries).

The broad partially ordered set AA is said to be minimal if, whenever we have a(a 1,,a n)a\leq(a_1,\ldots,a_n) we must have a ia ja_i\neq a_j for iji\neq j.

Finally the broad partially ordered set AA is finite is \leq is a finite subset of A×A nA\times A^n (this implies that the underying set AA is finite, of course).

At last, we can define a finite dendroidal order to be a finite and minimal broad partially ordered set AA which has a root and in which any element aAa\in A has a successor or is a leaf. The category Ω\Omega is the category of finite dendroidal orders.

I don’t know if this description of Ω\Omega is very conceptual of if it is elementary enough to your eyes, but, at least, it does not involve the notion of free operad.

Posted by: Denis-Charles Cisinski on April 7, 2014 10:13 PM | Permalink | Reply to this

Re: Operads and Trees

I think I have been a little clumsy with the notion of root: an element rr of AA is a root if it is dominated by any element of AA.

Posted by: Denis-Charles Cisinski on April 8, 2014 9:27 AM | Permalink | Reply to this

Re: Operads and Trees

I like the ideas of Weiss of broad relations and posets, but it seems to me that the implementation presented here is buggy. I think some freeness axiom is missing. Maybe I overlook something (this happens frequently).

Consider the tree with two nullary nodes and one binary node. So there are three edges: the root edge r, and its two children x and y. Altogether we have

r<(xy)r \lt (xy) (this is the minimal element in r¯\bar r)
x<()x \lt () (x has a ‘successor’, is not a leaf)
y<()y \lt () (ditto) and hence by transitivity we have also

r<(x)r \lt (x)
r<(y)r \lt (y)
r<()r \lt ()

The purpose of the example is to show that the four relations r<(xy),r<(x),r<(y),r<()r \lt (xy), r \lt (x), r \lt (y), r \lt () are not contradictory. Now alter the tree by keeping those four relations, but removing the relations x<()x \lt () and y<()y \lt (). Now x and y are leaves. The result is valid according to the listed axioms (as far as I can see), but should not be so in a correct tree formalism.

I think the correct implementation of the ‘broad’ idea involves something like first defining broad relations in which each symbol occurs at most once in the same <\lt , and altogether appears at most once on the left and at most once on the right. And then take transitive closure. I think Weiss did something like that (but maybe not in his thesis, and maybe not formulated exactly like that). Note then that the first condition is like saying that the building blocks are corollas (no repetition of symbols), the second condition is like saying that we glue together such corollas along edges (each edge used at most once for gluing), and finally the transitive closure corresponds to taking free operad. In the end the definition is similar to the one of my previous post.

Posted by: Joachim Kock on April 10, 2014 5:44 PM | Permalink | Reply to this

Re: Operads and Trees

There are indeed numerous equivalent definitions of ‘tree’. But being equivalent does not mean they are equally good! The value depends on how closely the formalism captures the features needed in the theory.

Let me first list some features ‘needed’, intended of course to sell my favourite definition of tree :-)

If coloured operads play any role, there should be a tree without nodes and with one edge (the unit tree). This tree indexes the colours (i.e. the objects). (Even if one’s primary interest is in non-coloured operads, it is very fruitful to step out to the setting of coloured operads, just as groupoids are a very fruitful supplement to groups. For example, a tree is a coloured operad, and a category is a coloured operad!)

The operations of the operad are indexed by corollas, i.e. one-node trees. There should be a category of elementary trees (corollas and unit trees) such that the underlying collection of an operad is a presheaf on elementary trees. This is just a formal way of saying that an operad has colours and operations, and that the operations have certain input-colours and an output colour.

To describe the algebraic structure, we need to be able to specify the configurations of operations we want to compose. These are the trees, and we need to describe trees as being configurations of corollas glued together along unit trees. More precisely, a tree should be a colimit of elementary trees.

To say precisely which configurations, inductive presecriptions are handy: we would like to say that a tree is either a unit tree or has a bottom corolla whose leaves indexes smaller trees. More formally, the set T of (isoclasses of) trees should be the least solution to a functional equation of the form

T = 1 + P(T)

For all these purposes, a notion of subtree inclusion is needed (something not all tree formalisms handle with equal elegance).

I think the following definition [J.Kock, Polynomial functors and trees] meets the desiderata. It is very similar to John’s definition, but avoids numberings, and leads to some nice formal ways of saying certain things.

Definition: A tree is a diagram of finite sets

    s       p       t
A <---- M ----> N ----> A

such that

(1) t injective (2) s is injective with singleton complement. The complement is called the root and is denoted 1. (3) with sigma: A –> A defined as sigma(1)=1 and otherwise sigma(x)=t(p(x)), we have: for each x in A there exists a natural number k such that sigma^k(x)=1.

Interpretation: A is the set of edges; N is the set of nodes.
M is the set of nodes with a marked incoming edge. t returns the outgoing edge of a node, s returns the marked edge, and p forgets the mark. Axiom 1 says that every edge is the outgoing edge of at most one node. Axiom 2 says that every edge is the incoming edge of precisely one node, except the root edge. Axiom 3 says that if you walk towards the root, you arrive there in finitely many steps.

A morphism of trees is a diagram

A'<---- M'----> N'----> A'
|       |       |       |
v       v       v       v
A <---- M ----> N ----> A

in which the middle square is a pullback. (This expresses arity preservation.) It follows from the axioms that necessarily the vertical arrows are injective, so the notion of map is that of subtree inclusion (and includes also automorphism).

The unit tree U is

1 <---- 0 ----> 0 ----> 1

An edge inclusion

1 <---- 0 ----> 0 ----> 1
|       |       |       |
v       v       v       v
A <---- M ----> N ----> A

is the root iff the left-hand square is a pullback, and it is a leaf iff the right-hand square is a pullback.

Given S <— U —> R such that the first inclusion is the root and the second a leaf, then the pushout exists in the category of trees: it is computed pointwise, so that on nodes it is the disjoint union, and on edges it is the amalgamated sum over the gluing edge. It is grafting of the tree S onto the specified leaf of R. The colimit descriptions of trees follow readily.

I pretend that this tree formalism is valuable in its own right. But the true motivation for it is that this shape of diagram is precisely the shape of representing diagrams for polynomial endofunctors.

To generate the Moerdijk-Weiss category Omega, more maps are needed: these are generated by the free-monad monad on polynomial endofunctors, exactly as Delta is generated from linear-graphs-and-graph-maps by the free-category monad. In fact, this case is just the linear case: a graph is a linear endofunctor, and a category is a linear polynomial monad.

The effect of the monad is that instead of just mapping nodes to nodes, one is now allowed to map nodes to subtrees.

A cool consequence of having trees and polynomial endofunctors on the same footing is that polynomial endofunctors are precisely what you want to decorate trees with. If P is a polynomial endofunctor represented by I <- E -> B -> I, a P-tree is a diagram

A <---- M ----> N ----> A
|       |       |       |
v       v       v       v
I <---- E ----> B ----> I

where the middle square is a pullback. For suitable choices of P, this gives notions such as planar tree, binary tree, and opetopes. If you allow P to be given by groupoids, it also gives naked trees, namely when P is the free-commutative-monoid monad (the exponential functor). It also covers many interesting tree-like structures with symmetries, such as Feynman diagrams.

The set of isoclasses of P-trees forms the initial algebra for 1+P, or equivalently, forms the operations of the free monad on P. These two descriptions are the inductive characterisations of P-trees used in type theory. I think it is interesting that the above non-inductive characterisation is possible.

So much for trees. Regarding free operads, note first that non-symmetric operads are the same thing as polynomial monads cartesian over the free-monoid monad L, and that L-trees are precisely planar trees. Modulo these identifications, a version of Conjecture 2 is in [Polynomial functors and trees], and also in Leinster’s book. In the symmetric case, one can either consider the free-operad monad on collections (presheaves on elementary trees), or (as Weber does) start instead with non-symmetric collections, and let the monad generate the symmetries too. (This has the technical advantage that the monad is now a local right adjoint.) The free operad on a collection has the property that the symmetric group actions are free. Operads with this property are precisely the (finitary) polynomial monads. Since free operads are polynomial, the polynomial setting is sufficient to generate the right tree morphisms, but not enough to establish Conjecture 1. However, as soon as one upgrades from sets to groupoids, these subtleties go away: the notions of operad and (discrete-finitary) polynomial monad coincide. The infinity-version of these results are in a forthcoming paper joint with David Gepner. A few of them (relevant to this discussion) are previewed in my conference paper [Data types with symmetries and polynomial functors over groupoids].

Posted by: Joachim Kock on April 10, 2014 5:38 PM | Permalink | Reply to this

Post a New Comment