Friday, November 14, 2008

Monotone Sequence Theorem: literature thing

Sometimes the literature gives a proof, and then a reference, but the reference is not really to that proof. Here is an example. The theorem in question is the following:
For any seq of n2+1 distinct reals there is either a dec subseq of length n or an inc subseq of length n+1.
In Proofs from the book the authors attribute the following argument to Erdos-Szekeres (paraphrased):
Let the seq be a(1),...,a(n2+1). Associate to each a(i) the number t(i) which is the length of a longest inc subseq starting at a(i). If there is an i such that t(i) &ge n+1 then we are done. If not then the function mapping a(i) to t(i) maps a set of size n2+1 to a set of size n. Hence there is some s such that n+1 elements of the seq map to s. These n+1 elements form a dec seq.
The actual proof in the Erdos-Szekeres paper is this (paraphased):
Let f(n) be the minimum number of points out of which we can select n inc or dec subseq. We show f(n+1) = f(n)+2n-1. Let a(1),...,a(f(n)+2n-1) be a sequence of distinct reals. Out of the first f(n) of them there is an inc or dec subseq of length n. Call the last elements of that subseq b(1). Remove it. (There is now a seq of length f(n)+2n-2.) Repeat the process to obtain b(1), b(2), ..., b(2n). Let A be the b(i)'s that are from inc subseq. Let B be the b(i)'s that are from dec subseq. It is easy to show that A is itself a dec subseq and that B is itself an inc subseq. If A or B has n+1 elements then we are done. The only case left is that A and B each have n elements. Let a be the last element in A and b be the last element in b. It is easy to show that a=b. But one of them was removed before the other, so this is impossible.
  1. I suspect that in talks Erdos gave he did the proof now atributed to Erdos-Szekeres and hence people naturally assumed that this is the paper it was in.
  2. I am surprised that Proofs from the book gave this proof. There is, IMHO, a better proof. I do not know whose it is.
    Let the seq be a(1),...,a(n2+1). Map every 1 \le i \le n2+1 to (x,y) where x (y) is the length of the longest inc (dec) subseq than ends with a(i). It is easy to show that this map is 1-1. If all of the x,y that are mapped to are in [n]x[n] then the domain is bigger than the range, contradiction.
  3. Erdos-Szekeres first proved this theorem in 1935. Martin and Joseph Kruskal proved it 15 years later without knowing that Erdos-Szekeres had proven it; though by the time Joesph Kruskal published it he knew. I have gathered up 5 proofs of the theorem that I know here.
  4. In those days it was harder to find out if someone else had done what you had done since they didn't have google, but it may have (in some cases) been easier since there were so many fewer researchers- you could just call them. OH- but long distance was expensive back then.


  1. Of the three proofs you give here, only the "Proofs from the book" one does not use the phrase "it is easy to show". That, in my opinion, makes it the better proof.

  2. Some comments:

    You say in the post that any sequence of n^2+1 distinct reals contains either a decreasing subsequence of length n or an increasing subsequence of length n+1. You can actually make both of those n+1, as you do in your collection of five proofs.

    Also, why not make it more general? Any sequence of length ab+1 contains either a decreasing subsequence of length a+1 or an increasing subsequence of length b+1. Moreover, it's worth mentioning that this is tight, by considering the following sequence of length ab: b,b-1,...,2,1;2b,2b-1,...,b+2,b+1; ...; ab,ab-1,...,(a-1)b+2,(a-1)b+1.

    Finally, the last proof in the PDF contains a minor error. You say that the co-domain of the map f is [n+1]x[n+1]. The actual co-domain could be much larger, e.g. if you consider the sequence 1,2,3,...

  3. Anon 1 (indirectly) raises a good question with regard to what level of details a proof should contain. I am an advocate for spelling out all details unless they're obvious to the average undergraduate student in mathematics. Clear explanations make a paper more easily accessible to those in neighboring fields of expertise.

  4. J Michael Steele has a survey with "six or more proofs" of it and related problems. Highly recommended. He attributes maybe the cutest proof to Hammersley (which you don't cite) and the last one you mention as your favorite to Seidenberg (1959). This last one is the version that seems the most generalizable.

  5. For those who don't look at the Steele survey, here is that other proof: View the numbers as being written on cards to be stacked in piles ordered from left to right. A card can be placed on top of another card if it has a smaller value. Place each card in turn on top of the leftmost pile where it fits. If a card's value is smaller than the top cards in all preceding piles then start a new pile to the right of the existing piles and record a pointer from that card to the top card of the immediately preceding pile.

    By the pigeonhole principle either there is a pile of height n+1, which is a decreasing sequence of length n+1, or there are n+1 piles in which case following back the pointers to the first pile selects an increasing sequence of length n+1.

  6. Correction; For each card records a pointer to the top card in the immediately preceding pile, not just when new piles are created.

  7. Thanks Paul - I like that proof as it is constructive (and efficient to implement).

  8. Yes, the book "Extremal Combinatorics" says that this proof is due to Seidenberg. And it is indeed beautiful.

  9. Proofs from the Book gives an argument that makes the claim immediately /intuitive,/ while the shorter alternative proof does not make it immediately obvious why the specified mapping is one-to-one.

  10. Amen to Anonymous 1. It is easy to show that the phrase "it is easy to show" is often false.