Voir la source de Théorème de Sylvester-Gallai

En [[géométrie discrète]], le '''théorème de Sylvester-Gallai''' affirme qu'étant donné un [[ensemble fini]] de points du [[Plan (mathématiques)|plan]], on a l'alternative suivante :

* soit tous les points sont [[alignement (géométrie)|alignés]],
* soit il existe une droite qui contient exactement deux de ces points.

Les droites contenant exactement deux points sont nommées ''droites ordinaires''. Ce théorème ne s'applique pas à des ensembles [[infini]]s de points : il suffit pour s'en convaincre de considérer l'ensemble des points de coordonnées entières dans le plan euclidien.

== Historique ==
Ce [[théorème]] est issu d'un problème initialement posé par [[James Joseph Sylvester]]<ref>{{article|lang=en|nom=J. J. Sylvester|titre=Mathematical question 11851|revue=Educational [[The Times|Times]]|volume=59|année=1893|p.=98}}</ref>, qui fut reposé indépendamment par [[Paul Erdős]]<ref>{{article|lang=en|nom1=P. Erdős|titre=Problem 4065|revue=[[American Mathematical Monthly|Amer. Math. Month.]]|volume=50|numéro=1|année=1943|p.=65–66|doi=10.2307/2304011}}</ref>. Il fut résolu par [[Tibor Gallai]] en 1944<ref>La preuve de Gallai fut d'abord publiée parmi d'autres preuves de divers autres auteurs ({{article|lang=en|lien auteur1=Robert Steinberg|prénom=R.|nom=Steinberg|nom2=R. C. Buck|nom3=T. Grünwald (Tibor Gallai)|lien auteur4=Norman Steenrod|prénom4=N. E.|nom4=Steenrod|titre=Three point collinearity  (solution to problem 4065)|revue=Amer. Math. Month.|volume=51|numéro=3|année=1944|p.=169–171|doi = 10.2307/2303021}}). La priorité lui est cependant accordée, car, comme le notent les publicateurs de la solution, elle fut soumise associée au problème posé par Erdős.</ref>, même si un théorème équivalent avait déjà été montré par {{Lien|langue=en|fr=Eberhard Melchior}}<ref>{{article|lang=de|nom=E. Melchior|année=1940|titre=Über Vielseite der Projektive Ebene|revue={{Lien|lang=de|Deutsche Mathematik|texte=Deutsche Math.}}|volume=5|p.=461–475}}</ref>.

== Point de vue projectif et problème dual ==

Le même problème peut être posé dans le [[plan projectif]] réel plutôt que dans le [[Géométrie euclidienne|plan euclidien]]. Le problème projectif ne généralise en rien le problème euclidien, car tout ensemble fini de points projectifs peut être ramené à un ensemble de points du plan euclidien par une transformation conservant les droites ordinaires. Le point de vue projectif permet cependant de décrire plus naturellement et donc plus facilement certaines configurations, par exemple la configuration de McKee, décrite plus bas.

Par [[Dualité (géométrie projective)|dualité projective]], l'existence d'une droite ordinaire associée à un ensemble fini de points non alignés du plan projectif est équivalente à l'existence d'un ''point ordinaire'', c'est-à-dire un point d'intersection d'exactement deux droites, dans un ensemble de droites qui ne passent pas toutes par un point commun.

Melchior a montré en 1940, avant la preuve de Gallai, que tout ensemble fini de droites non [[concourant]]es présente au moins trois points ordinaires. Il s'est servi de la [[caractéristique d'Euler]] pour montrer que tout tel arrangement de droites a au moins trois sommets de degré 4 ; par dualité, tout ensemble de points non alignés possède donc au moins trois droites ordinaires.

== Démonstration ==
[[Fichier:Tibor gallai2.svg|droite|vignette]]

La preuve suivante<ref>Pour la preuve originale de Gallai, se reporter à {{article|lang=en|lien auteur=Peter Borwein|prénom=P.|nom= Borwein|nom2=W. O. J. Moser|titre=A survey of Sylvester's problem and its generalizations|revue=Aequationes Mathematicae|volume=40|numéro=1|année=1990|doi=10.1007/BF02112289|p.=111–135}}.</ref> est due à {{Lien|langue=en|fr=Leroy Milton Kelly}}<ref>{{article|lang=en|nom=L. M. Kelly|titre=A resolution of the Sylvester–Gallai problem of J. P. Serre|revue=Discrete Comput. Geom.|volume=1| numéro=1|p.=101–104|doi=10.1007/BF02187687|année=1986}}.</ref> et repose sur la [[méthode de descente infinie]].

Supposons donné un ensemble fini de points du plan, non alignés (en particulier, cet ensemble contient au moins trois points). Nous appellerons ''droite de connexion'' toute droite qui contient au moins deux points de l'ensemble. Il s'agit de montrer qu'au moins une de ces droites de connexion contient exactement deux points.

La grandeur utilisé pour la méthode de la descente infinie sera le minimum des distances entre chaque droite de connexion et tous les points extérieurs à celles-ci.

Supposons donc que notre ensemble de points n'est pas aligné, et soit ''(P,l)'' un point et une droite de connexion de distance minimale strictement positive parmi tous les points et les droites de connexion.
Par hypothèse, ''l'' contient alors trois points, notés ''A'', ''B'' et ''C''. On considère la perpendiculaire à ''l'' passant par P. Il doit y avoir au moins deux points se trouvant d'un côté de la perpendiculaire. Considérons que ''C'' est le point le plus éloigné et ''B'' le point le moins éloigné de la perpendiculaire. Considérons alors la droite de connexion ''m'' passant par ''C'' et ''P''. ''m'' est alors une droite de connexion qui ne contient pas ''B'' et la distance séparant ''B'' de ''m'' est strictement inférieure à la distance séparant ''P'' de ''l''. En effet, si l'on considère les projections, le triangle rectangle hypoténuse ''BC'' est [[Triangle semblable|semblable]] à celui d'hypoténuse ''PC'', et strictement inclus dans celui-ci.

Ainsi nous avons montré qu'il est toujours possible sous l'hypothèse initiale de trouver un point de notre ensemble avec une distance minimale aux ''droites de connexions'' strictement inférieur à un point donné. Ceci mène à une contradiction, puisqu'il y a un nombre fini de telles distances.

== Généralisations ==

[[Image:Few-ordinary-lines.png|vignette|upright=1.7|Les deux configurations connues de n points présentant moins de n/2 droites ordinaires.]]
Si le théorème de Sylvester-Gallai affirme l'existence d'au moins une droite de connexion contenant exactement deux points (''droite ordinaire''), on ne connaît pas d'arrangement de points tel qu'il n'existe qu'une seule droite ordinaire ; le résultat de Melchior montre que, si les points ne sont pas tous alignés, il existe au moins trois droites ordinaires.

Ceci conduisit [[Gabriel Andrew Dirac|Gabriel Dirac]] à émettre la conjecture<ref>{{article|lang=en|nom=G. Dirac|titre=Collinearity properties of sets of points|revue=Quart. J. Math.|année=1951|volume=2|p.=221–227|doi=10.1093/qmath/2.1.221}}</ref> affirmant que pour tout ensemble de ''n ''points non alignés, il existe au moins {{Fraction|n|2}} droites ordinaires. En 2006, cette conjecture est démentie par seulement deux contre-exemples :
* Le premier, trouvé par Kelly et Moser<ref>{{article|lang=en|nom1=L. M. Kelly|nom2=W. O. J. Moser|titre=On the number of ordinary lines determined by ''n'' points|revue=Canad. J. Math.|volume=10|année=1958|p.=210–219|doi=10.4153/CJM-1958-024-6}}</ref>, est composé par les sommets, les milieux d'arêtes, et le centre d'un triangle équilateral ; ces sept points déterminent seulement trois droites ordinaires. La configuration dans laquelle ces trois droites ordinaires se confondent en une seule droite ne peut être réalisée dans le plan euclidien, mais forme un [[géométrie projective|plan projectif]] fini connu sous le nom de [[plan de Fano]].
* L'autre contre-exemple, imaginé par McKee<ref>{{article|lang=en|doi=10.2307/2687957|nom1=D. W. Crowe|nom2=T. A. McKee|titre=Sylvester's problem on collinear points|revue=[[Mathematics Magazine]]|volume=41|numéro=1|année=1968|p.=30–34}}</ref>, est constitué des sommets de deux pentagones réguliers ayant une arête commune, du milieu de cette arête, et de quatre points à l'infini (c'est-à-dire situés sur la droite à l'infini dans le [[plan projectif]]). Ces 13 points déterminent 6 droites ordinaires. Il est possible de déformer cette configuration de manière à ramener tous les points dans le plan euclidien usuel.

Une version plus faible de la conjecture de Dirac a été prouvée par Csima et Sawyer<ref>{{article|lang=en|nom1=J. Csima|nom2=E. Sawyer|titre=There exist 6''n''/13 ordinary points|revue=Discrete Comput. Geom.|année=1993|volume=9|p.=187–202|doi=10.1007/BF02189318}}</ref>. Elle énonce que dans n'importe quel ensemble de ''n'' points, il y a au moins <math>\scriptstyle\left\lceil \frac{6n}{13}\right\rceil</math> droites ordinaires.

Un résultat proche du théorème de Sylvester-Gallai est le [[théorème de Beck]], qui affirme qu'un ensemble de points du plan présente soit un grand nombre de droites de connexion, soit un grand sous-ensemble maximal de points alignés.

== Aspects algorithmiques ==
Un algorithme de Mukhopadhyay et ''al.''<ref>{{article|lang=en|nom1=A. Mukhopadhyay|nom2=A. Agrawal|nom3=R. M. Hosabettu|titre=On the ordinary line problem in computational geometry|revue=Nordic Journal of Computing|volume=4|numéro=4|année=1997|p.=330–341}}</ref>{{,}}<ref>{{chapitre|lang=en|nom1=A. Mukhopadhyay|nom2=E. Greene|titre=The ordinary line problem revisited|titre ouvrage=Proc. 19th Canadian Conference on Computational Geometry|passage=61–64|url=http://cccg.ca/proceedings/2007/03a4.pdf|année=2007}}</ref> permet de trouver une droite ordinaire dans un ensemble de ''n'' points en [[complexité en temps|temps O(''n'' log ''n'')]].

== Notes et références ==
{{Traduction/Référence|en|Sylvester–Gallai theorem|113319989|type=note}}
<references />

== Voir aussi ==
* {{Lien|langue=en|trad=Arrangement of lines|fr=Arrangement de droites}}
* [[Configuration (géométrie)]]
* {{Lien|langue=en|trad=Incidence (geometry)|fr=Incidence (géométrie)}}
* [[Théorème de De Bruijn-Erdős (géométrie d'incidence)]]
* [[Théorème de Don Chakerian]]
* {{Page h|Théorème de Sylvester|Théorèmes de Sylvester}}

== Liens externes ==
* Jonathan Chappelon, [https://images.math.cnrs.fr/Le-theoreme-de-Sylvester-Gallai.html « Le théorème de Sylvester-Gallai »], [[Images des mathématiques]], [[CNRS]], 2022

{{Portail|Géométrie}}

{{DEFAULTSORT:Theoreme Sylvester Gallai}}
[[Catégorie:Géométrie discrète]]
[[Catégorie:Théorème de géométrie|Sylvester Gallai]]