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

En [[matemáticas]], el '''teorema de Erdős-Szekeres''' es un resultado de finitud que precisa uno de los corolarios del [[teorema de Ramsey]]. Mientras que el teorema de Ramsey facilitar probar que toda sucesión infinita de números reales distintos contiene una [[subsucesión]] infinita monótonamente creciente o una subsucesión infinita monótonamente decreciente, el resultado que probaron [[Paul Erdős]] y [[George Szekeres]] va más allá. Para ''<math>r''</math>, ''<math>s''</math> dados, probaron que cualquier sucesión de longitud al menos <math>(''r''&nbsp;&#x2212;&nbsp;-1)(''s''&nbsp;&#x2212;&nbsp;-1)&nbsp;+&nbsp;1</math> contiene una subsucesión monótonamente creciente de longitud&#x20;'' <math>r''</math> o una subsucesión monótonamente decreciente de longitud&#x20;'' <math>s''</math>. La demostración está en el mismo artículo de 1935 que menciona el [[problema del final feliz]].<ref>{{Citation|authorlink1=Paul Erdős|last1=Erdős|first1=Paul|authorlink2=George Szekeres|last2=Szekeres|first2=George|title=A combinatorial problem in geometry|journal=[[Compositio Mathematica]]|volume=2|pages=463–470|year=1935|url=http://www.numdam.org/item?id=CM_1935__2__463_0|zbl=0012.27010|doi=10.1007/978-0-8176-4842-8_3|postscript=.}}</ref>

Para ''<math>r''&nbsp;=&nbsp;3</math> y ''<math>s''&nbsp;=&nbsp;2</math>, la fórmula afirma que cualquier permutación de tres números tiene una subsucesión creciente de longitud tres o una subsucesión decreciente de longitud dos. Tomando las seis posibles permutaciones de los números 1, 2, 3: