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

math
m (Añadiendo la Categoría:Geometría discreta mediante HotCat)
(math)
[[Archivo:Monotone-subseq-17-5.svg|miniaturadeimagen|Un camino de cuatro aristas ascendentes en un conjunto de 17 puntos. Por el teorema de Erdős-Szekeres, todo conjunto de 17 puntos tiene un camino de esta longitud bien ascendente o bien descendente. El subconjunto de 16 puntos que no incluye el punto central no tiene ningún camino de este tipo.]]
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>
 
== Ejemplo ==
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:
* 1,2,3 tiene una subsucesión creciente consistente en los tres números<br>
* 1,3,2 tiene una subsucesión decreciente 3,2
17 673

ediciones