## March 31, 2014

#### 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_n$ for $n \ge 0$. In a symmetric collection, each space $O_n$ has an action of the symmetric group $S_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 $n$-ary operations, the set of rooted trees having some of their leaves labelled $\{1, \dots, n\}$.

Conjecture 2. The free operad on the terminal collection has, as its space of $n$-ary operations, the set of planar rooted trees having some of their leaves labelled $\{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, \dots$, an $n$-tree is a quadruple $T=(V,E,s,t)$ where:

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

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

This data is required to satisfy the following conditions:

• $s : E \to V\sqcup \{1,\dots, n\}$ is a bijection;
• there exists exactly one $e\in E$ such that $t(e)=0$;
• for any $v \in V\sqcup\{1,\dots , n\}$ there exists a directed edge path from $v$ to $0$: that is, a sequence of edges $e_0, \dots, e_n$ and vertices $v_1 , \dots , v_n$ such that $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 \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, \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 $0$, but also a ‘pre-root’: the unique vertex with an edge going from it to $0$. 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 $Tree$ whose set of $n$-ary operations, $Tree_n$, consists of isomorphism classes of $n$-trees as defined above. I’m hoping someone has already proved this. And I hope someone has characterized this operad $Tree$ in a more algebraic way, as follows.

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

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

There is a forgetful functor from operads to symmetric collections

$U : Op \to STop$

$F: STop \to Op$

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

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

The algebras of $\Comm$ are commutative topological monoids.

Conjecture 1. There is a unique isomorphism of operads

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

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

(When I say “the unique $n$-ary operation in $Comm$”, but treating it as an operation in $F(U(Comm))$, I’m using the fact that the unique operation in $\Comm_n$ gives an element in $U(\Comm)_n$, and thus an operation in $F(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 $n$-tree is an $n$-tree in which each internal vertex $v$ is equipped with a linear order on the set of its children, i.e. the set $t^{-1}(v)$.

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

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

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

There is a forgetful functor

$\Upsilon : Op \to \mathbb{N}Top$

$\Phi : \mathbb{N}Top \to Op$

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

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

where the first functor freely creates a symmetric collection $G(C)$ from a collection $C$ by setting $G(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

$\psi : \Phi(\Upsilon (Comm)) \stackrel{\sim}{\longrightarrow} PTree$

that for each $n \ge 0$ sends the unique $n$-ary operation in $Comm$ to the corolla with $n$ leaves ordered so that $1 < \cdots < n$.

Have you seen a proof of this stuff???

Posted at March 31, 2014 9:02 AM UTC

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

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

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

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

The book Algebraic Operads is available online:

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

$Tree \cong S(Tree)$

where $S$ is the free commutative monoid functor. For planar trees $S$ can be replaced with $T$, 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

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

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

and similarly for trees without planar structure

$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

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

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

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

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

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

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 $p$ and $q$ have the same associated non-planar tree iff $E_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_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

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 $A$, denote by $A^\ast$ the free monoid on $A$. In otherwords, $A^\ast$ is the disjoint union of the cartesian products $A^n$, $n\geq 0$. Elements of $A^n$ might be thought of as words of length $n$. The multiplication on $A^\ast$ is defined by concatenation. Note also, that, for any non-negative integer $n$, the symmetric group $\Sigma_n$ acts (on the right) on the set $A^n$, by permuting the factors in tuples.

A broad relation on a set $A$ is a subset $R\subset A\times A^\ast$. Given $a\in A$ and $\alpha\in A^n$, we write $aR\alpha$ if $(a,\alpha)\in R$.

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

Reflexivity: $a\leq a$ for any $a\in A$.

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

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

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

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

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

where we have put $f(a_1,\ldots,a_n)=(f(a_1),\ldots,f(a_n))$ for $n$-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 $A$.

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

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

The broad partially ordered set $A$ is said to be minimal if, whenever we have $a\leq(a_1,\ldots,a_n)$ we must have $a_i\neq a_j$ for $i\neq j$.

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

At last, we can define a finite dendroidal order to be a finite and minimal broad partially ordered set $A$ which has a root and in which any element $a\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

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

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

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) (this is the minimal element in \bar r)
x < () (x has a ‘successor’, is not a leaf)
y < () (ditto)

and hence by transitivity we have also

r < (x)
r < (y)
r < ()

The purpose of the example is to show that the four relations
r < (xy), r < (x), r < (y), r < () are not contradictory.
Now alter the tree by keeping those four relations, but removing
the relations x < () and y < (). 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 < , 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

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.