# The Enormous TREE(3) – Numberphile

0
37

TONY PADILLA: A very very big number, a super super big number. In fact, it’s just an off-the-scale big number, and that’s TREE(3). It absolutely puts Graham’s Number to shame. I mean, really Graham’s Number is effectively zero compared to TREE(3). Let’s explain where TREE(3) comes from. Well, It comes from a game of trees. There are three different types of seeds. We’re gonna have a green seed…

Mathematicians wouldn’t call these seeds, they’d call them nodes, but we’ll call them seeds. Okay, and a black seed, and a red seed. And what we’re gonna try and do is we’re gonna try to build a forest. Okay, one tree at a time. The first tree can’t have more than one seed. The second tree can’t have more than two seeds. The third tree can’t have more than three seeds and so on, okay? And that’s rule number one.

The other rule is that if you build a tree, if you find that an earlier tree could’ve been contained within that tree, the whole forest dies. Okay? So let’s just sort of illustrate what we mean, so let’s try and build a tree for example, so we might start off with, you know, a green seed… And then we branch up and we get a black seed… And then maybe we have two branches… And there, you know we can have another green seed maybe… And we can sort of draw these trees, right? We said that the first go, the first tree, shouldn’t have more than one seed, the second tree shouldn’t have more than two seeds, and so on. We also said if you build a tree, then an earlier tree could’ve been contained within it, then the forest dies, so what do we mean by contained? Well the mathematical term that we’re really talking about here is inf-embeddable.

Don’t worry about what inf-embeddable is, let’s just try to understand what we mean by one tree being contained in another tree. Okay, so let me show you. We’ve got a tree here already, so we could draw another tree. For example, we could draw… this tree. And I think you’d be quite happy if you said that this tree was contained in this tree because you can sort of see you’ve got that there, and you’ve got that there, and you’ve got that there, so that tree is kinda contained in that tree. There’s something else that you have to- when you say a tree is contained in another, there’s an important property that they have to satisfy. And that’s that they must preserve the nearest common ancestor, so what do I mean by that? I mean this red seed, and this green seed, their nearest common ancestor is this black seed. And that same’s true here.

This red seed, this green seed, their nearest common ancestor is this black seed. So indeed, this tree is contained in this tree. Okay, let’s do another example. Is this tree contained in this tree? At some level you might think that it is. Green, green, red. Green, green, red. So you might think that this tree is indeed contained in this tree. But it’s not. And the reason it’s not is because of the nearest common ancestor. This red and this green, their nearest common ancestor is a green. It’s this green one here. This red and this green, their nearest common ancestor is this black.

So this tree is not contained in this tree. I want to do one last example, just so we get this point properly understood. So let me draw my new tree… Okay, so I’ve got two trees here, this one and this one. I want to ask: Is this one contained in this one? All right, now, it doesn’t look obvious that it is, but actually, it is. You could take this guy, you could take this guy, and you could take this guy, okay? That’s your black-black-red, black-black-red, and also they preserve the ancestry rule. Because the nearest common ancestor of this black, and this red is… the black.

BRADY: The nearest COMMON ancestor. TONY: Yes, the nearest COMMON ancestor. So even though they have other ancestors, the nearest common ancestor is this black guy, right? And that’s what’s important. And this is shared by the other graph and so, we can say that this graph is contained in this one. Okay, those the rules, are we happy with the rules? BRADY: I think so. TONY: First rule is: tree number one shouldn’t have more than one seed, tree number two shouldn’t have more than two seeds, tree number three shouldn’t have more than three seeds. We’re going to make a forest of trees and the minute we write down a tree that contains an earlier tree, forest dies. So let’s first play the game with only one type of seed. Let’s say it’s the green seed. Well the first tree has to have one seed, at most, so I’m gonna just do it, right? BRADY: Yup.

TONY: Okay, that’s it. Can I write down anything else? There’s no way I can- the next- I’m stopped, I have to stop now, right? Clearly, if I could draw this tree for example… Alright, but clearly this is contained in this. So this has to stop at one. That tells me that TREE(1) is one. Okay? So this game stops at one. Now let’s do it with two. I’m gonna use green and red, okay? Okay, so tree number one. Doesn’t matter; it’s gonna have to be out of the red or the green, doesn’t make any difference. I’ll choose the green. Okay, next one! What am I gonna do next? Well, I definitely can’t draw say, you know, two greens or something like that. I could do this. I could write down another red, just a red seed like that. But what could I draw next? Well, anything I draw next is gonna have to contain either the green seed or the red seed, so it’s going to contain- so, let me just draw an example down, so something like this. So whatever happens, you know, I’m gonna be able to contain one of these guys in this next one.

This game is stopped at two. Could I have gone any further than two, though, is that the longest game I could have played? It’s not. There is a longer game you could have played. Let’s play it. Okay, so I start off with my green seed. Then, if I’ve drawn two red seeds Okay, that’s fine. I think that- can I carry on? Yes. I can, I can draw a red seed. Because remember, the rule is: you can’t- if you draw down a tree that contains an EARLIER tree, that’s not allowed. But this tree doesn’t contain either of these two, okay? So I’ve actually managed to make this game last three trees. And actually I can’t go any further. So that tells me that TREE(2) is three. So what this tree thing is telling us is the length of the longest game that you could play this way. So now, Brady, have you got a bit of time on your hands? Now we’re gonna use three different types of seeds, three different colors: red, black, and green, okay? Well, what’s the longest game we could play? Well, you could start off with a green. You could maybe do this red, if you wanted to, you know… Uhhh… What else could you do? You could do this guy, I suppose, something like this. I mean, there’s all sorts you could start to write down… I mean you can go on and on and on, right? What’s the longest game you could play? The longest game you could play is TREE(3). It’s the answer.