Théorème d'Erdős-Szekeres

En mathématiques, et notamment en géométrie discrète, le théorème d'Erdős-Szekeres est une version finitaire d'un corollaire du théorème de Ramsey. Alors que le théorème de Ramsey permet de prouver facilement que toute suite infinie de réels distincts contient au moins une sous-suite infinie croissante ou une sous-suite infinie décroissante, le résultat prouvé par Paul Erdős et George Szekeres est plus précis en donnant des bornes sur les longueurs des suites. L'énoncé est le suivant : Soient r et s deux entiers. Toute suite d'au moins (r – 1)(s – 1) + 1 nombres réels contient une sous-suite croissante de longueur r ou une sous-suite décroissante de longueur s.

Texte : extrait de l'article Wikipédia « Théorème d'Erdős-Szekeres », sous licence CC BY-SA 4.0.