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_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$
with a left adjoint
$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$
with a left adjoint
$\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???
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.