Erdos-Szekeres, and The Mathematical Certainty of Structure

So, a couple of interesting results have come to light over the past week or so, and I'd like to discuss them here.

First off, consider the following 101 random integers, generated using Mathematica, between 0 and 1000 for convenience to me.

{458, 22, 856, 736, 354, 348, 843, 722, 112, 389, 790, 84, 154, 672, 263, 226, 185, 706, 985, 123, 161, 679, 349, 132, 562, 484, 576, 593, 503, 413, 895, 415, 227, 325, 791, 453, 386, 53, 772, 688, 765, 576, 644, 621, 404, 379, 5, 51, 684, 731, 286, 933, 111, 308, 758, 343, 664, 959, 659, 703, 817, 247, 817, 892, 923, 734, 305, 127, 340, 779, 412, 999, 264, 56, 825, 85, 477, 502, 603, 960, 496, 751, 363, 403, 419, 738, 670, 778, 271, 715, 932, 597, 899, 249, 228, 430, 891, 185, 23, 612, 544}

Going through in order, without even looking, I guarantee that there is a subsequence in that sequence of at least length 11 that is monotonic, either each term is greater than or equal to the next, or each term is less than or equal to the next.

Starting with 22, we can pick out, as convenient

{22, 112, 123, 132, 227, 325, 386, 404, 502, 670, 715, 932}

Even better, we managed to get a 12 length sequence.

At this point, you're probably wondering what it all means.

The point is that, repeat the experiment with any such sequence of 101 random numbers, and the result will always be the same. You will /always/ be able to find a monotonic subsequence of length 11. No matter what.

In general, this result is the Erdos-Szekeres Theorem. The idea is that given an arbitrary sequence of integers of length n² + 1, there always exists a monotonic subsequence of length n + 1.

And now, proof. This is kind of technical, so don't feel poorly if you'd like to skip to the end, where I finally make my point. The point is actually independent of the proof, but whatever :)

Proof

To begin with, we have a sequence,

{a₁, a₂, ..., a_n², a_n²+1}


So take each a_i in the sequence, in order. For each, consider the longest monotonic increasing subsequence that starts at a_i. We'll refer to this subsequence as L(a_i). Note that if L(a_i) is of length greater than or equal to n, for any a_i, this gives us a monotonic increasing subsequence of length at least n + 1, and we're done. So we have to assume that L(a_i) is of length less than or equal to n for all i.

This means that each subsequence L(a_i) has a length between 1 and n. Note too, that because each subsequence is different (each starts at a different a_i), there are n² + 1 many subsequences. So imagine sorting the sequences by length. Distributing n² + 1 many sequences over n many lengths, there must be some length such that at least n + 1 many subsequences have that length. We'll call that length t.

A bit of notation. We have a sequence of length n²+1, which we could refer to an arbitrary element of as a_i. Suppose we wanted to refer to a specific subsequence. For example, {a₃, a₅, a₁₂}. A way to think of this more compactly is to refer to the elements of the subsequence as a_k(j), where k(1) = 3, k(2) = 5, k(3) = 12. In general then, I can refer to subsequences of the main sequence as a_k(j), where j goes from 1 to the length of the subsequence.

Consider all the i's such that L(a_i) is of length t. As I said, there are at least n + 1 of these. Consider k(j) such that k(1) is the smallest i, k(2) is the next largest, and so on to k(n+1). a_k(j) is then an a subsequence of the original sequence of length n + 1.

I argue that {a_k(j)} is monotonically decreasing, which is to say that a_k(1) > = a_k(2) >= ... >= a_{k(n + 1)}.

Assume not, that we have k(j) < k(i) such that a_k(j) < a_k(i). We know that L(a_k(j)) and L(a_k(i)) are both of length t. But since L(a_k(j)) is the longest monotonically increasing subsequence starting at position k(j), as a_k(j) < a_k(i), a_k(i) must be included in L(a_k(j)). Further, all of L(a_k(i)) must be included in L(a_k(j)). This gives us then that L(a_k(j)) is actually longer than L(a_k(i)), since L(a_k(j)) includes all of L(a_k(i)), and L(a_k(i)) at the very least cannot include a_k(j). This contradicts the fact that both L sequences are of length t.

Therefore, we have that for all k(j), {a_k(j)} is in fact monotonically decreasing.

Therefore we have a monotonic sequence of length n + 1. And we are done.

So, the point is that Erdos-Szekeres guarantees that, independent of the sequence itself, any n² + 1 length sequence has a monotonic subsequence of length n.

This is is quite exceptional to me. The point of it all is that, within the sea of randomness that is ever possible sequence of a given length, there is a mathematical guarantee of order.

This shows up other places as well. For example, Ramsey theory guarantees that, if you invite 6 people to a party, no matter what people you invite, at least three of them will all know each other or all not know each other. Similarly, in a 49 person party, you are guaranteed a group of five people that all know or all don't know each other.

Islands of guaranteed stability within realms of what can only be described as chaos.

The reason all this interests me is that of late, on several fronts, there has been a question of order. Order in nature and the physical world, for example. Intelligent Design people maintain that order cannot arise from nothing. There's the question of the seeming order of the physical laws of the universe. Where does all this order come from? I don't claim to know the answer, but what this seems to suggest is that in any mathematical system, order might well be unavoidable. Even in a system that is consistently unpredictable, that behavior itself by the fact of it being described, has some degree of order. The Mathematical Certainty of Order.

I don't know if that's valid at all, but it certainly sounds nice.

Discuss.