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.
Thoughts:
-
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.
-
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.
-
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.
-
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.
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.
ReplyDeleteSome comments:
ReplyDeleteYou 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,...
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.
ReplyDeleteJ 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.
ReplyDeleteFor 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.
ReplyDeleteBy 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.
Correction; For each card records a pointer to the top card in the immediately preceding pile, not just when new piles are created.
ReplyDeleteThanks Paul - I like that proof as it is constructive (and efficient to implement).
ReplyDeleteYes, the book "Extremal Combinatorics" says that this proof is due to Seidenberg. And it is indeed beautiful.
ReplyDeleteProofs 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.
ReplyDeleteAmen to Anonymous 1. It is easy to show that the phrase "it is easy to show" is often false.
ReplyDelete