Timeline for How large is TREE(3)?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jul 30, 2012 at 18:10 | comment | added | Deedlit | You actually have it reversed with regard to more stringent versus less stringent. The less stringent definition of $T_i < T_j$ will mean fewer sequences satisfy the requirement, so if we define SUBTREE(n) as the longest possible sequence using this less stringent definition, SUBTREE(n) will exist and SUBTREE(n) <= TREE(n). It's an interesting question as to what the growth rate of SUBTREE(n) is. Regarding the two versions of n(k), the substring definition is more stringent, and that version of n(k) is infinite for k >= 3. | |
| Jul 30, 2012 at 18:02 | comment | added | Deedlit | Thanks for your comments, r.e.s. I believe you misread what I wrote; I meant that every tree in the initial part of the sequence had at least one 2 label or 3 label, not that it consisted solely of 2 and 3 labels. This is of course enough to imply that no tree in the initial part will be homeomorphically embeddable into a tree in the later part with solely 1 labels. Very nice construction of N. One can do even better; I can prove that TREE(3) > tree(tree(tree(6))), and tree(tree(6)) will certainly be much greater than your N. | |
| Jul 18, 2012 at 15:16 | history | edited | r.e.s. | CC BY-SA 3.0 |
"TREE(3)" should be "lower bound on TREE(3)"; improve wording & notations
|
| Jul 15, 2012 at 2:16 | history | edited | r.e.s. | CC BY-SA 3.0 |
add link to a sketch of the example
|
| Jul 11, 2012 at 20:50 | history | edited | r.e.s. | CC BY-SA 3.0 |
switch to mathjax formatting
|
| Jul 11, 2012 at 19:46 | history | edited | r.e.s. | CC BY-SA 3.0 |
mention an even larger result; deleted 14 characters in body
|
| Jul 11, 2012 at 17:40 | history | answered | r.e.s. | CC BY-SA 3.0 |