tag:blogger.com,1999:blog-3722233.post3026220326441561527..comments2021-10-18T17:43:52.487-05:00Comments on Computational Complexity: Monotone Sequence Theorem: literature thingLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-92124976356238908382008-11-25T02:57:00.000-06:002008-11-25T02:57:00.000-06:00Amen to Anonymous 1. It is easy to show that the p...Amen to Anonymous 1. It is easy to show that the phrase "it is easy to show" is often false.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63291040234080985122008-11-17T14:17:00.000-06:002008-11-17T14:17:00.000-06:00Proofs from the Book gives an argument that makes ...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.Louis Wassermanhttps://www.blogger.com/profile/09791700199162146308noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-203249899636050282008-11-16T15:23:00.000-06:002008-11-16T15:23:00.000-06:00Yes, the book "Extremal Combinatorics" says that t...Yes, the book "Extremal Combinatorics" says that this proof is due to Seidenberg. And it is indeed beautiful.Unknownhttps://www.blogger.com/profile/07631055333881459954noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41747388787596114452008-11-16T10:49:00.000-06:002008-11-16T10:49:00.000-06:00Thanks Paul - I like that proof as it is construct...Thanks Paul - I like that proof as it is constructive (and efficient to implement).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15311763855114106032008-11-15T15:38:00.000-06:002008-11-15T15:38:00.000-06:00Correction; For each card records a pointer to th...Correction; For each card records a pointer to the top card in the immediately preceding pile, not just when new piles are created.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70893310513755301952008-11-15T13:47:00.000-06:002008-11-15T13:47:00.000-06:00For those who don't look at the Steele survey, her...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. <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7990936765270091752008-11-14T18:13:00.000-06:002008-11-14T18:13:00.000-06:00J Michael Steele has a survey with "six or more pr...J Michael Steele has a <A HREF="http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf" REL="nofollow">survey</A> 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31043913222483433182008-11-14T16:18:00.000-06:002008-11-14T16:18:00.000-06:00Anon 1 (indirectly) raises a good question with re...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21992460713329616442008-11-14T16:08:00.000-06:002008-11-14T16:08:00.000-06:00Some comments:You say in the post that any sequenc...Some comments:<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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,...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56946565094658977812008-11-14T15:29:00.000-06:002008-11-14T15:29:00.000-06:00Of the three proofs you give here, only the "Proof...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.Anonymousnoreply@blogger.com