Happy Ending problem

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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 Happy Ending problem est un résultat de géométrie plane dont la formulation générale est la conjecture d'Erdős-Szekeres sur la relation entre la taille d'un ensemble de points en position générale et la taille de son plus grand polygone convexe.

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 (en) et Esther Klein (en). L'énoncé est le suivant :

Théorème — Tout ensemble de cinq points du plan en position générale[1] contient un sous-ensemble de quatre points qui forment les sommets d'un quadrilatère convexe.

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. Peterson 2000 contient une explication illustrée de cette preuve, et Morris et Soltan 2000 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 polygone convexe. La conjecture n'est pas prouvée, mais des bornes approchées sont connues.

Polygones plus grands[modifier | modifier le code]

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

Erdős et Szekeres 1935 prouvent la généralisation suivante :

Théorème — Pour tout entier N, tout ensemble assez grand de points du plan en position générale contient un sous-ensemble de N points qui forment les sommets d'un polygone convexe.

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 une polygone convexe à N sommets.

  • f(3)=3 évidemment.
  • 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 Erdős et Szekeres 1935, ceci a été prouvé en premier par E. Makai. La première preuve publiée figure dans Kalbfleisch, Kalbfleisch et Stanton 1970.
    La figure montre un ensemble de huit poins 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 Szekeres et Peters 2006. 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 Erdős et Szekeres 1935 é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 :

Conjecture d'Erdős-Szekeres — Soit f(N) le plus petit des entiers m tels qu'un ensemble de m points en position générale contient une polygone convexe à N sommets. Alors on a

f(N) = 1 + 2^{N-2}

pour N \geq 3.

Ils ont prouvé ultérieurement, dans Erdős et Szekeres 1961 que

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

par la construction d'exemples. La majoration

f(N) \leq \binom{2N-5}{N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right)

pour N > 6 est due à Tóth et Valtr 2005.

Polygones vides[modifier | modifier le code]

Une variante du problème, proposée par Paul Erdős dans Erdős 1978 est de déterminer si un ensemble de points suffisamment grand en position générale contient un quadrilatère, pentagone, etc. « vide », c'est-à-dire ne contenant pas d'autre point de l'ensemble en son intérieur. On peut modifier la solution du Happy Ending Problem 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[2]. Toutefois, il existe des ensembles arbitrairement grands de points en position générale qui ne contiennent pas d'heptagone vide[3].

Pendant longtemps, l'existence d'un hexagone convexe vide est restée ouverte, puis Nicolás 2007 et Gerken 2008 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, Overmars 2003 donnent un ensemble de 29 point en position générale sans hexagone convexe vide. Koshelev 2007 améliore la borne supérieure, de sorte que l'encadrement de h(6) est 30 \le h(6) \le 463.

Problèmes voisins[modifier | modifier le code]

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 (en) 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[4].

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 les somment d'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 les sommets d'un polytope cyclique (en)[5]. 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 les sommets d'un "neighborly polytope" (en), c'est-à-dire tel que tout ensemble de d sommets ou moins forme une face[6].

Notes[modifier | modifier le code]

  1. Dans ce contexte, cela signifie que les points sont deux-à-deux distincts, et que trois points quelconques ne sont pas alignés.
  2. Harborth 1978.
  3. Horton 1983.
  4. Scheinerman et Wilf 1994.
  5. Grünbaum 2003, Ex. 6.5.6, p. 120. Grünbaum attribue ce résultat à une communication privée de Micha A. Perles.
  6. Grünbaum 2003, Ex. 7.3.6, p. 126. Ce résultat suit par un argument à la Ramsey similaire à celui employé dans la preuve originale de Szekeres, et du résultat de Perles dans le cas k=d+2.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Happy Ending problem » (voir la liste des auteurs)

Bibliographie[modifier | modifier le code]

  • (en) Fan R. K. Chung et Ronald L. Graham, « Forced convex n-gons in the plane », Discrete and Computational Geometry, vol. 19, no 3,‎ 1998, p. 367–371 (DOI 10.1007/PL00009353).
  • (en) Paul Erdős et George Szekeres, « A combinatorial problem in geometry », Compositio Mathematica, vol. 2,‎ 1935, p. 463–470 (lire en ligne).
  • (en) Paul Erdős et George Szekeres, « On some extremum problems in elementary geometry », Ann. Univ. Sci. Budapest. Eötvös Sect. Math., vol. 3–4,‎ 1961, p. 53–62. Réimpression The Art of Counting: Selected Writings, MIT Press,‎ 1973, p. 680–689.
  • (en) Paul Erdős, « Some more problems on elementary geometry », Australian Mathematical Society Gazette, vol. 5,‎ 1978, p. 52–54.
  • (en) Tobias Gerken, « Empty convex hexagons in planar point sets », Discrete and Computational Geometry, vol. 39, no 1–3,‎ 2008, p. 239–272 (DOI 10.1007/s00454-007-9018-x).
  • (en) Branko Grünbaum, Convex Polytopes, Springer-Verlag, coll. « Graduate Texts in Mathematics » (no 221),‎ 2003 (ISBN 0-387-00424-6).
  • (de) Heiko Harborth, « Konvexe Fünfecke in ebenen Punktmengen », Elem. Math., vol. 33, no 5,‎ 1978, p. 116–118.
  • (en) Joseph D. Horton, « Sets with no empty convex 7-gons », Canadian Mathematical Bulletin, vol. 26, no 4,‎ 1983, p. 482–484 (DOI 10.4153/CMB-1983-077-8).
  • (en) John D. Kalbfleisch, James G. Kalbfleisch et Ralph Gordon Stanton, « A combinatorial problem on convex regions », dans Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, vol. 1, Baton Rouge, La., Louisiana State Univ.,‎ 1970, p. 180–188.
  • (en) Daniel J. Kleitman et Lior Pachter, « Finding convex sets among points in the plane », Discrete and Computational Geometry, vol. 19, no 3,‎ 1998, p. 405–410 (DOI 10.1007/PL00009358).
  • (en) V. A. Koshelev, « The Erdős-Szekeres problem », Dokl. Math., vol. 76, no 1,‎ 2007, p. 603–605 (DOI 10.1134/S106456240704031X).
  • (en) Walter Morris et Valeriu Soltan, « The Erdős-Szekeres problem on points in convex position — A survey », Bulletin of the American Mathematical Society, vol. 37, no 4,‎ 2000, p. 437–458 (DOI 10.1090/S0273-0979-00-00877-6, lire en ligne).
  • (en) Carlos M. Nicolás, « The empty hexagon theorem », Discrete and Computational Geometry, vol. 38, no 2,‎ 2007, p. 389–397 (DOI 10.1007/s00454-007-1343-6).
  • (en) Mark Overmars, « Finding sets of points without empty convex 6-gons », Discrete and Computational Geometry, vol. 29, no 1,‎ 2003, p. 153–158 (DOI 10.1007/s00454-002-2829-x).
  • (en) Ivars Peterson, « Planes of Budapest », MAA Online,‎ 2000 (lire en ligne).
  • (en) Edward R. Scheinerman et Herbert S. Wilf, « The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability », American Mathematical Monthly, Mathematical Association of America, vol. 101, no 10,‎ 1994, p. 939–943 (DOI 10.2307/2975158, JSTOR 2975158).
  • (en) George Szekeres et Lindsay Peters, « Computer solution to the 17-point Erdős-Szekeres problem », The ANZIAM Journal, vol. 48, no 2,‎ 2006, p. 151–164 (DOI 10.1017/S144618110000300X, lire en ligne).
  • (en) Géza Tóth et Pavel Valtr, « Note on the Erdős-Szekeres theorem », Discrete and Computational Geometry, vol. 19, no 3,‎ 1998, p. 457–459 (DOI 10.1007/PL00009363).
  • (en) Géza Tóth et Pavel Valtr, « The Erdős-Szekeres theorem: upper bounds and related results », dans Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications, no. 52,‎ 2005, p. 557–568.
  • (en) Pavel Valtr, « On empty hexagons », dans Surveys on discrete and computational geometry, Amer. Math. Soc., coll. « Contemp. Math. » (no 453),‎ 2008 (lire en ligne), p. 433–441.

Liens externes[modifier | modifier le code]