Talk:Erdős–Szekeres theorem

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	B Class	Low Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. May need more reference. Also consider nominating for Good Article status. Tompw (talk) 16:14, 4 January 2007 (UTC) A bit more context/motivation/application would also help. Geometry guy 20:56, 9 June 2007 (UTC)

This is a verbatim copy of the MathWorld page. Charles Matthews 21:58, 9 February 2006 (UTC)

Not any more it isn't! —David Eppstein 22:53, 7 October 2006 (UTC)

I changed "x comes before y" to "x comes not after y" since to be a partial order a relation must be reflexive.

[edit] Proof of tightness

This theorem is tight, and there's an easy way to show it.

What I mean by that is that for each positive integer n there exists a sequence of n^2 real numbers which does not contain a monotonous subsequence of length n+1.

Proof: Consider the following sequence: (n(n − 1) + 1,...,n²,n(n − 2) + 1,...,n(n − 1),...,...,n + 1,...,2n,1,...,n)

It's easy to see that in the following sequence any monotonous subsequence is of length n or less.

Should someone think that we ought to include it in the article? Peleg 12:23, 8 May 2007 (UTC)

Yes, if you can find a source that says the same thing. —David Eppstein 16:05, 8 May 2007 (UTC)