théorème d'Erdös-Szekeres

Placez des points sur une feuille sans jamais en aligner trois. Même si leur disposition paraît désordonnée, un ensemble assez nombreux cache toujours un certain nombre de points qui dessinent un polygone convexe : aucun sommet ne rentre vers l’intérieur.

Le théorème d’Erdős-Szekeres garantit cette forme sans indiquer d’avance quels points la composent. Pour cinq sommets, neuf points quelconques en position générale suffisent toujours. Le nombre neuf est optimal : avec seulement huit points, la garantie disparaît.

Le théorème d’Erdős-Szekeres est un résultat d’existence en géométrie combinatoire. Il s’applique à un ensemble fini de points du plan en position générale, c’est-à-dire sans trois points alignés. Pour un entier N au moins égal à 3, il assure qu’un ensemble suffisamment grand contient N points en position convexe : ces points sont exactement les sommets de leur enveloppe convexe et forment donc un polygone convexe à N sommets.

On note f(N) le plus petit nombre de points qui impose cette conclusion. Les valeurs établies dans la définition source sont f(3) = 3, f(4) = 5, f(5) = 9 et f(6) = 17. Le cas f(4) = 5 correspond au théorème d’Esther Klein, aussi associé au problème de la fin heureuse ; le résultat d’Erdős-Szekeres en donne la généralisation.

Erdős et Szekeres ont démontré que f(N) est finie pour tout entier N au moins égal à 3. Ils ont conjecturé la formule suivante :Elle reproduit les quatre valeurs connues de N = 3 à N = 6. D’après la définition source, la valeur exacte de f(N) reste inconnue lorsque N est supérieur à 6.

Si N est un entier au moins égal à 3, alors il existe un entier fini f(N) tel que tout ensemble d’au moins f(N) points du plan, sans trois points alignés, contient N points formant les sommets d’un polygone convexe.

Le nombre f(N) est minimal : remplacer f(N) par f(N) − 1 rend l’affirmation fausse pour au moins une configuration. Ainsi, f(5) = 9 signifie à la fois que neuf points suffisent toujours et qu’une configuration de huit points peut ne contenir aucun pentagone convexe.

Le cadre est le plan, et les données sont un ensemble fini de points ainsi qu’un entier N au moins égal à 3. La condition vérifiable est la position générale : aucune droite ne doit contenir trois des points. La conclusion porte sur un sous-ensemble de N points, pas nécessairement sur l’ensemble entier. Ces N points doivent tous être des sommets de leur enveloppe convexe.

Si trois points sont alignés, l’hypothèse échoue. Par exemple, neuf points placés sur une même droite ne déterminent aucun polygone convexe. Il faut alors modifier la configuration ou employer un énoncé qui autorise les alignements ; le seuil f(N) présenté ici ne s’applique pas tel quel.

Considérons neuf points : A(0, 0), B(8, 0), C(10, 5), D(5, 10), E(0, 7), P(1, 1), Q(1, 3), R(2, 3) et S(2, 5). Aucun triplet n’est aligné. Le dessin permet de suivre le pentagone extérieur A–B–C–D–E.

1. On fixe N = 5. La valeur connue f(5) = 9 garantit qu’un ensemble de neuf points en position générale contient un pentagone convexe.

2. Les quatre points P, Q, R et S sont strictement à l’intérieur du polygone A–B–C–D–E. Les cinq autres points en forment donc les sommets extérieurs.

3. En parcourant A, B, C, D puis E, chaque changement de direction se fait dans le même sens et aucun angle intérieur ne rentre dans la figure. Le pentagone A–B–C–D–E est convexe.

4. Le sous-ensemble {A, B, C, D, E} fournit les cinq sommets demandés. Le contrôle est refaisable dans la représentation : les quatre autres points restent à l’intérieur du contour rouge. Le théorème garantit l’existence d’un tel choix pour toute configuration admissible de neuf points, même si son pentagone est moins visible.

Pour vérifier une configuration donnée, on commence par contrôler qu’aucun triplet de points n’est aligné. On cherche ensuite un sous-ensemble dont tous les points sont sur le bord de sa propre enveloppe convexe. Ce critère évite de se fier seulement à l’apparence du tracé.

Pour obtenir une garantie sans examiner toutes les configurations, on compare leur effectif à une valeur connue de f(N). Neuf points garantissent un pentagone convexe ; dix-sept garantissent un hexagone convexe. En dessous du seuil minimal, une recherche directe peut encore réussir, mais le théorème ne promet plus le résultat.

Dans un raisonnement, le théorème sert surtout à établir l’existence d’un sous-ensemble convexe. Si l’on doit aussi exhiber ses sommets, il faut ajouter une méthode de recherche dans la configuration ; le seul énoncé ne fournit pas cette sélection.

La position générale concerne l’ensemble de départ : aucun de ses triplets n’est aligné. La position convexe concerne le sous-ensemble recherché : chacun de ses points est un sommet de son enveloppe convexe. Neuf points peuvent donc être en position générale sans être tous en position convexe.

Un polygone simple ne croise pas ses propres côtés, mais il peut avoir un angle rentrant. Le polygone exigé ici est convexe. Si un sommet se trouve à l’intérieur de l’enveloppe convexe des autres, la configuration ne fournit pas le sous-ensemble demandé.

Alignements. Dès que trois points sont alignés, la position générale n’est plus vérifiée. Il ne faut pas appliquer automatiquement les seuils f(N) ; il faut traiter les alignements séparément ou changer d’énoncé.

Existence sans construction. Le théorème affirme qu’un sous-ensemble convexe existe, mais ne désigne pas ses sommets. Si la configuration est fournie, une procédure de recherche supplémentaire reste nécessaire pour exhiber le polygone.

Sous-ensemble, non totalité. Les points inutilisés peuvent être à l’intérieur ou à l’extérieur d’un polygone candidat. Il faut seulement que les N points choisis soient les sommets de leur propre enveloppe convexe.

Seuil connu jusqu’à 6. La définition source donne f(6) = 17, mais indique que la valeur exacte de f(N) reste inconnue pour N supérieur à 6. La formule f(N) = 1 + 2^N−2 doit alors être présentée comme une conjecture, et non comme un seuil démontré.

La fiche concept de convexité précise la propriété géométrique qui empêche un segment joignant deux points de sortir de la figure.

L’article La géométrie convexe replace enveloppes et polygones convexes dans le domaine géométrique auquel appartient ce résultat combinatoire.