5
$\begingroup$

I was just introduced to the TREE() function, by a 2017 Numberphile video.

In it, Tony Padilla explains a simplified version of the calculation of the TREE function: We are building a forests with as many trees as we can, following certain rules. Each tree in the nth forest can't have more than n nodes, and each tree in a forest may not "contain" an earlier tree from the same forest (i.e. it can't be "inf-embeddable"). The maximum number of trees in a forest is TREE(n).

On the way to explaining that TREE(3) is very large, he computes the size of TREE(2) as 3, giving this sequence for the forest (where G is a green node, and R is a red node):

  1. G
  2. R-R
  3. R

However, following the rules as best I can, I can do better:

  1. G-G
  2. R-R
  3. R-G
  4. G-R
  5. G
  6. R

Now, both Padilla and Wikipedia tell me that TREE(2) = 3, while I have only just learnt about the subject, so I know I am wrong - I just don't know why.

Is the explanation in the video over-simplified and I am being misled over the meaning of inf-embeddable? Was there a rule clearly explained in the video that I foolishly misunderstood? Where did I make a misstep?

$\endgroup$
0

1 Answer 1

7
$\begingroup$

The first tree in the sequence is only allowed to have at most one node, so your "1. G-G" is invalid.

$\endgroup$
1
  • 5
    $\begingroup$ Ah, so when I said "Each tree in the nth forest can't have more than n nodes", it should have been "The nth tree in each forest can't have more than n nodes." Got it. Thanks. $\endgroup$ Oct 10, 2018 at 14:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .