# lower bound for Kruskal's weak tree function

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

• More than likely you are not wrong; I wouldn't be surprised if tree(3) were fairly large, say, larger than Graham's number even. Aug 25, 2018 at 1:00
• Well, at only 10^15, tree(3) is well short of G64. But it is a lot larger than Friedman's first estimate of "less than 100". Great job explaining the sequence construction so well. I can now sleep at night! Jul 29, 2020 at 15:08
• I don't understand why the first should not be embeddable in the second. You just added a node in the middle. What is it different from adding one after that like this: (((()()))()) and so on? But the bound of 262140 also suffers from this problem. Jan 26 at 15:09
• @GeorgeLee There's no way to map (()()()) into ((()())()) and preserve the least common ancestor of the left two nodes. You can map ((()())()) into (((()()))()) and preserve all the least common ancestors. This is what prevents you from creating arbitrary single chain "lengthenings " that would result in infinite sequences. Mar 4 at 18:36

I calcluate this new bound to be $3 \cdot 2^{49} - 2$, or 1,688,849,860,263,932.