Diferencia entre revisiones de «Teorema de Erdős-Szekeres»

Se pueden interpretar las posiciones de los números en una sucesión como las [[Coordenadas cartesianas|coordenadas ''x'']] de puntos en el [[plano euclídeo]], y los propios números como coordenadas ''y''; recíprocamente, para cualquier conjunto de puntos en el plano, las coordenadas y de los puntos, ordenadas por sus coordenadas ''x'', forman una sucesión de números (a menos que dos de los puntos tengan iguales coordenadas ''x''). Con esta relación entre sucesiones y conjuntos de puntos, el teorema de Erdős-Szekeres se puede interpretar como que en cualquier conjunto de al menos <math>rs-r-s + 2</math> puntos se puede encontrar un camino poligonal de o bien <math>r-1</math> aristas de pendiente positiva o <math>s-1</math> aristas de pendiente negativa. En particular (tomando <math>r=s</math>), en cualquier conjunto de al menos ''n'' puntos se puede encontrar un camino poligonal de al menos <math> \left \lfloor \sqrt (n-1) \right \rfloor</math> aristas con pendientes del mismo signo. Por ejemplo, tomando <math>r=s=5</math>, cualquier conjunto de al menos 17 puntos tiene un camino de cuatro aristas en el que todas las pendientes tienen el mismo signo.

 

 

=== Interpretación en patrones de permutación ===