Happy Ending problem

Le problème de la fin heureuse : tout ensemble de cinq points en position générale contient les sommets d'un quadrilatère convexe.

Le Modèle:Langue, ou Modèle:Langue, est un résultat de géométrie plane sur la relation entre la taille d'un ensemble de points en position générale et la taille de son plus grand sous-ensemble formant un polygone convexe. La formulation générale du problème est la conjecture d'Erdős-Szekeres.

Le problème d'origine, que l'on pourrait traduire par le problème à la fin heureuse, a été appelé ainsi par Paul Erdős parce qu'il a finalement conduit au mariage de deux chercheurs impliqués, George Szekeres et Esther Klein. L'énoncé est le suivant :

Ce théorème peut être prouvé par une simple analyse par cas : s'il y a quatre points qui sont les sommets de l'enveloppe convexe des points, on choisit quatre de ces points. Sinon, l'enveloppe convexe est un triangle, et ce triangle contient en son intérieur les deux points restants. Dans ce cas, on prend ces deux points intérieurs et un côté du triangle. Modèle:Harvsp contient une explication illustrée de cette preuve, et Modèle:Harvsp donne un survol plus détaillé du problème.

La conjecture d'Erdős-Szekeres formule précisément la relation générale entre le nombre de points d'un ensemble de points en position générale et la taille de son plus grand sous-ensemble formant un polygone convexe. La conjecture n'est pas prouvée, mais des bornes approchées sont connues.

Polygones plus grands

Un ensemble de huit points en position générale sans pentagone convexe.

Modèle:Harvsp prouvent la généralisation suivante:

La preuve figure dans le même article qui contient la démonstration du théorème d'Erdős-Szekeres sur les sous-suites monotones de suites de nombres.

Notons $f(N)$ le plus petit des entiers $m$ tels qu'un ensemble de $m$ points en position générale contient un polygone convexe à $N$ sommets.

• $f(3)=3$ trivialement ;
• $f(4)=5$. Ceci est le problème d'origine, résolu par Esther Klein et traité plus haut;
• $f(5)=9$. D'après Modèle:Harvsp, ceci a été prouvé en premier par E. Makai et Pál Turán. La première preuve publiée figure dans Modèle:Harvsp.
  La figure montre un ensemble de huit points sans pentagone convexe, ce qui montre que $f(5)>8$ ; la partie difficile de la preuve consiste à prouver que tout ensemble de neuf points en position générale contient les sommets d'un pentagone convexe ;
• $f(6)=17$. Cette égalité a été démontrée dans Modèle:Harvsp. La preuve utilise un modèle combinatoire de configuration planes. Trois implémentations différentes de la preuve par ordinateur ont été réalisées, montrant par là que le résultat est facilement reproductible.

La valeur de $f(N)$ pour $N>6$ est inconnue ; on sait seulement, par le résultat de Modèle:Harvsp énoncé plus haut, qu'elle est finie. Sur la base des valeurs de $f(N)$ connues alors pour $N=3,4$, et $5$, Erdős et Szekeres formulent dans leur article la conjecture suivante: Modèle:Théorème Ils ont prouvé ultérieurement, dans Modèle:Harvsp que

$f(N)\ge 1+2^{N-2},$

par la construction d'exemples. La majoration

$f(N)\le (\genfrac{}{}{0ex}{}{2N-5}{N-2})+1=O\left(\frac{4^N}{\sqrt{N}}\right)$

pour $N>6$ est due à Modèle:Harvsp.

Polygones vides

Une variante du problème, proposée par Paul Erdős dans Modèle:Harvsp est de déterminer si un ensemble de points suffisamment grand en position générale contient un quadrilatère, pentagone, etc. Modèle:Citation, c'est-à-dire ne contenant pas d'autre point de l'ensemble en son intérieur. On peut modifier la solution du Modèle:Anglais initial pour montrer que cinq points en position générale ont un quadrilatère convexe vide, comme montré dans la première figure, et que dix points contiennent un pentagone convexe vide. Toutefois, il existe des ensembles arbitrairement grands de points en position générale qui ne contiennent pas d'heptagone videModèle:,.

Pendant longtemps, l'existence d'un hexagone convexe vide est restée ouverte, puis Modèle:Harvsp et Modèle:Harvsp ont prouvé que tout ensemble assez grand de points en position générale contient un hexagone convexe vide. Plus précisément, Gerken a montré que le nombre, traditionnellement noté $h(6)$, de points requis vérifie $h(6)\le f(9)\le 1717$, avec $f(N)$ défini plus haut, alors que Nicolás a montré que $h(6)\le f(25)$. Valtr (2008) simplifie la preuve de Gerken au prix du remplacement de $f(9)$ par $f(15)$. Le nombre de points doit être au moins 30 ; en effet, Modèle:Harvsp donnent un ensemble de 29 point en position générale sans hexagone convexe vide. Modèle:Harvsp améliore la borne supérieure, de sorte que l'encadrement de $h(6)$ est $30\le h(6)\le 463$. En 2024, l'article de Modèle:Harvsp répond finalement à la question en montrant, à l'aide d'un solveur SAT, que $h(6)=30$.

Problèmes voisins

Trouver des ensembles de $n$ points qui minimisent le nombre de quadrilatères convexes est équivalent au problème de minimiser le nombre de croisements dans un tracé du graphe complet par segments de droites. Le nombre de quadrilatères est proportionnel à la quatrième puissance de $n$, mais la constante de proportionnalité n'est pas connue.

Il est facile de montrer que, dans un espace euclidien de dimension supérieure, des ensembles assez grands de points contiennent toujours $k$ points qui forment un polytope convexe, pourvu que $k$ soit supérieur à la dimension ; ceci résulte immédiatement de l'existence polygones convexes à $k$ sommets dans tout ensemble assez grand de points dans le plan, par une projection de l'ensemble de points de départ dans un quelconque sous-espace de dimension deux. Toutefois, le nombre de points nécessaires pour trouver k points en position convexe peut être inférieur, dans les dimensions plus élevées, que dans le plan, et on peut trouver des sous-ensembles satisfaisant à des contraintes additionnelles. En particulier, en dimension $d$, tout ensemble de $d+3$ points en position générale contient un sous-ensemble de $d+2$ points qui forment un Modèle:Lien. Plus généralement, pour tout $d$ et pour tout $k>d$, il existe un entier $m(d,k)$ tel que tout ensemble de $m(d,k)$ points en position générale admet un sous-ensemble de $k$ points qui forment un Modèle:Lien, c'est-à-dire tel que tout ensemble de $d$ sommets ou moins forme une face.

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article. Réimpression Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Chapitre.
• Modèle:Article

Liens externes

• Happy ending problem et Ramsey-theoretic proof of the Erdős-Szekeres theorem sur PlanetMath
• Modèle:MathWorld
• Modèle:Lien web