Au début des années 1930, dans un parc de Budapest, se réunissait régulièrement un groupe de jeunes mathématiciens. Bien avant le mouvement « hacktiviste », il se faisait appeler Anonymus, du nom d'une statue érigée en hommage à l'auteur inconnu de la Gesta hungarorum, première chronique de l'histoire hongroise. En 1933, Eszter Klein annonce à ses amis du groupe, dont Pál Erdös, Pál Turán et György Szekeres, le résultat suivant : parmi cinq points du plan, dont aucun triplet n'est aligné, on peut toujours en trouver quatre qui sont les sommets d'un quadrilatère convexe. Szekeres donne alors une preuve d'existence de la généralisation suivante : pour un nombre suffisamment grand de points du plan, on peut toujours en trouver k qui sont les sommets d'un k-gone (polygone de k côtés) convexe.

La démonstration est simple pour k = 5, on raisonne sur l'enveloppe convexe de cinq points. Si c'est un quadrilatère, le problème est réglé. 

Ordem e progresso

Erdös s'attaque lui aussi au problème et en fournit d'autres démonstrations et généralisations, ce qui constitue la pierre angulaire de la géométrie combinatoire, ou géométrie discrète. Il établit en 1934 avec Szekeres que pour tout entier n ≥ 3, il existe un entier minimal ES(n) tel que tout ensemble de ES(n) points du plan en configuration générale (aucun triplet aligné) contient n points qui constituent les sommets d'un n-gone convexe.

Erdös et Szekeres donnent dans le même article deux preuves de l'existence de ES(n). Leur première preuve repose sur le théorème de Ramsey et donne une très pauvre borne supérieure pour ES(n). Le théorème de Ramsey, fondamental dans la théorie de Ramsey (qui s'intéresse à déterminer la taille d'une structure pour qu'une configuration donnée apparaisse), stipule que dans tout graphe complet (aux sommets tous reliés entre eux) suffisamment grand et coloré existe un sous-graphe complet monochrome de taille donnée. Théodore Motzkin résume par contraposée cette théorie : « Le désordre complet est impossible. »

La seconde preuve est plus géométrique, utilisant ce qui est devenu le théorème d'Erdös–Szekeres (voir plus loin), et établissait que ES(n) ≤ (2n–4)! / (n–2)!² + 1. D'un autre côté, ils montrent que ES(n) ≥ 2^n–2 + 1 et conjecturent que ES(n) = 2^n–2 + 1, offrant 500 dollars de récompense à qui le prouverait (ou l'invaliderait).

Le cas n = 3 est trivial, la preuve pour n = 4 a été donnée par Eszter Klein, et celle pour n = 5 par Endre Makai selon les dires d'Erdös. En 2006, soixante-dix ans après son premier article sur le sujet, Szekeres prouve numériquement, dans un papier posthume rédigé avec son collègue Peters, qu'une configuration plane de dix-sept points, sans triplet aligné, contient toujours un hexagone convexe. Le cas n = 6 est donc résolu, lui aussi.

Corollaire de ce problème, György épouse Eszter en 1937, et dès lors Erdös le qualifie de happy ending problème. Et si leur histoire se termine avec leur décès le même jour, à une heure d'intervalle, le 28 août 2005 à Adélaïde, en Australie, l'aventure mathématique continue.

La borne supérieure ne fut pas améliorée pendant soixante ans ! Ce n'est qu'en 1998 qu'une petite unité est gagnée. Les travaux de Daniel Kleitman et Lior Pachter, puis de Géza Tóth en 2005, ne réussissent qu'à améliorer grossièrement d'un facteur 2 la borne supérieure d'Erdös–Szekeres. La borne reste du même ordre de grandeur,  \( $\text{O}(4^n/\sqrt[\;] {n})$\) , soit  \( $\text{O}(2^{2n+\text{O}(n)})$.\)  En 2015, Georgios Vlachos puis Sergei Norin raffinent cette estimation (voir en encadré l'utilisation des notations de Landau). C'est enfin au mois d'avril dernier que l'on enregistre une nette progression : l'Américain Andrew Suk précise, en trois pages de démonstration seulement, que pour n assez grand, \( $\text{ES}(n)\leq2^{n+4n^{4/5}}$\) .

L'encadrement de ES(n) se resserre donc nettement puisque 4/5 < 1. Pas d'euphorie cependant : il reste encore beaucoup de travail pour décider du statut de la conjecture !

En 1978, Erdös propose une variante du problème en demandant de trouver le nombre g(n) de points nécessaires pour garantir l'existence d'un n-gone convexe dont l'intérieur ne contient aucun point. On montre que g(4) = 5 et g(5) = 10, mais Joseph Horton prouve en 1983 que g(7) n'existe pas, pointant les limites de l'ordre caché dans les grandes structures ! Si l'on sait depuis 2007 que 30 ≤ g(6) ≤ 463, le problème de la valeur de g(6) reste néanmoins ouvert.

Théorèmes d'Erdös-Szekeres

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 monotone (croissante ou décroissante), le théorème d'Erdös-Szekeres est plus quantitatif en bornant les longueurs des suites. Voici son énoncé : soient deux entiers p et q. Toute suite d'au moins (p – 1)(q – 1) + 1 nombres réels contient soit une sous-suite croissante de longueur p (ou q), soit une sous-suite décroissante de longueur q (ou p).

Ce théorème peut être prouvé d'au moins six façons différentes, mais d'aucuns attribuent à Abraham Seidenberg « la preuve la plus lisse et la plus systématique », que voici.

Pour une suite de (p – 1)(q – 1) + 1 nombres réels, on associe au i-ème nombre n_i de la suite un couple C_i = (a_i, b_i), où a_i est la longueur de la plus longue sous-suite croissante se terminant par n_i, et b_i celle de la plus longue sous-suite décroissante se terminant par n_i. Pour i < j, si n_i < n_j on a, par définition des a_i, a_i < a_j, et bien sûr b_i < b_j si n_i > n_j. Dans tous les cas, les (p – 1)(q – 1) + 1 couples C_i sont différents et il ne sont au maximum que (p – 1)(q – 1) tels que a_i < p (soit p – 1 valeurs) et b_i < q (soit q – 1 valeurs). Par le principe des tiroirs, « théorème de Ramsey du pauvre », il existe donc au moins un couple C_j tel que a_j ≥ p, et n_j fait alors partie d'une sous-suite croissante de longueur au moins p, ou tel que b_j ≥ q, et n_j fait partie d'une sous-suite décroissante de longueur au moins q.