# 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.
Dans le même article de 1935 où ce résultat est démontré figure aussi le Happy Ending problem.

## Un exemple

Pour r = 3 et s = 2, l'énoncé dit que toute permutation de trois nombres contient une sous-suite croissante de longueur 3 ou une sous-suite décroissante de longueur 2. Parmi les six permutations de {1, 2, 3} :
* (1, 2, 3) est une suite croissante ;
* (1, 3, 2) contient la sous-suite décroissante (3, 2) ;
* (2, 1, 3) et (2, 3, 1) contiennent la sous-suite décroissante (2, 1) ;
* (3, 1, 2) et (3, 2, 1) contiennent les sous-suites décroissantes (3, 1) et (3, 2).

## Interprétation géométrique

Étant donné un ensemble de points dans le plan euclidien, on forme une suite en triant les points par abscisses croissantes ; les nombres comparés dans le théorème d'Erdős-Szekeres sont alors les ordonnées des points. Dans ce contexte, le théorème affirme que s'il y a au moins rs + 1 points, on peut trouver une ligne polygonale de r segments de pentes positives, ou de s segments de pentes négatives. Par exemple, en prenant r = s = 4, tout ensemble de 17 points contient une ligne polygonale composée de quatre segments qui ont tous une pente de même signe.
Un exemple qui montre que la borne est atteinte, c'est-à-dire que rs points ne suffisent pas pour obtenir une telle ligne polygonale, consiste à prendre une grille régulière de rs points et de lui appliquer une légère rotation.

## Démonstrations

Le théorème d'Erdős-Szekeres peut être prouvé de diverses manières ; Steele passe en revue six preuves différentes, parmi lesquelles les deux suivantes. D'autres preuves décrites par Steele incluent la preuve originale d'Erdős et Szekeres, celles de Blackwell, Hammersley et Lovász.

### Principe des tiroirs

Étant donné une suite de (r – 1)(s – 1) + 1 points, on étiquette le i-ème nombre n$_i$ de la suite par un couple (a$_i$, b$_i$) d'entiers positifs, où a$_i$ est la longueur de la plus longue sous-suite croissante qui se termine par n$_i$, et b$_i$ est la longueur de la plus longue sous-suite décroissante qui se termine par n$_i$. Deux nombres de la suite sont étiquetés par des paires distinctes : en effet, soient i < j deux indices ; si n$_i$ < n$_j$, alors a$_i$ < a$_j$ ; si au contraire n$_i$ > n$_j$, alors b$_i$ < b$_j$. D'autre part, il n'y a que (r – 1)(s – 1) couples tels que a$_i$ < r et b$_i$ < s. Par le principe des tiroirs, il existe un entier i tel que a$_i$ ≥ r ou b$_i$ ≥ s ; dans le premier cas, n$_i$ fait partie d'une sous-suite croissante de longueur au moins r et dans le deuxième cas, n$_i$ fait partie d'une sous-suite décroissante de longueur au moins s.
Steele attribue cette preuve à Seidenberg (en) et l'appelle, dans son article de synthèse, la « preuve la plus lisse et la plus systématique ».

### Théorème de Dilworth

Un autre preuve fait appel au théorème de Dilworth sur la décomposition en chaînes d'un ordre partiel, ou à sa version duale, le théorème de Mirsky (en).
Pour cela, on définit un ordre partiel sur les nombres de la suite par : x est inférieur ou égal à y dans cet ordre partiel si x ≤ y comme nombres, et si x figure avant y dans la suite. Une chaîne dans cet ordre est une sous-suite croissante, et une antichaîne est une sous-suite décroissante. Par le théorème de Mirsky (en), s'il n'existe pas de chaîne de longueur r, la suite peut être partitionnée en au plus r – 1 antichaînes ; la plus longue de ces antichaînes forme alors un sous-suite décroissante de longueur au moins
    $\left\lceil {\frac {(r-1)(s-1)+1}{r-1}}\right\rceil =s.$
De manière duale, par le théorème de Dilworth lui-même, s'il n'existe pas d'antichaîne de longueur s, alors la suite peut être partitionnée en au plus s – 1 chaînes, et la plus longue doit avoir longueur au moins r.