# Is the following invariant of rooted trees a complete invariant?

Recall that rooted trees may be generated by starting with a trivial rooted tree (just a vertex), along with the operations of grafting a number of trees (identify their roots) and adding a new vertex to the tree to be a new minimum element. We will call this second operation "leafing".

Now let us define an invariant of rooted trees. If $T$ is a rooted tree, we will denote $P_T(z)$ to be the associated polynomial.

If the number of edges of $T$ is zero, then $P_T(z)=1$.

If $T'$ is the leafing of $T$, then $P_{T'}(z)=(z+1)P(z)+1$.

If $T$ is the grafting of $T_i, i=1\ldots n$, then $P_T(z)=P_{T_1}(z)P_{T_2}(z)\ldots P_{T_n}(z)$.

This polynomial is an isomorphism invariant of rooted trees. My question is

If $P_T=P_{T'}$, are the rooted trees, $T,T"$ isomorphic? If these trees are not isomorphic, what is the smallest counterexample? Any references to this invariant would be appreciated.

-
Interesting question. You might compare what you are doing with the paper "On distinguishing trees by their chromatic symmetric functions" by Jeremy Martin, Matthew Morin and Jennifer Wagner, though they are dealing with unrooted trees. I wonder if your polynomial is somehow a specialization of the subtree polynomial $S_T$, which they prove is not as strong (for purpose of distinguishing trees) as the chromatic symmetric function. It looks like it is probably an open question whether the chromatic symmetric function can distinguish trees -- or at least it was when this paper was written. – Patricia Hersh Sep 23 '12 at 15:23
Hope you don't mind the new tag I just added. People in enumerative combinatorics definitely work on questions of this flavor. – Patricia Hersh Sep 23 '12 at 16:07
Thank you for the addition of the tag. It could only help the question. – Spice the Bird Sep 23 '12 at 19:58
I went back and calculated your above polynomial $P_T$ for the two trees given in Figure 2 of the paper I mention above which the subtree polynomial $S_T$ also mentioned above couldn't distinguish. Your polynomial did distinguish these. To save time, I actually just compared a few evaluations of the two polynomials, which was enough to see this. I didn't look at how your polynomial relates to the chromatic symmetric functions though. Any chance that when your root has a single child, your polynomial is irreducible over ${\bf Z}[z]$? Or is that too much to hope for? – Patricia Hersh Sep 24 '12 at 13:19
The linear tree with n nodes (n+1 vertices, one of them the root) has polynomial $((z+1)^{(n+1)}−1)/(z)$. So no – Spice the Bird Sep 24 '12 at 16:52

Chaudhary and Gordon ("Tutte polynomials for trees," J. Graph Theory 15, no. 3 (1991), 317-331) construct a couple of invariants that look very similar to yours. They prove that these invariants do in fact determine a rooted tree up to isomorphism.

The relevant invariant from the Chaudhary-Gordon paper is what they call $f_p(T;t,z)$. This is a polynomial in two variables $t,z$ that satisfies the recurrence $$f_p(L(T);t,z) = t(z+1)f(T) + 1 - tz,$$ $$f_p(T_1*\cdots*T_r;t,z) = f(T_1)\cdots f(T_r)$$

where $L$ means leafing and $*$ means grafting. (These are Prop 4(b) and and Prop 5 in Chaudhary-Gordon.) If I'm doing the algebra right, your invariant is $P_T(z) = f_p(T;z+1,0).$

Chaudhary and Gordon give an example of two rooted trees on 8 vertices with the same values of $f_p(T;t,z)$. The edge sets could be labeled as 01,12,24,13,35,56,57 and 01,12,13,34,35,56,67, with 0 the root vertex in both cases. (Probably a good idea to confirm this if you have code to compute your invariant quickly.)

-
Did somebody vote this down? My calculations indicate the Jeremy is absolutely right. The polynomials as modified by Owen are equal and are $z^7 + 3z^6 + 4z^5 + 4z^4 + 3z^3 + 2z^2 +z + 1$. I am very glad to have this answer, and I believe it absolutely deserves to be upvoted. – Todd Trimble Sep 26 '12 at 20:51
"the Jeremy" --> that Jeremy – Todd Trimble Sep 26 '12 at 20:53
Great! This excellent answer absolutely settles the question, and provides a truly complete invariant. – Owen Biesel Sep 26 '12 at 21:40
Very happy to help! – Jeremy Martin Sep 26 '12 at 21:44
Their is a smaller set of trees that also works. Just chop off the first root to get 12,24,13,35,56,57 and 12,13,34,35,56,67. – Spice the Bird Sep 27 '12 at 19:58

This is not a complete answer, but there is a nice description of the information in $P_T$ which may prove useful to someone else.

First of all, I will define a slightly different polynomial $\tilde P_Z(T)$: Grafting works the same way, but if $T'$ is the leafing of $T$, then I define $\tilde P_{T'}(z)= z\tilde P_T(z)+1$. It's an easy proof by recursion that $\tilde P_T(z) = P_T(z-1)$, so this new polynomial determines $T$ just as well or poorly as yours.

By "node" of $T$, I mean a vertex of $T$ other than its root, and by "subtree" $T'$ of $T$, I mean a subgraph of $T$, such that for every node of $T$ included in $T'$, the node's parent and the edge to it are also included in $T'$. [Edit: These are non-standard uses of those words.] Then the coefficient of $z^n$ in $\tilde P_T(z)$ is the number of $n$-node subtrees of $T$. This is because, for $n>0$, choosing an $n$-node subtree of the leafing of $T$ is the same as choosing an $(n-1)$-node subtree of $T$, and for any $n$, choosing an $n$-node subtree of the grafting of $T$ and $T'$ is the same is choosing a $k$-node subtree of $T$ and an $(n-k)$-node subtree of $T'$ for some $k$ between $0$ and $n$.

Some consequences include:

• If $T$ has $n$ nodes (vertices other than the root), then the highest-order term of $\tilde P_T(z)$ is $z^n$.
• The coefficient of $z$ in $\tilde P_T(z)$ is the degree of the root of $T$.
• If $T$ has $a$ nodes at distance $1$ from the root, and $b$ nodes at distance $2$, then the coefficient of $z^2$ in $\tilde P_T(z)$ is ${a \choose 2}+ b$.
• If $T$ has a total of $n$ nodes, then the coefficient of $z^{n-1}$ is the number of leaves of $T$ (nodes with degree 1).

Hence if $\tilde P_T(z)=\tilde P_{T'}(z)$, then $T$ and $T'$ have the same numbers of vertices and leaves, their roots have the same degrees, and they have the same total number of vertices at distance $2$ from the root. It seems that more should be true, but I haven't proven any more.

Edit: I've now proved the following result: if $T$ and $T'$ are graphs whose nodes are distance at most $2$ from the root, and such that $\tilde P_T(z) = \tilde P_{T'}(z)$, then $T\cong T'$.

Proof: A rooted tree of depth at most $2$ corresponds to a sequence of natural numbers $b_1, b_2, \ldots, b_a$, where $a$ is the number of children of the root, and $b_i$ is the number of children of the $i$th child of the root. Then $$\tilde P_{T}(z) = \prod_{i=1}^a (z(z+1)^{b_i} + 1)$$ $$= \prod_{i=1}^a \left(1+{b_i\choose 0}z + {b_i\choose 1}z^2 + \ldots + {b_i\choose k}z^{k+1} + \ldots + {b_i\choose b_i-1}z^{b_i} + {b_i\choose b_i}z^{b_i+1}\right)$$ I show that $\tilde P_T(z)$ determines the $b_i$ up to reordering, and hence $T$ up to isomorphism.

First, note that knowing the $b_i$ up to reordering is the same as knowing the elementary symmetric polynomials in the $b_i$, because they are the solutions of $\prod_{i=1}^a(x-b_i)=0$. Or equivalently, by Newton's identities, that information is contained in the sums $\sum_{i=1}^a b_i^k$ for all $k\geq 0$. In turn, knowing the $\sum_{i=1}^a b_i^k$ for $k$ up to $n$ is the same as knowing the $\sum_{i=1}{b_i\choose k}$ for $k$ up to $n$, through simple linear identities relating the two sets of data.

Now I show that $\tilde P_T(z)$ does determine each $\sum_{i=1}^a {b_i\choose k}$ for $k \geq 0$, by induction on $k$. Suppose we know that $\tilde P_T(z)$ determines $\sum_{i=1}^a {b_i\choose k}$ for $0\leq k < n$, and now consider the coefficient of $z^{n+1}$. There is a contribution from each partition $n+1 = \lambda_1+\lambda_2+\ldots+\lambda_m$ of $n+1$, given by $$\sum_{i_1,\ldots,i_m\text{ distinct}}\left(\prod_{j=1}^m {b_i\choose \lambda_i-1}z^{\lambda_i}\right)=\left(\sum_{i_1,\ldots,i_m\text{ distinct}}\prod_{j=1}^m {b_i\choose \lambda_i-1}\right)z^{n+1}.$$ Considering the term in parentheses on the right-hand side as a polynomial in the $b_i$, note that it is symmetric in the $b_i$ and has degree $\sum_{j=1}^m(\lambda_j-1) = (n+1)-m< n$ if $m>1$. Hence such contributions are expressible in terms of the $\sum_{i=1}^a {b_i\choose k}$ for $0\leq k < n$, and so can be deduced from $\tilde P_T(z)$ by the induction hypothesis, unless the partition is simply $n+1=(n+1)$, in which case the resulting term is $\sum_{i=1}^a{b_i\choose n}z^{n+1}$. Therefore the coefficient of $z^{n+1}$ in $\tilde P_T(z)$ differs predictably from $\sum_{i=1}^a {b_i\choose n}$, so the latter is deducible from $\tilde P_T(z)$ as well.

Knowing the $\sum_{i=1}^a {b_i\choose k}$ for all $k$, we can work backwards: first we inductively deduce the $\sum_{i=1}^a b_i^k$, from which Newton's identities tell us the values of the elementary symmetric polynomials evaluated at the $b_i$. Then we recover the simplified form of $\prod_{i=1}^a (x-b_i)$, and the $b_i$ are its roots.

For example: If $\tilde P_T(z) = z^4 + 3z^3 + 3z^2 + 2z + 1$ and we know $T$ has no nodes of distance more than $2$ from the root, then we can recover $T$ as follows. The coefficient of $z$ is $a=2$, so we are trying to find $b_1$ and $b_2$ such that $$P_T(z) = (z(z+1)^{b_1} + 1)(z(z+1)^{b_2} + 1).$$ The coefficient of $z^2$ is ${a\choose 2} + (b_1+b_2) = 1 + (b_1+b_2) = 3$, so $b_1+b_2 = 2$. And the coefficient of $z^3$ is ${a\choose 3} + \sum_{i\neq j} b_i + \sum_i {b_i\choose 2} = (0) + (b_1+b_2) + \left({b_1\choose 2} + {b_2\choose 2}\right) = 2 + {b_1\choose 2} + {b_2\choose 2} = 3$, so ${b_1\choose 2} + {b_2\choose 2} = 1$. Hence $\frac{b_1^2-b_1}{2} + \frac{b_2^2-b_2}{2} = \frac{(b_1^2 + b_2^2) - (b_1 + b_2)}{2} = \frac{(b_1^2 + b_2^2) - 2}{2} = 1$, so $b_1^2 + b_2^2 = 4$. Therefore $b_1b_2 = \frac{(b_1 + b_2)^2 - (b_1^2 + b_2^2)}{2} = \frac{2^2 - 4}{2} = 0$, so $b_1$ and $b_2$ are the roots of $$x^2 - (b_1+b_2)x + (b_1b_2) = x^2 - 2x.$$ Therefore $b_1$ and $b_2$ are $0$ and $2$, up to reordering, so $T$ is the tree whose root has $a=2$ children, one of which has $0$ children, and the other of which has $2$.

-
Thank you for your answer. Is their a reference for your invariant? I am wondering about complete invariants. The absence of a discussion of that seems to indicate that this might be an open question? Also, are you sure that your polynomial is mine shifted by one? Mine shifted by one is $zP(z-1)+1$. maybe I am missing something silly? – Spice the Bird Sep 22 '12 at 22:50
I just made mine $\tilde P(z) = P(z-1)$, so the recurrence relation for mine is $\tilde P'(z) = P'(z-1) = z P(z-1) + 1 = z\tilde P(z) +1$, which is simpler. I don't know if it's in the literature, but it's slightly easier to read of some of the graph's information from my polynomial than yours. I've tried to clarify in the edit. – Owen Biesel Sep 23 '12 at 4:53
Well, I realized that I was being silly. Again thank you very much. – Spice the Bird Sep 23 '12 at 6:14

Since there seems to be some confusion in the comments below Richard Stanley's answer, and maybe also some discrepancy in terminology between Owen's answer and Richard's, I will record what I think is going on.

Vertices of rooted trees can be ordered by $x \lt y$ if $x$ is a descendant of $y$. The notion of subtree used by Owen looks as though he means upward closed subsets, since his subtrees include the root of the original tree (I apologize to Owen if that's not what he meant, although I think it is because that seems to be consistent with his remark on coefficients).

But that's not the usual notion of subtree, which according to Wikipedia is a (principal) downward closed subset of the original tree (i.e., if $y$ belongs to the subtree and $x$ is a descendant of $y$, then $x$ belongs to the subtree). Under that notion, Richard's answer made a lot more sense. Let me describe what I think the isomorphism types of his examples are using ZF sets. Let $a, b, c, d$ be ur-elements, and order sets by the transitive closure of the membership relation (so that $x \in y$ implies $x \lt y$). Then I can guess one of his trees looks like

$$\{ \{a, b, c\}, \{ \{ d \} \} \}$$

which has four one-node subtrees $a, b, c, d$, one two-node subtree $\{d\}$, one three-node subtree $\{\{ d \} \}$, one four-node subtree $\{a, b, c\}$, and one eight-node subtree which is the original tree (N.B. here, $n$-node subtree means there are $n$ vertices, including its root.) The other of his trees looks like

$$\{ \{a, \{ b \} \}, \{c, d \} \}$$

which has four one-node subtrees $a, b, c, d$, one two-node subtree $\{ b \}$, one three-node subtree $\{c, d \}$, one four-node subtree $\{a, \{ b \} \}$, and one eight-node subtree which is the original tree. (If those were not the isomorphism types he had in mind, then again I apologize.)

I don't believe however that these two trees have the same polynomial. If I did my arithmetic correctly, I believe they have different constant coefficients (one is 35 and the other is 36), using the original definition of the polynomial, not Owen's modification.

-
Thank you Todd. I suspected that we were all talking about different things. – Spice the Bird Sep 24 '12 at 15:38
Yes, thank you Todd. I didn't realize that (a) "subtree" is already standard terminology and (b) it doesn't mean what I thought it should mean. I'll clarify. – Owen Biesel Sep 24 '12 at 15:49

The number of different values taken by the polynomial is given by

1, 1, 2, 4, 9, 20, 47, 112, 274, 679, 1717, ...

Comparing with the sequence A000081 given by

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, ...

one can easily see that this is not at all a complete invariant.

-

My feeling is (or was) that it should not be an isomorphism invariant. But my attempt to find a counterexample suggests that perhaps it is (or that my quick and dirty programming had an error). Consider rooted trees where no vertex has out-degree greater than $2$. It is pretty quick work to generate them and find their polynomials (for a while). The number for depth (vertices in longest direct path) $2,3,4,5$ receptively are $2, 7, 56, 2212.$ Up to that far, the polynomials are unique. This seems to be (equal to) the number of rooted 3 trees suggesting that the next number is $2595782.$ That was too big for my quick Maple program.

-