A Theorem of Erdős and Szekeres

A theorem by two mathematical greats, which anybody, no maths experience required, can understand! An amazing and beautiful result accompanied by some pretty hand-coded visualisations!

Regardless of your experience with math, this theorem can be understood, and the elegance of the solution appreciated. Throughout I will both use diagrams to explain concepts where possible. Where I use algebra notation like ‘x’ and ‘y’, I will also give concrete examples using real numbers so you can understand what is going on even if you aren’t comfortable with algebra.

Simple diagrams to explain complicated language

Before I state the problem, I want to build some understanding. That’s because the terms can be confusing to people who haven’t done much math, but by taking a little more time we can understand the problem without previous knowledge of any complicated language. If you are familiar with the terms used (in bold), then you can skip to the next section.

Sequence

An example sequence of numbers

First, we learn what a sequence of numbers is. (1,2,3,4,5) is a sequence of numbers. (2,9,-1,23,12,24,-5) is another sequence of numbers. A sequence of numbers is simply a list of numbers, where you can ask what the first number is, what the second number is, and so on. For example, in the sequence (2,9,-1,23,12,24,-5), the first number is 2, the second number is 9, the third number is -1, the fourth number is 23, the fifth number is 12, the sixth number is 24 and the seventh number is -5. Then the sequence ends.

(2,-1,24,-5) is a subsequence of (2,9,-1,23,12,24,-5)

Second, we learn what a subsequence of numbers is. A subsequence of numbers takes a sequence, and then only looks at some numbers in the sequence. This is like going shopping in a supermarket: you don’t have to take every item in an aisle, you can instead go down the aisle, and take a couple of elements out. For example, a subsequence of (1,2,3,4,5) is (1,4,5); a subsequence of (2,9,-1,23,12,24,-5) is (2,-1,24,-5). In each case, we simply chose a few numbers, from left to right, from the original sequence.

(2, -1, -5) is a decreasing subsequence

Finally, we learn what an increasing subsequence, and decreasing subsequence are. (1,3,5) is an increasing subsequence of (1,2,3,4,5), as 1≤3≤5. A decreasing subsequence of (2,9,-1,23,12,24,-5) is (2,-1,-5), as 2≥-1≥-5.

(1,3,5) is an increasing subsequence

Note that while some subsequences are increasing, and some are decreasing, others are neither. Consider the sequence (1,2,3,4,5,0). Then (1,4,0) is a subsequence which is neither increasing (as 4≥0, as 0 is after 4 in the sequence), not is it decreasing (as 1≤ 4 and 4 is after 1 in the sequence).

To use our supermarket analogy, if you go down the aisle, and every new item you pick is more expensive than the last, then you have picked an increasing sequence. If you go down the aisle, and every new item is less expensive than the last, then you have picked a decreasing sequence. And, finally, if you go down the aisle, and sometimes the next item you pick is more expensive, and sometimes less expensive, then the subsequence you have picked is neither increasing, nor is it decreasing.

Statement of the Theorem

Suppose we have the numbers 1,2,3,…N, but arranged in any order. For example, if N=5, we have the numbers 1,2,3,4,5 and we allow them to be arranged in any order; such as (3,4,1,2,5)

An example of arranging (1,2,3,4,5) in a random order

The Erdos-Szekeres theorem tells us that there either an increasing subsequence of length root N, or there is a decreasing subsequence of root N.

Suppose N = 3² = 9. Then the Erdos-Szekeres sequence tells us that we have the numbers (1,2,3,…,9) arranged in any order, we can either find an increasing subsequence of at least length 3, or a decreasing subsequence of at least length 3. In the sequence (9,3,2,6,1,4,5,8,7) you can check for yourself that this is indeed the case; e.g. (2,4,5,7) is an increasing subsequence of length 4. A visual illustration of this example is below.

What if N isn’t a perfect square? Then we look at the square root rounded up. If N = 50, then the square root of 50 is about 7.07, so we round upwards to 8, and the theorem tells us that we are guaranteed either an increasing subsequence of length at least 8, or a decreasing subsequence of length at least 8. However, we will only look at the case where N is a perfect square because the logic is essentially the same in both cases, just the algebra is a little messier when N is not a square number.

Proof

For each number in the sequence, consider the longest increasing subsequence which ends at that number, and longest decreasing subsequence which ends at that number.

Consider two points in the sequence, x and y, with x earlier in the sequence than y. If x is larger than y, i.e. x>y, then for any decreasing sequence which ends at x, we can make it longer by making it end at y. This remains a decreasing sequence, as y is smaller than x. The diagram below illustrates this

For instance, if x=10, and y=5, the decreasing sequence (16,14,13,11,10) which ends at x, can be made longer by including y on the end, (16,14,13,11,10,5), and this remains a decreasing subsequence. This guarantees that the longest decreasing subsequence ending at y is longer than the longest decreasing subsequence ending at x, provided x>y.

y is smaller than x; therefore we can extend a decreasing subsequence ending at x to include y.

If y is larger than x, i.e. y>x then we get a very similar result. If we have an increasing subsequence ending at x, we can make it longer by including y, which remains an increasing subsequence as y>x. This guarantees that the longest increasing subsequence ending at x is shorter than the longest increasing subsequence ending at y, provided y>x.

y is greater than x: therefore we can extend an increasing subsequence ending at x.

Note, either y>x or x>y, as all the numbers in our sequence are different.

We will be using the following notation in the next sections, so please read the next two paragraphs carefully.

Let Inc[x] denote the length of the longest increasing subsequence ending at x, and let Dec[x] denote the length of the longest decreasing subsequence ending at x. We use the same notation for y. E.g. in (1,2,3,0,4), Inc[1] = 4, as the longest increasing subsequence starting at 1 is (1,2,3,4) which is length 4. To help you remember, ‘Inc’ is an abbreviation of ‘Increasing’, and ‘Dec’ is an abbreviation of ‘Decreasing’

It is impossible that both Inc[x] = Inc[y] and Dec[x] = Dec[y]. This is because, if x>y then Dec[x] < Dec[y], and if xy, we can create a longer decreasing subsequence ending at y than x, and when x