Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This follows Ryan Budney's comment to the question asked here.

What is the automorphism group of the rooted tree operad?

(By the rooted tree operad, I just mean the operad with object rooted trees and morphisms given by grafting a root to a leaf).

share|improve this question
Are you interested in the linear operad, or the setwise operad? Also what is the arity of a tree, is it the number of vertices or the number of leaves? Also I wouldn't call it the rooted tree operad, I would guess that most people would take this to be a form of the PreLie operad as described by Chapoton and Livernet. –  James Griffin Sep 29 '10 at 13:38
arity = number of leaves. –  Dr Shello Sep 29 '10 at 14:27
add comment

1 Answer

I think the answer to the question as literally stated is "the trivial group", but I think there are related inquiries which get into some deep combinatorics.

One way of thinking about the rooted tree operad is that it is the free operad $O(F)$ generated by the Joyal species $F$ (a functor $\mathbb{P} \to Set$ where $\mathbb{P}$ is the groupoid of finite sets $\{1, \ldots, n\}$ and permutations) where $F(0)$ is empty and $F(n)$ is a singleton for $n \geq 1$. You can think of the element of $F(n)$ as a "sprout" $s_n$ consisting of a root, $n$ leaves, and no other nodes, and then the elements of $O(F)$ are obtained recursively by starting with sprouts and applying grafting operations.

So we're looking at operad automorphisms $\phi: O(F) \to O(F)$. By freeness, the endomorphisms of $O(F)$ are in bijection with natural transformations $\psi: F \to U O(F)$ where $U O(F)$ is the underlying species or permutation representation of $O(F)$. Concretely, to give such a natural transformation is to give a collection of trees $t_n = \psi_n(s_n)$ for all $n \geq 1$ where each $t_n$ must be invariant under permuting the leaves, since the sprout $s_n$ is invariant under such permutations. That's a pretty strong condition on $t_n$, and there are actually precious few such collections.

But now you want more: you want $\phi$ to be an automorphism as well. So each sprout $s_n$ must be in the image of $\phi_n$. But no nonsprout tree $u$ can ever map to $s_n$ under $\phi_n$, because if $u$ is obtained by grafting together more than one sprout $s_k$, then $\phi_n(u)$ is obtained by similarly grafting together more than one tree $t_k$, and this is never a sprout.

So in order for there to exist $u$ such that $\phi_n(u) = s_n$, we must have $u = s_n$. To have that for all $n$ means $\psi(s_n) = s_n$ for all $n$, hence the only operad automorphism is the identity automorphism.

I think a more interesting inquiry is to understand the groupoid of rooted trees and isomorphisms between them. This is an incredibly rich object.

Edit: Let me make my last suggestion more precise. Let's define a rooted tree to be a finite set $X$ equipped with a function $f: X \to X$ and an element $r \in X$ such that $f^{(n)}(X) = \{r\}$ for sufficiently large $n$. The idea is that $f(x)$ is one step closer to the root than $x$, unless $x$ is the root. Then an isomorphism is a function $\phi: X \to Y$ which preserves the stepping-closer function and the root. It is determined by its restriction to the leaf set.

But even this groupoid isn't that mysterious; it seems automorphism groups are iterated wreath products of symmetric groups. Here is a different but related inquiry which I think is rather more interesting: regarding trees $T$ as posets, describe the category of order-preserving bijections between trees.

share|improve this answer
Very interesting. Can you say more about this groupoid of rooted trees? Also, what are examples of: - a "simple" operad that has a non-trivial automorphism group? - an operad that has a relatively simple automorphism group? –  Dr Shello Sep 29 '10 at 14:34
1. The groupoid is equivalent to a sum over isomorphism classes of trees of the automorphism groups of class representatives, and each such automorphism group is an iterated wreath products of symmetric groups. A useful picture might be to think of a tree as a hereditarily finite multiset. Then an automorphism of a multiset consists of a permutation of multiple copies of an element together with an automorphism of each element (as a multiset). 2. E.g., a monoid or group can be viewed as an operad where each operation has arity one. Pick a monoid with an interesting automorphism group. (Cont.) –  Todd Trimble Sep 30 '10 at 7:38
For example, free groups have interesting automorphism groups; they contain braid groups for instance (cf. Artin representation). 3. I am not absolutely sure, but I think the automorphism group of the operad whose algebras are monoids might be Z mod 2. The nontrivial automorphism would send an operation of arity n, namely a total ordering of the elements 1, 2, ..., n, to the reverse ordering. –  Todd Trimble Sep 30 '10 at 7:50
That's right the automorphism group of the (set-wise) associative operad is Z mod 2. A really important point is that automorphisms of operads induce automorphisms of categories of algebras. In the case of the associative operad the non-trivial automorphism takes an algebra A to its oppositive algebra. –  James Griffin Sep 30 '10 at 10:54
Oh and I think that we should point out that the automorphism group of the operad in the original question is only trivial if we take it to be the set-wise operad. Working instead with the linear version I think we get a group resembling the upper-triangular matrices, but I haven't checked the details. –  James Griffin Sep 30 '10 at 10:58
show 3 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.