Why is Erdős–Szekeres theorem sharp?
For $n=5$:
$$\underbrace{5,4,3,2,1},\underbrace{10,9,8,7,6},\underbrace{15,14,13,12,11},\underbrace{20,19,18,17,17},\underbrace{25,24,23,22,21}$$
Any subsequence of $6$ of these numbers must contain two numbers from the same block and two numbers from different blocks. Two numbers from the same block must appear in decreasing order, while two from different blocks must appear in increasing order. Thus, the subsequence cannot be monotonic.
The construction clearly generalizes to arbitrary $n$.
Related videos on Youtube
Oria Gruber
Updated on December 06, 2020Comments
-
Oria Gruber almost 3 years
I have a question about Erdős–Szekeres:
Erdős–Szekeres theorem - if there is a sequence of $n^2+1$ numbers, then there is either a monotonic rising subsequence of $n+1$ numbers or a monotonic descending subsequence of $n+1$ numbers.
(I realize that the general form is $ab$ instead of $n^2$ but that is how I was taught and for the sake of this question, it's the same thing).
What I want to know is, is this theorem sharp? In other words, is it possible to find a sequence of $n^2$ numbers that does not have a monotonic subsequence of $n+1$ numbers for all $n \in \mathbb N$?
-
cactus314 almost 10 yearshint: draw the numbers in a square
-
-
GinKin almost 10 yearsDidn't you just prove that it isn't sharp ? Can you please give an example of what you meant ?