Is the following invariant of rooted trees a complete invariant? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T05:23:07Z http://mathoverflow.net/feeds/question/107863 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107863/is-the-following-invariant-of-rooted-trees-a-complete-invariant Is the following invariant of rooted trees a complete invariant? Spice the Bird 2012-09-22T20:45:47Z 2012-09-28T18:41:49Z <p>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".</p> <p>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. </p> <blockquote> <p>If the number of edges of $T$ is zero, then $P_T(z)=1$.</p> <p>If $T'$ is the leafing of $T$, then $P_{T'}(z)=(z+1)P(z)+1$.</p> <p>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)$. </p> </blockquote> <p>This polynomial is an isomorphism invariant of rooted trees. My question is </p> <blockquote> <p>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.</p> </blockquote> http://mathoverflow.net/questions/107863/is-the-following-invariant-of-rooted-trees-a-complete-invariant/107868#107868 Answer by Owen Biesel for Is the following invariant of rooted trees a complete invariant? Owen Biesel 2012-09-22T22:22:21Z 2012-09-24T15:54:34Z <p>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.</p> <p>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.</p> <p>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 <strong>the coefficient of $z^n$ in $\tilde P_T(z)$ is the number of $n$-node subtrees of $T$.</strong> 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$. </p> <p>Some consequences include:</p> <ul> <li>If $T$ has $n$ nodes (vertices other than the root), then the highest-order term of $\tilde P_T(z)$ is $z^n$.</li> <li>The coefficient of $z$ in $\tilde P_T(z)$ is the degree of the root of $T$.</li> <li>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$.</li> <li>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).</li> </ul> <p>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.</p> <p><strong>Edit</strong>: 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'$.</p> <p>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.</p> <p>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.</p> <p>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 &lt; 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&lt; 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 &lt; 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.</p> <p>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.</p> <p><strong>For example:</strong> 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$.</p> http://mathoverflow.net/questions/107863/is-the-following-invariant-of-rooted-trees-a-complete-invariant/107967#107967 Answer by Aaron Meyerowitz for Is the following invariant of rooted trees a complete invariant? Aaron Meyerowitz 2012-09-24T10:34:09Z 2012-09-24T10:34:09Z <p>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 <a href="http://oeis.org/A002658" rel="nofollow">rooted 3 trees</a> suggesting that the next number is $2595782.$ That was too big for my quick Maple program.</p> http://mathoverflow.net/questions/107863/is-the-following-invariant-of-rooted-trees-a-complete-invariant/107986#107986 Answer by Todd Trimble for Is the following invariant of rooted trees a complete invariant? Todd Trimble 2012-09-24T15:28:17Z 2012-09-24T15:28:17Z <p>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. </p> <p>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 <em>upward closed</em> 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). </p> <p>But that's not the usual notion of subtree, which <a href="http://en.wikipedia.org/wiki/Subtree#Terminology" rel="nofollow">according to Wikipedia</a> is a (principal) <em>downward closed</em> 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 </p> <p>$$\{ \{a, b, c\}, \{ \{ d \} \} \}$$ </p> <p>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, <em>including its root</em>.) The other of his trees looks like </p> <p>$$\{ \{a, \{ b \} \}, \{c, d \} \}$$ </p> <p>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.) </p> <p>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. </p> http://mathoverflow.net/questions/107863/is-the-following-invariant-of-rooted-trees-a-complete-invariant/108190#108190 Answer by Jeremy Martin for Is the following invariant of rooted trees a complete invariant? Jeremy Martin 2012-09-26T19:31:45Z 2012-09-26T20:12:15Z <p>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.</p> <p>Update: I think the answer to your original question is no.</p> <p>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)$$</p> <p>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).$</p> <p>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.)</p> http://mathoverflow.net/questions/107863/is-the-following-invariant-of-rooted-trees-a-complete-invariant/108370#108370 Answer by F. C. for Is the following invariant of rooted trees a complete invariant? F. C. 2012-09-28T18:41:49Z 2012-09-28T18:41:49Z <p>The number of different values taken by the polynomial is given by</p> <p>1, 1, 2, 4, 9, 20, 47, 112, 274, 679, 1717, ...</p> <p>Comparing with the sequence <a href="http://oeis.org/A000081" rel="nofollow">A000081</a> given by</p> <p>1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, ...</p> <p>one can easily see that this is not at all a complete invariant.</p>