The wiki on Kruskal's tree theorum briefly mentions the weak tree function regarding unlabeled trees. It gives values of tree(1) = 2, tree(2) = 5 (trivial to prove) but then it gives tree(3) >= 262140. This is a very specific bound which makes me think the actual number must hover close to this range. The problem is, when I write out the sequence for tree(3), I get a number in excess of a quadrillion (10^15).
My sequence goes as follows (using bracket notation where nesting implies parenthood, and left number = max nodes)
4 (()()())
5 ((()())())
6 ((((()()))))
7 ((((())(()))))
from here, we have a leg coming from two nodes. The technique to eliminate the legs involves subtracting a right leg, and then incrementing the left leg to the max number of allowed nodes, then sequentially removing the left legs until it matches the right, then repeating until both legs are gone. The equation for removing a two leg of arbitrary length is
3/2 * (2^(x + 2)) – 2*x – 6
the last step had a two leg of length 1 which requires 4 steps to remove
11 (((()())))
12 (((4)(4))) —4 nodes deep –> (((())))
using the above equation we get 82 steps to remove a two leg of length 4
94 ((()()))
95 ((46)(46)) removing a two leg of length 46 = aprox 2^48 steps
(2^48 + 95 = aprox 2^48)
2^48 (()())
the only option we have from here is a single leg with 2^48 nodes
which can be whittled down in 2^48 steps yielding a total of 2^49 steps or roughly 10^15
Am I missing something? the only way I can see this not working, is if the first tree in the sequence (()()()) embeds into the second ((()())()). I don't think it does, because the lowest common ancestor of the left two lowest nodes is not the root. Perhaps someone who knows more about inf preserving and homeomorphic embeddability can tell me if this is truly a new lower bound or if I made a mistake (the more likely answer)
EDIT I noticed this lower bound is now posted on Wikipedia, and someone has taken the time to do the exact calculation. Just so this is reflected in the original source, I will add it here as well. Above, I approximated after 2^48, but the exact number of steps to remove the legs from 95 ((46)(46)) is 3/2 * 2^(46+2) – 2*46 – 6 = 422,212,465,065,886. The next step we will increment by one and add 95 from the previous step bringing us to 422,212,465,065,981. Our last sequence is a single chain of nodes which can be removed in n-1 steps. 422,212,465,065,981 * 2 – 1 = 844,424,930,131,963. Finally we subtract 3, as the sequence started at 4 nodes to get 844,424,930,131,960 — Mark Giroux
Best Answer
It appears that you are using ordered trees (sometimes called structured trees) in your construction. Both tree(n) and TREE(n) are defined using unordered trees, where all children can be swapped arbitrarily. So for example the trees ((())()) and (()(())) are considered isomorphic, and they both can be homeomorphically embedded into (((()))()).If we define otree(n) to be the same as tree(n) except using ordered trees, then otree(3) is indeed a fairly large number, larger than Graham's number.Forget the above, I misunderstood the construction a little bit; your sequence appears to be correct, and improves the current known lower bound. Kudos!
I calcluate this new bound to be $3 \cdot 2^{49} - 2$, or 1,688,849,860,263,932.