Cualquier sucesión de mn+1 números tiene una subsucesión monótona de largo m+1 o n+1.
El Teorema de Erdős-Szekeres es un resultado fundamental en combinatoria y Teoría de Ramsey que garantiza que existe una subestructura organizada dentro de un sistema caótico lo suficientemente grande. Específicamente, asegura que cualquier sucesión finita de números reales distintos, si es lo suficientemente larga, debe contener una subsucesión monótona "larga". Una subsucesión la formas eliminando cero o más elementos de la sucesión original manteniendo el orden relativo de los elementos que quedan; no hace falta que sean contiguos.
Este teorema es una aplicación clásica del Principio de las Casillas y da una cota determinista para el orden en las sucesiones. Lo puedes usar muchísimo en olimpiadas de matemáticas para resolver problemas de permutaciones, configuraciones geométricas (como el "Problema del Final Feliz" sobre polígonos convexos) y algoritmos de ordenamiento. La intuición detrás del teorema es un análisis del "peor caso": si intentas construir una sucesión que no tenga una subsucesión creciente larga, te ves obligado a acomodar los números de forma que crees una subsucesión decreciente larga, y viceversa.
El Teorema General Para cualesquiera enteros $r, s \ge 1$, cualquier sucesión de números reales distintos con una longitud de al menos $(r-1)(s-1) + 1$ contiene ya sea: