Combinatorics is the study of possibilities.
So, you know, if you have a given set, how many subsets might it have?
Or if we have a given set, how can you arrange it in a line?
So I want to talk about these questions but I want to talk about them from a geometric point of view.
Let's do an example. So let's say, we have a set of 3 elements A, B, and C.
Now, I want to figure out, what are the possible subsets?
Usually the notation that we use is {} -> this one. But just to make it a little bit easier to read,
I am just going to add it like this -> abc
And so, a subset is just choosing some of these, and... and not others.
And so, I might chose for example: A, B, or C.
Or I might chose A and B. Or I might chose B and C.
Or I might chose A and C. I could choose all of them. Why not?
Or I could chose none of them -> ɸ
Now one point that I want to make is that we don't just want to count.
But, we do want to count. So if we were to just count how many subsets there are,
then here is the argument that we can do. I need to make 3 decisions.
Am going to put the element A in my subset, yes or no?
I am going to put my element B in the subset?
And I am gonna put my element C on the subset, yes or no?
So I got three decisions. And if for example:
I say I don't want to put A in, and I do wanna put B in, and I do want to put C in.
Then, that is going to determine uniquely one of these; in this case it's B and C.
This is kind of a different point of view so,
if instead of trying to choose the whole subset we just ask each element,
"OK, are you in? Are you out? Are you in? Or are you out?"
Then each element has two options, right? A has 2 options
B has 2 options, and C has 2 options.
And so, the number of possibilities is 2x2x2, which is 8.
This is true in general, that if I had a set of N elements, then each element has, "yes or no," "yes or no."
So I get 2^N possible subsets.
So that's kind of the plain combinatorial point of view.
But now what I want to do, is talk about little bit about how we can model this geometrically,
and see if we learn a little bit more not just about the subsets, but, you know, how we gonna make sure we got them all?
How they are related to each other? And so on. Before we go into this one,
let's go into a smaller example where it is a little bit easier to draw.
We're actually going to start at the set of 1 element--
Actually, just start with a set of 0 element.
So we have 1 subset because we only have 1 option which is to not do anything.
This is going to be my subset right here. This dot is going to be very important.
I know it doesn't look important, but you'll see it is important.
So now let's move to 1 element, and let's call it A.
So now our subsets are... well, we have two options. You either, "don't chose A," or you, "do chose A."
And so what I want to do now, is that I want to represent them like this.
This is where I, "don't chose A," and this is where I, "do choose A."
Bear with me, I am just going to draw a line between them.
For the 0 element case... so what I'm trying to do is to draw a picture,
where every dot corresponds to every subset.
And then we'll talk about the connections between them,
so that we know how they are really related to each other.
So to do the next one, where we have two elements. Let's say they're A and B.
I'm actually kind of getting tired of listing these subsets in on a line.
And I want to convince you that actually these subsets don't want to be on the line.
Does not... that's not really the shape they wanna make. They wanna make a different shape.
So I will try to convince you of that! Let's start with the subset that we have before, OK.
And one thing you'll notice that these are still subsets of my set.
The empty set is the subset of {A,B}. A is the subset of {A,B}.
But now there's some new subsets, which I'm going to put right here.
When I add a green line, that means then I take a subset and then I add B to it.
Let's do the green marker. I add B to my set, so I get AB.
And now my red marker is still going to mean that I add A.
So if I take B and I add A to it, I get AB.
Really I would argue that actually this is the shape that these subsets want to be in.
Let's do the next one. Lets try to do the same thing we did here, but now let's use a different order.
So if I have three elements A, B, and C, we get the same picture that I have here, because each one of these is still a subset of ABC,
and it's still connected in the same way; red means add A, green means add B.
You see what we are missing, right?
BRADY HARAN: You're missing C. FEDERICO ARDILA: We're missing C?
We need... we need to get C involved. C is not playing any role.
And I think I need a new color to put C in there.
So, if I go like this, that's going to mean I add C.
And of course I can do it for each one of these, and I'm going to get these new sets.
In this case I get AC.
In this case I get BC.
In this case I get ABC.
And this can follow the connections as before. So I use red to add A, I use red to add A,
And then with my green marker that means add B. You know what we get?
BRADY HARAN: You made a cube!
FEDERICO ARDILA: And so this is the thing. The subsets... I mean okay here when we... when we did this,
we listed them all, and we... you know, it's a fine list. It's complete.
But we totally missed an aspect that is very important, which is that actually,
these things don't want to be sitting in a line, they want to be sitting in a cube.
We count them by listing them and going, "1, 2, 3, 4, 5, 6, 7, 8."
And usually when we think about counting, kind of in everyday life,
we think of laying things in a row, and going, "1, 2, 3," and so on.
But if you look at this other method that we used, this is a very different kind of method,
where we actually were using the internal structure of these objects,
and let's try and let's think/see why it's 2 times 2 times 2.
Really what we're saying, in this argument is that: every time I add a new element to my set, the number of subsets doubles.
And this is something that becomes very clear visually.
Where I had one element, then I projected, and the number doubles.
Then I take these subsets, and now they double to become 4.
And these 4; they doubled to become 8.
And so now you see a pictorial representation of why these are doubling each time.
And then not only have we counted them, but we really have understood what is the kind of universal substance, and what that looks like.
The first time that I saw this, it was so clever. And so beautiful. And now when I think of the subsets,
I just think of a cube. And that's what I'm used to. I've been doing it for many years.
And this is the image in my head now.
You know, we walk around the world and then I see a table, and then I think, "well, the table..." it took humanity
many generations to figure out, that.. you know,
that tables are made of molecules, and the molecules are made of atoms.
Depending on what atom it is, or what the material is made of,
then you know is maybe more flexible... it's flexible, stronger or weaker.
BRADY HARAN: Okay, I'm going to give you nineteen elements, you know, in a set.
Tell me how many combinations there are.
You wouldn't sit there, in your head, and start creating this nineteen-dimensional object though.
You would... you would come... you would use this.
FEDERICO ARDILA: So, right. So, if I wanted to know the subsets of 19 are,
I definitely wouldn't use use this method of trying to list all of them.
Because, you know, that would take me impossibly long. When I think I'm done, I'm not sure I'm going to be sure if I'm done.
So really, the way that I would do it is just, you know... here I have a method for understanding why the number of subsets of 19 elements is 2x2x2 19 times,
And then it's 2^19. And then I figure out what that is.
I think more that what I would say is this geometric model is really a more detailed explanation for why this multiplicative formula holds.
BRADY HARAN: And since Mathematicians starting using this kind of technique, your way of thinking,
have they made new discoveries or reached new understandings because they see it this way?
FEDERICO ARDILA: That's a... that's a really great question.
And maybe what I will answer to that is... you know, let's... let's look at these pictures.
And... and let me follow exactly the question that you made earlier.
So here's 0 elements, 1 element, here's 2 elements, here's 3 elements.
And this doesn't stop here. It's... it's clear that I could keep doing this for any number of elements.
I think what we should be asking ourselves is what kind of realm I working into now?
For example, you see this and you immediately call it a cube.
How many dimensions to a cube have? We are used to saying that a cube is a 3 dimensional object.
If I look at the subsets of a 2 element set, then they form a square.
And... and a square is a 2 dimensional shape.
If I look at the subsets of a 1 element set, it's a line segment, and that's a 1 dimensional shape.
We're not used to talking about 0 dimensions, but... but a dot is a 0 dimensional shape.
And so here I'm going 0 dimensions, 1 dimension, 2 dimensions, 3 dimensions.
And then, this really shows me that the 4th dimension is going to appear very naturally here.
And I might be thinking here that I'm scared of 4 dimensions.
I might be thinking that I don't know how this goes.
But I can certainly just do the next step, and I think we should.
And we should find out what a 4 dimensional polytope looks like.
Let's say that I have now, the 4 element set.
And let's try to figure out, what are the subsets here?
So now what I am going to do is the same procedure that we did before.
I am going to want to add Ds. And so basically I am going to have to give this a new direction.
This picture is going to now kind of move over here, and include Ds also.
And before we do that I think we should go back and see... and just look at what happened over here.
Here we had the subsets of 0 elements. So this was 0 dimensional.
And now to move from here to here, we basically had 2 copies of this... of this picture.
One of them is here, one of them is here. And we connected it with an edge.
So we added a new direction, OK?
Now when we move in this direction, we basically are taking 2 copies of this one.
There's this copy, and this copy. And now we are adding a new dimension.
So now this is a line, and it becomes a 2 dimensional square.
Now here, I have a square. And now I really want to think that this is 3 dimensional,
in the sense that we are taking a square, and I am protruding it to a 3rd dimension.
So I am really taking a 2 dimensional picture, and I'm taking the bottom and top square, and connecting to make it a 3 dimensional picture.
And so that's the visualization that we want to think of here.
I have a now 3 dimensional thing, and it's... it's a cube.
And, this is the part that's going to be a little hard to imagine.
But, we are going to want to move it into the 4th dimension.
By taking a 3 dimensional cube here, a 3 dimensional cube some parallel universe, and connect them with a line.
So, I don't know about this parallel universe. I don't know what that looks like.
But I know how to draw another cube and make the connections.
In fact I'm going to...
We're going to make a 4th dimension. We're going to add a new direction telling me to add the Element D.
It's going to look like... this.
And this is green.
And this is red.
OK.
BRADY HARAN: That's a monster.
FEDERICO ARDILA: So that's... that's it.
So, this picture right here... is... you know, for one, is the illustration of subsets of a 4 elements set.
And we can see that there's 16 of them.
It also is maybe the first time you have seen a 4 dimensional shape.
This is a 4 dimensional figure.
Now, of course this is drawn on a piece of paper, so this is like the 2 dimensional shadow of a 4 dimensional object.
But then you can see, for example, how... for example in a 3 dimensional cube.
You can see that there's a lot of squares, right?
A 3 dimensional cube has 6 squares.
Corresponding to the 6 times that you get shapes like this.
If you look at this one carefully, we started by drawing one and two 2 dimensional cubes.
But if you look more carefully, you are going to find that there's many other cubes.
For example, here's another one with these two squares.
Here's another one with these two squares.
And really there's a bunch of different cubes that are living together.
And so then you start to see there's a lot of inherent structure here,
where there's you know, in this case, the 4 dimensional shape,
and then there's all these 3 dimensional pieces, and 2 dimensional pieces, which fit together into this... this nice shape.
This is exactly what geometrical combinatorics is about.
It's about kind of drawing the connections between geometry. And it's often geometry in very high dimensions.
And noticing that there's actually a lot of discrete structure behind there.
So for example, if you know about the regular solids.
Then, you know that there's the 3 dimensional regular solids.
And there's a few 4 dimensional, 5 dimensional, and so on.
They have a very rigid combinatorial structure.
And if you really want to understand those,
you also have to get into what is the combinatorics behind what is those discrete structures.
There's this beautiful dictionary that really teaches you about... both about these very old questions of,
"how do you count the subsets of a set?" Something as basic as that.
But then if you really just take that idea further, you end up finding... just landing into 4 dimensional space,
And figuring out how... how to walk around in that space.
BRADY HARAN: Are you going to draw a 5 dimensional one for us?
FEDERICO ARDILA: No. (laughs)
But I... you know I know, say I definitely would invite the viewers... with grid paper.
Which is what... you know it's tricky to this without grid paper.
But... but with grid paper, it's actually pretty simple to do.
You do... you take this shape, and you draw it, you know, you take it, you shift it over, and you make connections.
And that's the 5 dimensional shape.
And if you really have a lot of time on your hands, you could draw your 19 dimensional shape.
By taking it and protruding it, protruding it to 5, to 6, to 7, and so on.
Oh, we have got something very interesting.
Have we?
Yes. Look at this. We have--