5
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Simply Beautiful Art Aug 25 '18 at 1:00
  • 1
    $\begingroup$ 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! $\endgroup$ – Michael Tiemann Jul 29 '20 at 15:08
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ awesome :) kudos on doing the extra bit of calculation, appreciate the help! $\endgroup$ – mgiroux Aug 27 '18 at 13:33
  • 1
    $\begingroup$ Ever since I learned about TREE(3), tree(3) has been keeping me up at night. Thank you for finally sorting out this "missing link" in the explanation as to why it all grows so fast. $\endgroup$ – Michael Tiemann Jul 29 '20 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.