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.
 
Se puede formar un ejemplo de ''<math>rs''&nbsp;&#x2212;&nbsp;''-r''&nbsp;&#x2212;&nbsp;''-s''&nbsp;+&nbsp;1</math> puntos sin un camino de este tipo, probando que este límite es fijo, aplicando una pequeña rotación a una red <math>(''r''&nbsp;&#x2212;&nbsp;-1)</math> por <math>(''s''&nbsp;&#x2212;&nbsp;-1)</math>.
 
=== Interpretación en patrones de permutación ===
17 673

ediciones