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

Modèle:Voir homonymes 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 : Modèle:Énoncé

Dans le même article de 1935 où ce résultat est démontré figure aussi le Modèle:Lang.

Un chemin de quatre segments de pente positive dans un ensemble de 17 points. On considère la suite des ordonnées des 17 points triés par abscisses croissantes ; le théorème d'Erdős-Szekeres assure alors qu'il quatre segments consécutifs de pente positive ou quatre segments consécutifs de pente négative. Si le point central est omis, un tel chemin n'existe pas.

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 [[Groupe symétrique|six permutations de Modèle:Nobr]]

• (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 nModèle:Ind de la suite par un couple (aModèle:Ind, bModèle:Ind) d'entiers positifs, où aModèle:Ind est la longueur de la plus longue sous-suite croissante qui se termine par nModèle:Ind, et bModèle:Ind est la longueur de la plus longue sous-suite décroissante qui se termine par nModèle:Ind. Deux nombres de la suite sont étiquetés par des paires distinctes : en effet, soient i < j deux indices ; si nModèle:Ind < nModèle:Ind, alors aModèle:Ind < aModèle:Ind ; si au contraire nModèle:Ind > nModèle:Ind, alors bModèle:Ind < bModèle:Ind. D'autre part, il n'y a que (r – 1)(s – 1) couples tels que aModèle:Ind < r et bModèle:Ind < s. Par le principe des tiroirs, il existe un entier i tel que aModèle:Ind ≥ r ou bModèle:Ind ≥ s ; dans le premier cas, nModèle:Ind fait partie d'une sous-suite croissante de longueur au moins r et dans le deuxième cas, nModèle:Ind fait partie d'une sous-suite décroissante de longueur au moins s.

Steele attribue cette preuve à Modèle:Lien et l'appelle, dans son article de synthèse, la Modèle:Citation.

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 Modèle:Lien.

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 Modèle:Lien, 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

$\lceil \frac{(r-1)(s-1)+1}{r-1}\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.