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)

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

$\endgroup$
4
  • $\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$ Aug 25, 2018 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$ Jul 29, 2020 at 15:08
  • $\begingroup$ 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. $\endgroup$
    – George Lee
    Jan 26 at 15:09
  • $\begingroup$ @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. $\endgroup$
    – mgiroux
    Mar 4 at 18:36

1 Answer 1

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$
4
  • 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$ Jul 29, 2020 at 15:06
  • $\begingroup$ Wrong calculation. See the edit in the question for the correct calculation. $\endgroup$
    – George Lee
    Jan 26 at 15:00
  • $\begingroup$ @GeorgeLee I made the edit in 2021, and I commented on this post in 2018... I hope that clears things up. $\endgroup$
    – mgiroux
    Mar 4 at 18:17
  • $\begingroup$ @GeorgeLee Done! thanks for pointing it out. I don't come on here very often anymore $\endgroup$
    – mgiroux
    Mar 10 at 16:04

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.