Timeline for Is the following invariant of rooted trees a complete invariant?
Current License: CC BY-SA 3.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| S Jan 13, 2014 at 21:00 | history | suggested | F. C. |
addition of the tag "trees"
|
|
| Jan 13, 2014 at 20:56 | review | Suggested edits | |||
| S Jan 13, 2014 at 21:00 | |||||
| Oct 23, 2012 at 16:47 | comment | added | Spice the Bird | I personally have no problem with you suggesting this problem to a grad student. Thank you for your input to the question. I had fun watching it happen. | |
| Oct 23, 2012 at 13:18 | comment | added | Patricia Hersh | I'm thinking about suggesting this question (about flag f-vectors, etc.) to a smart early grad student to take a look at, but wanted to check if anyone here was thinking about it already and still checking back here to these comments. I realize that Spice mentioned something about having resolved his or her related question about prod-simplicial complexes, but was guessing that might not be exactly this question about flag f-vectors and multivariate polynomials summing over nested trees. Thanks, Spice, for starting an interesting discussion here. | |
| Sep 29, 2012 at 12:50 | comment | added | Patricia Hersh | I was just speculating that the flag $f$-vector of a prod-simplicial complex should contain the same data as the polynomial where you sum over nestings $T_1 \subseteq T_2 \subseteq\dots $ of rooted trees with monomials $x_1^{|T_1|}x_2^{|T_2|}\cdots $ as summands. It seems like a nice question from various viewpoints to try to prove that these are equivalent data (if it's true) and that they determine the rooted tree. Right now I don't have time to think about this, but might at some point. Or it would seem like e.g. Owen would be in a great position to figure this out if he's interested. | |
| Sep 28, 2012 at 18:41 | answer | added | F. C. | timeline score: 3 | |
| Sep 27, 2012 at 19:56 | vote | accept | Spice the Bird | ||
| Sep 27, 2012 at 19:56 | vote | accept | Spice the Bird | ||
| Sep 27, 2012 at 19:56 | |||||
| Sep 27, 2012 at 17:29 | comment | added | Spice the Bird | @Patricia, This question is indeed inspired by my earlier one. I have since found an approach that does not require the this polynomial to be a complete invariant. This took on a question of a life of it's own. | |
| Sep 27, 2012 at 11:51 | comment | added | Todd Trimble | @Hans: "invariant" here means the polynomial is well-defined, independently of which operations were used to put the tree together. Or, if two trees are isomorphic, then they have the same polynomial. StB was asking about the converse of the last sentence, which says the invariant is complete. (Compare soundness and completeness for systems of logic.) | |
| Sep 27, 2012 at 3:07 | comment | added | Patricia Hersh | By the way, the flag $f$-vector does distinguish the two trees in Jeremy's example, by comparing number of subtrees with 2 nonroot nodes contained in subtrees with 3 nonroot nodes contained in subtrees with 4 nonroot nodes. The first tree gives 8 while the second one gives 9. | |
| Sep 27, 2012 at 1:07 | comment | added | Patricia Hersh | Was this question inspired by your question about regular cell complexes and trees? I was intrigued by that question. I gather $P_T$ is calculating the number of cells of each dimension in your other cell complexes? You could also try the flag f-vector to further separate things there. For each possible list of dimensions $d_1 < \cdots < d_j$, the flag $f$-vector has a coordinate counting lists of cells of these proscribed dimensions each of which is contained in the closure of the next. I've been trying to find a specialization to satisfy the $f_p$ recurrences Jeremy mentions. | |
| Sep 26, 2012 at 21:00 | comment | added | Hans-Peter Stricker | @StB: Please help me to understand: You say "this polynomial is an isomorphism invariant of rooted trees" and ask "if PT=PT′, are the rooted trees T,T" isomorphic"? Isn't the latter a definition of being an isomorphism invariant? What do I miss? | |
| Sep 26, 2012 at 19:32 | comment | added | Jeremy Martin | Also, to confirm Tricia's comment above: whether a tree is determined by its CSF is still open AFAIK, and seems to be a very hard problem. | |
| Sep 26, 2012 at 19:31 | answer | added | Jeremy Martin | timeline score: 17 | |
| Sep 26, 2012 at 19:28 | comment | added | Jeremy Martin | The proof that the subtree polynomial is not as strong as the chromatic symmetric function is actually due not to Morin, Wagner and myself, but to Eisenstat and Gordon (Discrete Math. 306 (2006) 827-830); they construct a pair of 11-vertex trees with the same subtree polynomial but different CSFs. | |
| Sep 26, 2012 at 16:24 | comment | added | Spice the Bird | Thank you. I was sort of curious about what one would gets if we started with an unrooted trees and summed over the possible roots. | |
| Sep 26, 2012 at 14:48 | comment | added | Patricia Hersh | Latex is being annoying -- $S_T'(q,1)$ is supposed to be the usual derivative of $S_T$ with respect to $q$. | |
| Sep 26, 2012 at 14:47 | comment | added | Patricia Hersh | By the way, here is the relationship to the polynomial $S_T$ that I mentioned before: if you take unrooted tree $T$ and sum over all possible choices of root $r\in T$, then $S_T′(q,1)=\sum_{r\in T}(\tilde{P}_{T,r}(q)−1)$ where $\tilde{P}$ is Owen's polynomial. Recall from [MMW], $S_T(q,t):=\sum q^{|S|}t^{|L(S)|}$ where the sum is over "subtrees" having at least one edge (here defined as subgraphs that are trees), $S$ is the set of vertices in such a subtree, and $L(S)$ is the set of edges to leaves in the subtree. So I guess your rooted version may well be better at tree recovery | |
| Sep 24, 2012 at 16:52 | comment | added | Spice the Bird | The linear tree with n nodes (n+1 vertices, one of them the root) has polynomial $((z+1)^{(n+1)}−1)/(z)$. So no | |
| Sep 24, 2012 at 15:28 | answer | added | Todd Trimble | timeline score: 6 | |
| Sep 24, 2012 at 13:19 | comment | added | Patricia Hersh | 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? | |
| Sep 24, 2012 at 10:34 | answer | added | Aaron Meyerowitz | timeline score: 2 | |
| Sep 23, 2012 at 23:35 | history | edited | Mariano Suárez-Álvarez | CC BY-SA 3.0 |
edited title
|
| Sep 23, 2012 at 20:00 | vote | accept | Spice the Bird | ||
| Sep 23, 2012 at 20:15 | |||||
| Sep 23, 2012 at 19:58 | comment | added | Spice the Bird | Thank you for the addition of the tag. It could only help the question. | |
| Sep 23, 2012 at 16:07 | comment | added | Patricia Hersh | Hope you don't mind the new tag I just added. People in enumerative combinatorics definitely work on questions of this flavor. | |
| Sep 23, 2012 at 16:04 | history | edited | Patricia Hersh |
edited tags
|
|
| Sep 23, 2012 at 15:23 | comment | added | Patricia Hersh | 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. | |
| Sep 22, 2012 at 22:22 | answer | added | Owen Biesel | timeline score: 10 | |
| Sep 22, 2012 at 20:45 | history | asked | Spice the Bird | CC BY-SA 3.0 |