>>BRADY HARAN: I think most Numberphiles are fascinated by the idea of Graham’s number, which is supposedly unimaginably big – but what actually is it? What does it count? Well, I think the best person to explain that is none other than the world famous mathematician himself, Ron Graham.>>RON GRAHAM: Suppose you took four vertices of a square – and, this is two dimensons, so it has how many vertices? Two squared (four vertices). Now, what I’m going to do is take these four vertices, and put – two more edges connecting all possible pairs of these vertices. Now how many possible edges would you be able to draw? Well, there’s something called a binomial coefficient, and there are four vertices, and you choose two of them, and this turns out to be six. So you see there are six edges here – all the ways you could join these four dots. And now, what we’re going to do – is – take the four dots again and look at each one of these possible six lines and color them red or blue in any way that you like, so for example – I might color this one red, and maybe this one red, and then I’d say, well ok, maybe I’ll color this one blue, and this one blue, and this one blue, and this one blue. Ok, so that’s one way, and you might say, well, okay, so what? I’m looking for certain special configurations – and, I’m not going to find it here in a square because this is too small; we need more dimensions. What about three dimensions? Well, what does a three-dimensional cube look like? Well, I can’t really draw it on a piece of paper, but you can kind of draw a version of it, namely, if you take your four vertices that form your square and then you kind of move it a little bit, well, that’s a picture you might recognize, how many vertices on these corner points here? Well, you can see there are eight, which is two cubed. So the three-dimensonal cube has – two cubed – eight vertices. 28 possible line segments. And if you color them, say, this one’s red, and this one’s red, and this one’s red, and that one’s red, but – you know – a lot of the others are blue, and what you’re trying to do is do it in a way that avoids something. Now, what is this thing you’re trying to avoid? That’s the whole point. You’re trying to avoid the following configuration: namely, four points in here someplace and all the six line segments have the same color (in this case it’s red) and, furthermore, these four points lie in a flat plane. They don’t stick up in three dimensions. Usually, if you took four points, you’d have three dimensions. It kind of spans a three-dimensional volume. Here, I want four points to be flat, and they form a square, and all six line segments are the same color. In three dimensions, you definitely can avoid such a configuration, because this only seems to happen on, just kind of the faces. And what you have to do – your challenge – is to go in a much larger dimension. And what do you mean by a cube – in say – four dimensions? Well, in four dimensions, you could take this picture, and translate it, and join the lines, but it gets kind of messy, but yeah. I’m not afraid; I think I can do that. Let’s see. Here’s a three-dimensional cube, and now I have to shift it, okay, well, I’ve gotta be a little careful here – and now I join the corresponding things. Well, you can see it’s going to be, as we can call it, a tesseract. Now how many different ways can you color these 120 different lines with red and blue? Well, with each one of them, there are two choices. So, it’s two times two times two times two 120 times, or 2 to the 120 (2^120). Already beyond what computers can do, and no computer can do 2^120 things right now. But the problem we’re trying to avoid having these four points that form a square lie in a plane and have all six line segments the same color and in four dimensions, you can do it. Not too hard to do. Well, what about the five-dimensional cube? In five you can avoid it, six – it takes more work, seven – yes, it takes a lot more work, the question is, can you always avoid it? The answer: no. If the dimension is large enough, you cannot avoid it. No matter how hard you try to color it, you can’t avoid it. And when is that dimension finally reached? Well, you know it’s reached by the time you get to a very large number, sometimes known as Graham’s number, a pretty big number, and you know for sure, in that dimension, you cannot avoid it. And the proof that you can’t avoid it is pretty complicated, pretty recursive, and that’s what causes this number to be so large. Now, you might say, well, what’s the truth? Sure, if you go as far as Graham’s number, in that dimension, you can’t avoid it, but maybe you can make it unavoidable in a smaller dimension. And it turns out that it appears that already in thirteen dimensions you can’t avoid it. Now, how could you check that by computer? Well, okay, no problem really, in thirteen dimensions, so “n” is thirteen dimensions, so how many vertices in your thirteen-dimensional cube? Well, 2^13 vertices, which is, what, that’s about 8192. Okay, a little over eight thousand vertices. Well, how many line segments? Well, 8192 times 8191 over two – you have to check – no matter how you color them with red or blue – you’ll make one of these things. Well, it’s uncheckable. You can’t check that; it’s impossible. You need to think! You can’t just compute. Right now, we don’t know. It’s between 13 – we know, maybe – uh, 12 is not enough, it turns out, and this other, slightly bigger number, which uh – I can – I can try to write it,>>BRADY HARAN: So there we go. As cubes move up the dimensions, from three dimensions, that I think we all understand, to four dimensions, to five – eventually we reach a number of dimensions in which one of these configurations must exist. And the upper bound on that, the point where it has to happen by, is this “Graham’s number”. Now, we know this number is unimaginably big, it was even in the Guinness Book of Records. But just how big is it? Well that deserves a video all of its own, and again, we’ve got Ron Graham to explain it. The links are on the screen here, I’ve also put them in the description under the video. So, why don’t you check it out? It’s a pretty big number.