[MUSIC] Hello, welcome to our video course on discrete mathematics. The topic of today will again be orderings, in this lecture we'll actually prove an algorithm theorem and all to see an interesting application. So as a quick review, what do we see here is an ordering on a finite set. To be more precise, it's the Hazi diagram of this ordering which we defined last week. We have also seen two important concept of chain and anti-chain. So for example, this is a chain, it's a set of PYs comparable vertices. And actually, what I draw here is a chain of maximum size. So this is what I want to define to be the height of our ordered set. It's the size of the largest chain. Similarly, I define the width. To be the size of the largest anti-chain. So in this example, the anti-chains are not very exciting. So you can see every anti-chain has size at most, two. So here the width is two, and the height is actually one, two, three, four, five, six. It's six. Let's look at another example here. Again, we have an order set, and the largest chain should be something like this. So the height here is three, and the width is a little bit larger. So the largest anti-chain, should be this in the middle. Four, five, six, seven, eight. So the width of S is eight. All right. So this defines the height and the width of an ordering. And now we're ready for the theorem of today, which is called Mirsky's theorem. It tells you the height of S is the minimum t that you can partition your set into t anti-chains. So as a picture, it basically means this is your set S, you somewhat partition it into anti-chains And somehow, if you manage, this time it's one, two, three, four, five, six. If you manage to partition it into six anti-chains, then no chain will be larger than six, and actually these two numbers meet. So you can find a chain of some size, and an anti-chain covering of the same size. So the proof consists of two parts. First, let's do the simpler half, let's prove that the height is at most t. So, let's take an anti-chain partition, this is A2 and one A2. This is At, and so on. And we have seen in last lecture that if we have a chain and an anti-chain, they can intersect in at most one element. Right, so if you have a chain, it can have most one element in each of these levels. And therefor, it's immediate that you cannot have more than t elements in the chain. So this proves the upper bound. So this was easy. For the lower bound namely that the height is at least t, you must do the following. We must find a partition of S into anti-chains. And we must find a chain t, a chain C of size at least t. So this is what we have to do to prove the lower bound. And how are we going to prove that? Well, it's actually not that difficult. Let's draw our set S, so this is S. And here is a kind of obvious choice for an anti-chain partition. We start with a minimal elements. So A1 is the minimal elements of S. In this, we have seen last week this forms in fact an anti-chain. So now, what is A2, well, A2 is the minimal elements of whatever is left. So formally, A2 is the minimal elements of S minus A1. So, we can work all the way up. Let's say this is Ai, how do we define Ai plus 1? Ai plus 1 is the minimal elements of S when I remove everything below it. So I remove the elements A1 until Ai, and whatever is left, I take the minimal element of this, and this is A1. So in every step, we remove at least one element. And therefore, this process terminates with a set At. Good. So this is our anti-chain partition. So now, what we have to do, we have to find a chain that actually has t elements. So here is a lamma. For all elements x in anti-chain Ai plus one. So let's say x is here, there exists an element y, one level below such that x is smaller, no, other way around. Such that y is smaller than x. So something like this. The proof is very simple. Well, if none such y existed, so, otherwise, x would already be minimal. In the set S minus A1 up to Ai minus 1. And we would put x into Ai, and into Ai plus 1. So this is a contradiction, and therefore we can be sure we find some element that is smaller than y, right? And this almost finishes the proof because now, we can take any element in At, we find an element smaller in At minus 1, and so on. Until we are down here, right? And this is your chain of size t. And that concludes the proof. So now again, let's look a little bit more in depths at Mirsky's Theorem. Here's one way to state it. The maximum size of the chain is the minimum size of an anti-chain partition. In its theorem of this kind, we can say the max of something equals to the min of something is called a min-max theorem. So every time we discover a min-max theorem, you should rejoice because these are kind of the highlights of discrete mathematics. We'll see in the course of this lecture, we'll see many more min-max theorems. Here's another way to formulate Minsky's theorem in a more logical way. You can say, S can be partitioned into t anti-chains if and only if every chain has size at most t. So note that the only if part is very easy and the if part required a little bit more work. So we can say the obvious, necessary condition is also sufficient. And this provides a nice nickname for theorems like this. TONCAS. This is just an acronym. The obvious necessary condition is also sufficient. So Mirsky's theorem is an example of a TONCAS. Another thing, on the left side here, we have chains, and on the right side we have anti-chain partitions. So know what happens if you switch these two terms. You ask yourself, is the max size of an anti-chain equal to the minimum size of a chain partition? Is this statement still true? And it turns out, yes, it is still true. It has another name. It's called Dilworth's theorem. Today we can prove one half of the Dilworth's theorem, which is this inequality. So if you have an anti-chain and a chain partition, your anti-chain must be smaller. It must be at most the size of the chain partition. So the proof is very similar to the first half of Mirsky's theorem. If this is your set S and you have a chain partition, something like this, this is C1. Then here is your chain C2, this is C3, C4, and so on. And you have an anti-chain A, then we also know A intersects Ci is at most 1. So, again, our anti-chain can have, at most, one element in each chain, and therefore, A is at most t. So this proves the first half of Dilworth's theorem. Now, the other half, for the other half, we would have to find a chain partition. And a large anti-chain that match in size. And this is actually much more difficult and it requires some tools that we do not yet have. So we have to wait a couple of weeks. But I promise you, when we come to the topic of matchings in bi-part graphs, then we have the tools to prove Dilworth's theorem. But for today, we have actually to put up with, just proving one half of it. All right, so here is an application of Mirsky's theorem, a direct corollary. It tells you that if you have a set S, then one of the width or the height must be large. So the product of both must be at least S. Why is that? So why is that? Well, you see, there must exist an i, such as Ai is at least S divided by t, right? Because all sets together make up whole of S. And what is this? By Mirsky's theorem, this is S divided by the height. This proves the theorem. All right, here is a nice application. So what you see here is a sequence of integers. One, three, two, and so on. So what I marked here are integers that are increasing. So this is an increasing subsequence. And there are also decreasing subsequences, for example this is a decreasing subsequence. And now there is a famous theorem by Erdos-Szekeres. It says, if you have in distinct integers, then either you find a long increasing subsequence, long meaning at least square root n, or a decreasing subsequencing of length at least n, square root n, or both. But you find, at least, one of the two. So how can you prove it? Well, actually, it follows pretty directly from Mirsky's theorem, are the following proof. So we take all sequence of numbers and we put it into a two dimensional space. So note, the first element in my sequence is one, so I should put it down here. The second is three, we should put a vertex here. The third, I put here, and the fourth is eight, so I should put it somewhere up here, all right. So I can take my sequence of integers and I get a set of points in n squared. So now we know that n squared with this relation is a partially ordered set. And this is the Hazi diagram of this partially ordered set. And the key observation is if you have a chain in this partial ordering, then this corresponds to an increasing subsequence. So this is one, two, four, and 13. This is an increasing subsequence, and similarly if you have an anti-chain like this, it corresponds to a decreasing subsequence. So in this case, this would be eight and seven. And now you see that the largest increasing subsequence, the size of the largest increasing subsequence is actually the height of all partial ordering. And, the size of the largest decreasing subsequence is the width. And therefore, the product of these two must at least n by Mirsky's theorem. So one of them is at least squared root n. So here's a summary. Here you can see the Erdos-Szekeres theorem that we have just proved. And actually, you can state it in a little bit more general form. If you want, you can easily verify that the same proof that you gave also proves this more general form. All right, that's it for today. Thank you for listening and I'll see you next week. Goodbye. [MUSIC]