Talk:Erdős–Szekeres theorem

Untitled

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.

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^{2},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)

Awkward notation

I know this is subjective, but I feel it would look better if instead of saying that a sequence of $rs-r-s+2=(r-1)(s-1)+1\$ contains … etc., it used r+1 and s+1 instead: a sequence of length $rs+1$ contains either an increasing sequence of length r+1 or a decreasing sequence of length s+1. This is also how I've always seen it written, and e.g. how MathWorld does it (with ab+1). Could we change this? Shreevatsa (talk) 16:20, 6 November 2009 (UTC)

I prefer the (r-1)(s-1)+1 version, for the reason that it is clearer what r and s are: they are the desired lengths of the monotonic sequences you are looking for. In the MathWorld version, if you want to know how many items you need to get a monotonic sequence of length 10, you have to work backwards from the formula to set r=s=9 (and it would be easy to mistakenly set r=s=11) before plugging those values into the simpler rs+1 formula. As it is in the article, you just plug 10 directly into the formula. But I don't think the rs-r-s+2 part is so helpful; I've simplified it to include only the (r-1)(s-1)+1 part. —David Eppstein (talk) 18:15, 6 November 2009 (UTC)

I guess the question is whether it should be written in a form that is most helpful for a reader to use, or most good-looking to simply read. The difference is trivial in this case, so either way doesn't matter. :) Shreevatsa (talk) 06:26, 7 November 2009 (UTC)

Either or?

This article is very explicit that the theorem says _either_ an increasing or decreasing subsequence of sufficient length exists. However it seems one can meet the preconditions of this theorem by writing an increasing string of length r followed by a decreasing string of length s for sufficiently large r and s. So it appears incorrect. I will temporarily remove the "either or" language, but perhaps there is a related result with the either-or language that the author intended? [the math world article did not mention such a thing] 129.2.129.153 (talk) 17:47, 24 July 2012 (UTC)

Yes, that emphasis was misleading; the result is that there must be an increasing subsequence or a decreasing subsequence or both. --JBL (talk) 15:20, 25 July 2012 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Erdős–Szekeres theorem/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

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)

Last edited at 20:56, 9 June 2007 (UTC). Substituted at 02:04, 5 May 2016 (UTC)