Is the following invariant of rooted trees a complete invariant? - MathOverflow

Is the following invariant of rooted trees a complete invariant?

2012-09-22T20:45:47Z

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.

Answer by Owen Biesel for Is the following invariant of rooted trees a complete invariant?

2012-09-22T22:22:21Z

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$.

Answer by Aaron Meyerowitz for Is the following invariant of rooted trees a complete invariant?

2012-09-24T10:34:09Z

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.

Answer by Todd Trimble for Is the following invariant of rooted trees a complete invariant?

2012-09-24T15:28:17Z

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.

Answer by Jeremy Martin for Is the following invariant of rooted trees a complete invariant?

2012-09-26T19:31:45Z

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.

Update: I think the answer to your original question is no.

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.)

Answer by F. C. for Is the following invariant of rooted trees a complete invariant?

2012-09-28T18:41:49Z

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.