So I've been stuck on Ramsey theory for a few days now and ran across this cool theorem. If you have a sequence of n²+1 distinct numbers, then you are guaranteed to have a monotonically increasing (or decreasing) subsequence of length n + 1 or more.

Of course I had to try this. Let n = 3, so that n²+1 = 10. The largest subsequence has to be of length n+1 = 4, or greater. Let's do an example.

I took a random permutation of {0..9} and got

π{0..9} = {0 9 7 8 1 3 5 4 2 6}

The longest increasing subsequence is {0 1 3 5 6}, which is of length 5.
The longest decreasing subsequence is {9 8 5 4 2}, which is also of length 5.

So in this case the theorem holds up, as it must. Try it yourself!

This theorem of subsequence length was shown in a 1935 paper by Paul Erdós and Szekeres. This was a cornerstone paper in the field of combinatorics now called Ramsey Theory. A general discussion of such subsequences can be found in Martin Aigner and Günter Ziegler's "Proofs from the Book," Springer-Verlag, (c)1998.

(Thanks to user Clockmaker who pointed out the Hungarian orthography of Paul Erdós's name here, as well as typo detection.)

Log in or register to write something here or to contact authors.