Why is Erdős–Szekeres theorem sharp?

1,413

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$.

Share:
1,413

Related videos on Youtube

Oria Gruber
Author by

Oria Gruber

Updated on December 06, 2020

Comments

  • Oria Gruber
    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
      cactus314 almost 10 years
      hint: draw the numbers in a square
  • GinKin
    GinKin almost 10 years
    Didn't you just prove that it isn't sharp ? Can you please give an example of what you meant ?