4
$\begingroup$

I am no combinateur, but I stumbled across the following construction when studying an operad arising from information theory (actually it's a special algebra of an A$_\infty$-operad). It looked familiar to me, but I could not place it. I was hoping someone here could throw me some search terms.

The construction is essentially a map $\phi$ from the set of rooted trees to the positive reals arising from some operations on the positive reals, $+$ and a collection of operations, one for each $n$, $\oplus_n$, taking $n$ arguments. Every one of these operations is symmetric and $+$ distributes over $\oplus_n$ for each $n$. There is a notion of composition of trees, which is just root-to-leaf adjoining of graphs. We require that whenever a tree, $T$, can be written as a composition of an $n$-corolla (ie. a rooted tree with $n+1$ vertices and $n$ leaves) and $n$ trees $A_1,..,A_n$, then

$\phi(T)=\phi(n$-corolla$)+\oplus_n(\phi(A_1),...,\phi(A_n))$.

So that $\phi$ is completely determined by its values on the set of $n$-corollae for each $n$. I was wondering if $\phi$ had a name or a combinatorial interpretation. For me, it is an internal algebra in an algebra where the trees correspond simultaneously to search algorithms, guessing strategies, ways of building up information measures, and ways of associating variables.

The map is actually defined more generally for such trees, since these trees act via $\oplus_n$ on the positive reals as prescribed by the $A_\infty$-operad. This allows us to define a more general recursion relation than the one above, but all are equivalent, so I will not fill this post with those technicalities.

Thanks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.