Théorème de Sylvester–Gallai

Un article de Wikipédia, l'encyclopédie libre.

Le théorème de Sylvester–Gallai affirme qu'étant donné un ensemble fini de points du plan, on a l'alternative suivante :

soit tous les points sont colinéaires,
soit il existe une droite qui contient exactement deux de ces points (droite ordinaire).

Ce théorème est issu d'un problème initialement posé par James Joseph Sylvester (1893), qui fut reposé indépendamment par Paul Erdős (1943). Il fut résolu par Tibor Gallai en 1944^[1], même si un théorème équivalent avait déjà été montré par Melchior en 1940.

Ce théorème ne s'applique pas à des ensembles infinis de points : il suffit pour s'en convaincre de considérer l'ensemble des points de coordonnées entières dans le plan euclidien.

Les droites contenant exactement deux points sont nommées droites ordinaires. Un algorithme de Mukhopadhyay et al. (1997) permet de trouver une droite ordinaire dans un ensemble de n points en temps O(n log n).

Sommaire

1 Point de vue projectif et problème dual
2 Démonstration du théorème de Sylvester–Gallai
3 Généralisations du théorème de Sylvester–Gallai
4 Références

[modifier] 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 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é projective, l'existence d'une droite ordinaire associée à un ensemble fini non colinéaire de points 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 de droites non globalement concordantes 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.

[modifier] Démonstration du théorème de Sylvester–Gallai

Pour la preuve originale de Gallai, se reporter à Borwein et Moser (1990). La preuve suivante est dûe à Kelly et repose sur la méthode de descente infinie.

Supposons donné un ensemble fini de points du plan, non colinéaires (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.

Soit l une droite de connexion. Si l contient seulement deux points, la démonstration est terminée. Sinon l contient au moins trois points, que nous appellerons A, B et C de manière telle que B se trouve entre A et C. D'autre part, les points de l'ensemble n'étant pas colinéaires, il existe au moins un point P qui n'appartient pas à l. Comme les angles $\widehat{ABP}$ et $\widehat{CBP}$ sont supplémentaires, l'un des deux est nécessairement aigu ou droit. On peut, sans perte de généralité, supposer que c'est $\widehat{ABP}$ . 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 résumé, nous avons démarré avec une droite de connexion l et un point P n'appartenant pas à l, et observé que soit l contient exactement deux points, soit il existe une droite de connexion m et un point B n'appartenant pas à m tels que la distance entre B et m soit strictement inférieure à la distance entre P et l. Dans ce dernier cas, nous répétons alors le procédé ci-dessus en remplaçant P et l par B et m. L'algorithme s'arrête car le nombre de distances possibles entre un point et une droite de connexion est fini car l'ensemble des points considéré est lui-même fini. Nous obtenons donc finalement une droite contenant exactement deux des points de l'ensemble.

[modifier] Généralisations du théorème de Sylvester–Gallai

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 à ce jour d'arrangement de points tel qu'il n'existe qu'une seule droite ordinaire.

Ceci conduisit Dirac à émettre la conjecture (1951) affirmant que pour tout ensemble de $n$ points, non tous colinéaires, il existe au moins ⁿ⁄₂ droites ordinaires. En 2006, cette conjecture est démentie par seulement deux contre-exemples :

Le premier, trouvé par Kelly et Moser (1958), 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 plan projectif fini connu sous le nom de plan de Fano.
L'autre contre-exemple, imaginé par McKee (Crowe et McKee 1968), 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 en 1993. Elle énonce que dans n'importe quel ensemble de n points, il y a au moins $\lceil \frac{6n}{13} \rceil$ 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 colinéaires.

[modifier] Références

↑ La preuve de Gallai fut d'abord publiée parmi d'autres preuves de divers autres auteurs (Steinberg et al 1944). 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.