Voir la source de Happy Ending problem

{{Voir homonymes|Happy Ending (homonymie)}}
[[Fichier:Happy-End-problem.svg|vignette|Le problème de la fin heureuse : tout ensemble de cinq points en position générale contient les sommets d'un [[quadrilatère]] [[polygone convexe|convexe]].]]

Le '''{{langue|en|happy ending problem}}''', ou '''{{langue|en|happy end problem}}''', 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 Szekeres|Esther Klein]]. L'énoncé est le suivant :

{{Théorème|Théorème|Tout ensemble de cinq points du plan en position générale<ref>Dans ce contexte, cela signifie que les points sont deux-à-deux distincts, et que trois points quelconques ne sont pas alignés.</ref> contient un sous-ensemble de quatre points qui forment 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. {{harvsp|Peterson|2000}} contient une explication illustrée de cette preuve, et {{harvsp|Morris|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 sous-ensemble formant un polygone convexe. La [[conjecture]] n'est pas prouvée, mais des bornes approchées sont connues.

== Polygones plus grands ==
[[Fichier:8-points-no-pentagon.svg|vignette|Un ensemble de huit points en position générale sans [[pentagone]] convexe.]]
{{harvsp|Erdős|Szekeres|1935}} prouvent la généralisation suivante<ref name = "delahaye">{{Article|langue = français|titre = À la recherche de l'ordre caché|auteur = [[Jean-Paul Delahaye]]|périodique = [[Pour la Science]]|numéro = 553|mois = novembre|année = 2023}}.</ref>:

{{Théorème|Théorème|Pour tout entier <math>N</math>, tout ensemble assez grand de points du plan en position générale contient un sous-ensemble de <math>N</math> points qui forment 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 <math>f(N)</math> le plus petit des entiers <math>m</math> tels qu'un ensemble de <math>m</math> points en position générale contient un polygone convexe à <math>N</math> sommets.
* <math>f(3)=3</math> trivialement ;
* <math>f(4)=5</math>. Ceci est le problème d'origine, résolu par Esther Klein et traité plus haut<ref name = "delahaye"/>;
* <math>f(5)=9</math>. D'après {{harvsp|Erdős|Szekeres|1935}}, ceci a été prouvé en premier par E. Makai et Pál Turán<ref name = "delahaye"/>. La première preuve publiée figure dans {{harvsp|Kalbfleisch|Kalbfleisch|Stanton|1970}}.<br />La figure montre un ensemble de huit points sans [[pentagone]] convexe, ce qui montre que <math>f(5) > 8</math> ; 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 ;
* <math>f(6)=17</math>. Cette égalité a été démontrée dans {{harvsp|Szekeres|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<ref name = "delahaye"/>.

La valeur de <math>f(N)</math> pour <math>N > 6</math> est inconnue ; on sait seulement, par le résultat de {{harvsp|Erdős|Szekeres|1935}} énoncé plus haut, qu'elle est finie<ref name = "delahaye"/>. Sur la base des valeurs de <math>f(N)</math> connues alors pour <math>N=3, 4</math>, et <math>5</math>, Erdős et Szekeres formulent dans leur article la conjecture suivante<ref name = "delahaye"/>:
{{théorème|Conjecture d'Erdős-Szekeres|Soit <math>f(N)</math> le plus petit des entiers <math>m</math> tels qu'un ensemble de <math>m</math> points en position générale contient une polygone convexe à <math>N</math> sommets. Alors on a
:<math>f(N) = 1 + 2^{N-2}</math>
pour <math>N \geq 3</math>.}}
Ils ont prouvé ultérieurement, dans {{harvsp|Erdős|Szekeres|1961}} que
:<math>f(N) \geq 1 + 2^{N-2},</math>
par la construction d'exemples<ref name = "delahaye"/>.
La majoration
:<math>f(N) \leq \binom{2N-5}{N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right)</math>
pour <math>N > 6</math> est due à {{harvsp|Tóth|Valtr|2005}}.

== Polygones vides ==
Une variante du problème, proposée par Paul Erdős dans {{harvsp|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. {{Citation|vide}}, c'est-à-dire ne contenant pas d'autre point de l'ensemble en son intérieur. On peut modifier la solution du {{anglais|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<ref>{{harvsp|Harborth|1978}}.</ref>. Toutefois, il existe des ensembles arbitrairement grands de points en position générale qui ne contiennent pas d'[[heptagone]] vide<ref name = "delahaye"/>{{,}}<ref>{{harvsp|Horton|1983}}.</ref>.

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

== Problèmes voisins ==

Trouver des ensembles de <math>n</math> points qui minimisent le nombre de quadrilatères convexes est équivalent au problème de minimiser le [[Nombre de croisements (théorie des graphes)|nombre de croisements]] dans un [[tracé de graphes|tracé]] du [[graphe complet]] par segments de droites. Le nombre de quadrilatères est proportionnel à la quatrième puissance de <math>n</math>, mais la constante de proportionnalité n'est pas connue<ref>{{harvsp|Scheinerman|Wilf|1994}}.</ref>.

Il est facile de montrer que, dans un [[espace euclidien]] de dimension supérieure, des ensembles assez grands de points contiennent toujours <math>k</math> points qui forment un [[polytope convexe]], pourvu que <math>k</math> soit supérieur à la dimension ; ceci résulte immédiatement de l'existence polygones convexes à <math>k</math> 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 <math>d</math>, tout ensemble de <math>d+3</math> points en position générale contient un sous-ensemble de <math>d+2</math> points qui forment un {{Lien|trad=Cyclic polytope|langue=en|fr=polytope cyclique}}<ref>{{harvsp|Grünbaum|2003}}, Ex. 6.5.6, {{p.}}120. Grünbaum attribue ce résultat à une communication privée de Micha A. Perles.</ref>. Plus généralement, pour tout <math>d</math> et pour tout <math>k > d</math>, il existe un entier <math>m(d,k)</math> tel que tout ensemble de <math>m(d,k)</math> points en position générale admet un sous-ensemble de <math>k</math> points qui forment un {{Lien|trad=neighborly polytope|langue=en|fr=neighborly polytope|texte="neighborly polytope"}}, c'est-à-dire tel que tout ensemble de <math>d</math> sommets ou moins forme une face<ref>{{harvsp|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 <math>k=d+2</math>.</ref>.

== Notes ==
{{Références|colonnes=2}}
{{Traduction/Référence|en|Happy Ending problem|476268519|type=note}}

== Bibliographie ==
* {{Article
 | langue = en
|auteur=[[Fan Chung|Fan R. K. Chung]]
|auteur2=[[Ronald Graham|Ronald L. Graham]]
 | doi = 10.1007/PL00009353
|revue=[[Liste des journaux scientifiques en mathématiques#D|Discrete Comput. Geom.]]
 | pages = 367-371
 | numéro = 3
 | titre = Forced convex n-gons in the plane
 | volume = 19
 | année = 1998}}.
* {{Article
 | langue = en
|auteur=Paul Erdős
|auteur2=George Szekeres
|revue=[[Liste des journaux scientifiques en mathématiques#C|Compos. Math.]]
 | pages = 463-470
 | titre = A combinatorial problem in geometry
 | url = http://www.numdam.org/item?id=CM_1935__2__463_0
 | volume = 2
 | année = 1935}}.
* {{Article
 | langue=en
|auteur=Paul Erdős
|auteur2=George Szekeres
 | périodique = Ann. Univ. Sci. Budapest. Eötvös Sect. Math.
 | pages = 53-62
 | titre = On some extremum problems in elementary geometry
 | volume = 3-4
 | année = 1961}}. Réimpression {{Ouvrage| titre=The Art of Counting| sous-titre=Selected Writings| éditeur=[[MIT]] Press| année=1973| passage=680-689}}.
* {{Article
 | langue=en
|auteur=Paul Erdős
|revue=[[Société australienne de mathématiques|Aust. Math. Soc.]] Gaz.
 | pages = 52-54
 | titre = Some more problems on elementary geometry
 | volume = 5
 | mr=80b:52005
 | année = 1978}}.
* {{Article
 | langue=en
 | nom1 = Gerken | prénom1 = Tobias
 | doi = 10.1007/s00454-007-9018-x
 | numéro = 1-3
 | périodique=Discrete Comput. Geom.
 | pages = 239-272
 | titre = Empty convex hexagons in planar point sets
 | volume = 39
 | année = 2008}}.
* {{Ouvrage
 | langue=en
 | auteur1=[[Branko Grünbaum]]
 | titre=Convex Polytopes
 | lieu=New York
 | éditeur=[[Springer-Verlag]]
 | collection=[[Graduate Texts in Mathematics|GTM]]
 | numéro dans collection=221
 | année=2003
 | numéro d'édition=2
 | pages totales=466
 | isbn=0-387-00424-6
}}.
* {{Article
 | langue = de
|auteur={{Lien|langue=en|fr=Heiko Harborth}}
 | numéro = 5
 | périodique = Elem. Math.
 | pages = 116-118
 | titre = Konvexe Fünfecke in ebenen Punktmengen
 | volume = 33
 | année = 1978|url=https://eudml.org/doc/141217}}.
* {{Article
 | langue = en
 | doi = 10.4153/CMB-1983-077-8
|auteur=Joseph D. Horton
 | numéro = 4
|revue=[[Canadian Mathematical Bulletin]]
 | pages = 482-484
 | titre = Sets with no empty convex 7-gons
 | volume = 26
 | année = 1983}}.
* {{Chapitre
 | langue = en
|auteur=John D. Kalbfleisch
|auteur2=James G. Kalbfleisch
|auteur3=Ralph G. Stanton
 | titre ouvrage= Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing
|éditeur=[[Université d'État de Louisiane]]
|lieu=[[Bâton-Rouge]]
 | series = [[Congressus Numerantium]]
 | passage = 180-188
 | titre chapitre = A combinatorial problem on convex regions
 | volume = 1
 | année = 1970}}.
* {{Article
 | langue = en
|auteur=[[Daniel Kleitman]]
|auteur2=Lior Pachter
 | doi = 10.1007/PL00009358
 | périodique=Discrete Comput. Geom.
 | pages = 405-410
 | numéro = 3
 | titre = Finding convex sets among points in the plane
 | volume = 19
 | année = 1998}}.
* {{Article
 | langue = en
|auteur=V. A. Koshelev
|revue=[[Doklady Akademii Nauk|Dokl. Math.]]
 | pages = 603-605
 | numéro = 1
 | titre = The Erdős-Szekeres problem
 | doi =  10.1134/S106456240704031X
 | volume = 76
 | année = 2007}}.
* {{Article
 | langue = en
|auteur=Walter Morris
|auteur2=Valeriu Soltan
 | doi = 10.1090/S0273-0979-00-00877-6
|revue=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]]
 | pages = 437-458
 | titre = The Erdős-Szekeres problem on points in convex position — A survey
 | numéro = 4
 | url = http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html
 | volume = 37
 | année = 2000}}.
* {{Article
 | langue = en
|auteur=Carlos M. Nicolás
 | doi = 10.1007/s00454-007-1343-6
 | numéro = 2
 | périodique=Discrete Comput. Geom.
 | pages = 389-397
 | titre = The empty hexagon theorem
 | volume = 38
 | année = 2007}}.
* {{Article
 | langue = en
|auteur=[[Mark Overmars]]
 | doi = 10.1007/s00454-002-2829-x
 | périodique=Discrete Comput. Geom.
 | pages = 153-158
 | titre = Finding sets of points without empty convex 6-gons
 | numéro = 1
 | volume = 29
 | année = 2003}}.
* {{Article
 | langue = en
|auteur={{Lien|langue=de|fr=Ivars Peterson}}
|revue=[[Mathematical Association of America|MAA]] Online
 | titre = Planes of Budapest
 | url = http://www.maa.org/mathland/mathtrek_10_3_00.html
 | année = 2000}}.
* {{Article
 | langue = en
|auteur=[[Edward Scheinerman|Edward R. Scheinerman]]
|auteur2=[[Herbert Wilf|Herbert S. Wilf]]
 | doi = 10.2307/2975158
 | numéro = 10
|périodique=[[American Mathematical Monthly|Am. Math. Monthly]]
 | pages = 939-943
 | titre = The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability
 | volume = 101
 | année = 1994
 | jstor = 2975158}}.
* {{Article
 | langue = en
|auteur=George Szekeres
|auteur2=Lindsay Peters
 | doi = 10.1017/S144618110000300X
 | périodique = The ANZIAM Journal
 | pages = 151-164
 | titre = Computer solution to the 17-point Erdős-Szekeres problem
 | numéro = 2
 | url = http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html
 | volume = 48
 | année = 2006}}.
* {{Article
 | langue = en
|auteur=Géza Tóth
|auteur2=Pavel Valtr
 | doi = 10.1007/PL00009363
 | périodique=Discrete Comput. Geom.
 | pages = 457-459
 | titre = Note on the Erdős-Szekeres theorem
 | numéro = 3
 | volume = 19
 | année = 1998}}.
* {{Chapitre
 | langue = en
|auteur=Géza Tóth
|auteur2=Pavel Valtr
 | titre chapitre = The Erdős-Szekeres theorem: upper bounds and related results
 | passage = 557-568
 | éditeur=[[MSRI]] Publications, no. 52
 | titre ouvrage = Combinatorial and Computational Geometry
 | année = 2005}}.
* {{Chapitre
 | langue = en
|auteur=Pavel Valtr
 | titre chapitre = On empty hexagons
 | passage = 433-441
|éditeur=[[American Mathematical Society|AMS]]
 | titre ouvrage = Surveys on Discrete and Computational Geometry
 | collection = Contemp. Math.
 | numéro dans collection = 453
 | mr = 2009h:52042
 | url = http://kam.mff.cuni.cz/~valtr/h.ps
 | année = 2008}}.
* {{Article|langue=en|prénom1=Marijn J. H.|nom1=Heule|prénom2=Manfred|nom2=Scheucher|titre=Happy Ending: An Empty Hexagon in Every Set of 30 Points|périodique=Tools and Algorithms for the Construction and Analysis of Systems|volume=14570|pages=61-80|éditeur=Springer-Verlag|date=2024|doi=10.1007/978-3-031-57246-3_5}}

== Liens externes ==
* [http://planetmath.org/encyclopedia/HappyEndingProblem.html Happy ending problem] et [http://planetmath.org/encyclopedia/RamseyTheoreticProofOfTheErdHosSzekeresTheorem.html Ramsey-theoretic proof of the Erdős-Szekeres theorem] sur [[PlanetMath]]
* {{MathWorld | nom-url = HappyEndProblem | titre = Happy End Problem}}
* {{lien web|url=http://images.math.cnrs.fr/Polygones-convexes-le-probleme-de.html|titre=Polygones convexes : le problème de la fin heureuse|auteur=Pierre-Alain Cherix, Shaula Fiorelli Vilmart et [[Pierre de la Harpe]]|date=28 novembre 2014|site=[[Images des mathématiques|Images des maths]]}}

{{Portail|géométrie}}

[[Catégorie:Géométrie discrète]]
[[Catégorie:Conjecture non résolue]]
[[Catégorie:Géométrie euclidienne]]