théorème de Sylvester-Gallaï

Placez quelques points sur une feuille. S'ils ne sont pas tous sur une même droite, le théorème assure qu'au moins une droite relie exactement deux de ces points, sans en rencontrer un troisième. Cette droite est dite ordinaire.

Le résultat est surprenant parce qu'il ne demande pas que les points soient en position générale : plusieurs peuvent être alignés. Il suffit que l'ensemble soit fini et qu'au moins trois points ne soient pas tous alignés.

Le théorème de Sylvester-Gallaï concerne un ensemble fini de points du plan. Une droite déterminée par cet ensemble passe par au moins deux de ses points. Elle est ordinaire lorsqu'elle en contient exactement deux.

Deux situations s'excluent : soit tous les points appartiennent à une même droite, soit l'ensemble détermine au moins une droite ordinaire. Des alignements partiels restent donc autorisés. En revanche, la finitude est essentielle : l'énoncé ne vaut pas pour tous les ensembles infinis de points.

Le problème fut posé par James Joseph Sylvester en 1893, repris indépendamment par Paul Erdős en 1943 et résolu par Tibor Gallai en 1944. Eberhard Melchior avait établi en 1940 un résultat équivalent par une autre approche. Son résultat donne même au moins trois droites ordinaires lorsque les points ne sont pas tous alignés.

Si un ensemble contient un nombre fini de points du plan et si ces points ne sont pas tous colinéaires, alors il existe une droite qui passe par exactement deux points de l'ensemble. Cette droite est une droite ordinaire.

Autrement dit, malgré d'éventuels alignements de trois points ou davantage, une configuration finie non entièrement alignée possède toujours au moins une liaison à deux points seulement.

L'ensemble étudié doit contenir un nombre fini de points, tous situés dans le plan. Pour obtenir la conclusion utile, il faut aussi vérifier qu'ils ne sont pas tous sur une même droite. Aucune hypothèse n'interdit cependant que trois points, ou davantage, soient alignés sur certaines droites.

Si tous les points sont alignés, leur droite commune en contient plus de deux dès que l'ensemble compte au moins trois points : la branche « droite ordinaire garantie » ne s'applique pas. Avec un ensemble infini, il faut employer un résultat adapté, car ce théorème ne fournit aucune garantie.

Considérons quatre points A, B, C et D. Les points A, D et B sont alignés dans cet ordre, tandis que C est hors de leur droite. La configuration permet de voir simultanément une droite non ordinaire et les droites ordinaires garanties.

Étape 1. La droite passant par A et B contient aussi D : elle rencontre donc trois points de l'ensemble et n'est pas ordinaire.
Étape 2. La droite AC ne contient que A et C : elle est ordinaire.
Étape 3. Les droites BC et CD contiennent elles aussi exactement deux des quatre points : elles sont ordinaires.

On obtient ainsi trois droites ordinaires, AC, BC et CD. Le contrôle consiste à reprendre chaque paire de points et à vérifier quels autres points se trouvent sur sa droite : les trois paires formées parmi A, D et B donnent toutes la même droite à trois points.

Dans un exercice de géométrie combinatoire, commencez par vérifier la finitude de la configuration et l'absence d'alignement total. Cherchez ensuite une droite contenant exactement deux points, plutôt que d'exiger qu'aucun triplet ne soit aligné.

Pour contrôler un dessin fini, examinez les droites déterminées par les paires de points et comptez les points placés sur chacune. Si une droite en porte exactement deux, la recherche est terminée ; si tous les points partagent une même droite, retenez l'autre branche de l'énoncé.

Lorsque l'on veut davantage qu'une simple existence, le résultat de Melchior est plus informatif : dans le même cadre non aligné, il garantit au moins trois droites ordinaires.

Droite ordinaire et droite déterminée. Une droite déterminée passe par au moins deux points de l'ensemble ; elle n'est ordinaire que si elle en contient exactement deux. Dans l'exemple, AB est déterminée mais non ordinaire, car D appartient aussi à AB.

Points non tous colinéaires et absence de trois points alignés. La première condition permet des alignements partiels ; la seconde les interdit tous. Les points A, D et B de l'exemple sont alignés, mais l'ensemble n'est pas entièrement colinéaire puisque C est hors de leur droite.

Alignement total. Si tous les points appartiennent à une même droite, on se trouve dans la première branche du théorème. Il ne faut pas conclure que cette droite est ordinaire lorsqu'elle contient trois points ou davantage.

Ensemble infini. La finitude n'est pas un détail technique que l'on peut retirer : le théorème ne s'étend pas aux ensembles infinis. Une configuration infinie exige donc un autre énoncé et une vérification propre de ses hypothèses.

Garantie minimale. Le théorème affirme l'existence d'au moins une droite ordinaire, pas que toute paire de points en définit une. Le résultat de Melchior renforce ce seuil à au moins trois droites ordinaires lorsque l'ensemble fini n'est pas entièrement aligné.

Le résultat de Melchior conduit à étudier non plus seulement l'existence, mais le nombre de droites déterminées par une configuration. Pour un ensemble fini E de n points, ce nombre ne dépasse pas $\left(\genfrac{}{}{0px}{}{n}{2}\right)=\frac{n(n-1)}{2}\backslash binom\{n\}\{2\}=\backslash frac\{n(n-1)\}\{2\}$. Cette borne élémentaire vient du fait que chaque droite déterminée contient au moins une paire de points, tandis que plusieurs paires alignées peuvent définir la même droite.

L'histoire du problème éclaire aussi la circulation des idées : question de Sylvester en 1893, résultat équivalent de Melchior en 1940, reprise indépendante par Erdős en 1943, puis résolution par Gallai en 1944.