¿Por qué es Teorema de Erdős-Szekeres sharp?

Question

Tengo una pregunta acerca de Erdős–Szekeres:

Erdős–Szekeres teorema - si hay una secuencia de $n^2+1$ números, entonces hay una monótona creciente larga de $n+1$ o de los números de una monótona decreciente larga de $n+1$ números.

(Me doy cuenta de que la forma general es $ab$ en lugar de $n^2$ pero eso es lo que me enseñaron y por el bien de esta pregunta, es la misma cosa).

Lo que quiero saber es, es este teorema aguda? En otras palabras, es posible encontrar una secuencia de $n^2$ números que no tienen una monótona larga de $n+1$ números para todos los $n \in \mathbb N$?

Answer 1

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

Cualquier subsequence de $6$ de estos números debe contener dos números de la misma cuadra y dos números de diferentes bloques. Dos números del mismo bloque deben aparecer en orden decreciente, mientras que dos de los diferentes bloques deben aparecer en orden creciente. Así, el subsequence no puede ser monotónica.

La construcción se generaliza claramente arbitraria $n$.