Timeline for Lower bound on the number of "short" paths in a rooted tree with polynomial size
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2010 at 8:14 | vote | accept | Marc Bury | ||
| Dec 14, 2010 at 22:56 | answer | added | Peter Shor | timeline score: 9 | |
| Dec 14, 2010 at 21:37 | comment | added | Marc Bury | The size of $T$ is the number of nodes, i.e. internal + leaf nodes. | |
| Dec 14, 2010 at 21:31 | comment | added | Oleksandr Bondarenko | @Marc: By the size of $T$ you mean the number of internal nodes or something else? | |
| Dec 14, 2010 at 21:20 | comment | added | Kaveh | +1: I saw your comment about the motivation, thanks. (I removed my comment after reading Peter's.) | |
| Dec 14, 2010 at 20:58 | history | edited | Marc Bury | CC BY-SA 2.5 |
added 66 characters in body; deleted 1 characters in body
|
| Dec 14, 2010 at 20:41 | comment | added | Marc Bury | This is a good question. It is allowed but this is not the interesting case :) Then we should make a lower bound on the number of branching nodes in the tree, e.g. $\omega(\log n)$ branching nodes. | |
| Dec 14, 2010 at 20:14 | comment | added | Peter Shor | What about the tree that has just one path (and $n$ nodes)? Is that allowed? | |
| Dec 14, 2010 at 20:07 | comment | added | Marc Bury | I edit the question and try to make it more precise. | |
| Dec 14, 2010 at 20:06 | history | edited | Marc Bury | CC BY-SA 2.5 |
added 94 characters in body
|
| Dec 14, 2010 at 19:58 | comment | added | Oleksandr Bondarenko | @Marc: Could you, please, make more precise your statement "two paths are different iff they use different child nodes in a branching node". You mean they're different if there is such a branching node where they use different child nodes? | |
| Dec 14, 2010 at 19:46 | comment | added | Oleksandr Bondarenko | @Marc: The letter $T$ (5th line) is obviously from ``too much nodes in" (7th line)? | |
| Dec 14, 2010 at 19:36 | history | asked | Marc Bury | CC BY-SA 2.5 |