Théorème de Sylvester-Could

Sylvester–Gallai theorem Three of the ordinary lines in a 4 × 4 grid of points The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. Il porte le nom de James Joseph Sylvester, qui l'a posé comme problème dans 1893, et Tibor Gallaï, qui a publié une des premières preuves de ce théorème en 1944.

Une ligne qui contient exactement deux points d'un ensemble de points est appelée ligne ordinaire. Une autre façon d'énoncer le théorème est que chaque ensemble fini de points qui n'est pas colinéaire a une ligne ordinaire. D'après un renforcement du théorème, tout ensemble de points finis (pas tous sur une seule ligne) a au moins un nombre linéaire de lignes ordinaires. Un algorithme peut trouver une ligne ordinaire dans un ensemble de {displaystyle n} points dans le temps {style d'affichage O(loyer m)} .

Contenu 1 Histoire 2 Versions équivalentes 3 Preuves 3.1 La preuve de Kelly 3.2 Preuve de Melchior 3.2.1 L'inégalité de Melchior 3.3 Axiomatique 4 Trouver une ligne ordinaire 5 Le nombre de lignes ordinaires 6 Le nombre de lignes de connexion 7 Généralisations 7.1 Points de couleur 7.2 Coordonnées non réelles 7.3 Matroïdes 7.4 Géométrie des distances 8 Remarques 9 Références 10 External links History The Sylvester–Gallai theorem was posed as a problem by J. J. Sylvestre (1893). Kelly (1986) suggère que Sylvester pourrait avoir été motivé par un phénomène connexe en géométrie algébrique, dans laquelle les points d'inflexion d'une courbe cubique dans le plan projectif complexe forment une configuration de neuf points et de douze droites (la configuration hessoise) dans laquelle chaque ligne déterminée par deux des points contient un troisième point. Le théorème de Sylvester-Gallai implique qu'il est impossible que ces neuf points aient des coordonnées réelles.[1] H. J. Woodall (1893un, 1893b) prétendait avoir une courte preuve du théorème de Sylvester-Gallai, mais il a déjà été noté qu'il était incomplet au moment de la publication. Eberhard Melchior (1941) prouvé le théorème (et en fait un résultat légèrement plus fort) dans une formulation équivalente, son dual projectif. Ignorant la preuve de Melchior,[2] Paul Erdős (1943) a de nouveau énoncé la conjecture, qui a ensuite été prouvé par Tibor Gallai, et peu après par d'autres auteurs.[3] Dans un 1951 examen, Erdős a appelé le résultat "Théorème de pourrait",[4] mais il s'appelait déjà le théorème de Sylvester-Gallai dans un 1954 revue par Leonard Blumenthal.[5] C'est l'un des nombreux sujets mathématiques nommés d'après Sylvester.

Equivalent versions The question of the existence of an ordinary line can also be posed for points in the real projective plane RP2 instead of the Euclidean plane. Le plan projectif peut être formé à partir du plan euclidien en ajoutant des points supplémentaires "à l'infini" où les droites parallèles au plan euclidien se coupent, et en ajoutant une seule ligne "à l'infini" contenant tous les points ajoutés. Cependant, les points supplémentaires du plan projectif ne peuvent pas aider à créer des ensembles de points finis non euclidiens sans ligne ordinaire, car tout ensemble de points finis dans le plan projectif peut être transformé en un ensemble de points euclidiens avec le même modèle combinatoire d'incidences de points-lignes. Par conséquent, tout motif d'un nombre fini de points et de lignes d'intersection qui existe dans l'un de ces deux types de plan existe également dans l'autre. Néanmoins, le point de vue projectif permet de décrire plus facilement certaines configurations. En particulier, il permet l'utilisation de la dualité projective, dans lequel les rôles des points et des lignes dans les déclarations de géométrie projective peuvent être échangés les uns pour les autres. Sous dualité projective, l'existence d'une ligne ordinaire pour un ensemble de points non colinéaires dans RP2 est équivalente à l'existence d'un point ordinaire dans un arrangement non trivial d'un nombre fini de lignes. Un arrangement est dit trivial lorsque toutes ses droites passent par un point commun, et non trivial sinon; un point ordinaire est un point qui appartient exactement à deux droites.[2] Le dodécaèdre allongé, un zonoèdre. Ses huit faces rouges de parallélogramme correspondent aux points ordinaires d'un arrangement à cinq lignes; une forme équivalente du théorème de Sylvester-Gallai stipule que chaque zonoèdre a au moins une face de parallélogramme.

Les arrangements de lignes ont une structure combinatoire étroitement liée aux zonoèdres, polyèdres formés comme la somme de Minkowski d'un ensemble fini de segments de droite, appelés générateurs. Dans cette connection, chaque paire de faces opposées d'un zonoèdre correspond à un point de croisement d'un arrangement de droites dans le plan projectif, avec une ligne pour chaque générateur. Le nombre de côtés de chaque face est le double du nombre de lignes qui se croisent dans l'arrangement. Par exemple, le dodécaèdre allongé représenté est un zonoèdre à cinq générateurs, deux paires de faces hexagonales opposées, et quatre paires de faces de parallélogramme opposées. Dans l'arrangement à cinq lignes correspondant, deux triplets de lignes se croisent (correspondant aux deux paires d'hexagones opposés) et les quatre paires de lignes restantes se croisent en des points ordinaires (correspondant aux quatre paires de parallélogrammes opposés). Une déclaration équivalente du théorème de Sylvester-Gallai, en termes de zonoèdres, est que chaque zonoèdre a au moins une face de parallélogramme (compter les rectangles, losanges, et les carrés comme cas particuliers de parallélogrammes). Plus fortement, chaque fois que des ensembles de {displaystyle n} points dans le plan peuvent être garantis d'avoir au moins {style d'affichage t_{2}(n)} lignes ordinaires, zonoèdres avec {displaystyle n} les générateurs peuvent être garantis d'avoir au moins {style d'affichage 2t_{2}(n)} faces de parallogramme.[6] Proofs The Sylvester–Gallai theorem has been proved in many different ways. Ça pourrait 1944 la preuve bascule entre la géométrie euclidienne et la géométrie projective, afin de transformer les points en une configuration équivalente dans laquelle une droite ordinaire se retrouve comme une droite de pente la plus proche de zéro; pour les détails, see Borwein & Moser (1990). La 1941 la preuve de Melchior utilise la dualité projective pour convertir le problème en une question équivalente sur les arrangements de lignes, auquel on peut répondre en utilisant la formule polyédrique d'Euler. Une autre preuve de Leroy Milton Kelly montre par contradiction que la ligne de connexion avec la plus petite distance non nulle à un autre point doit être ordinaire. Et, suite à une preuve antérieure de Steinberg, H. S. M. Coxeter a montré que les concepts métriques de pente et de distance apparaissant dans les preuves de Gallai et Kelly sont inutilement puissants, à la place prouver le théorème en utilisant uniquement les axiomes de la géométrie ordonnée.

Kelly's proof Notation for Kelly's proof This proof is by Leroy Milton Kelly. Aigner & Ziegler (2018) appeler "simplement le meilleur" des nombreuses preuves de ce théorème.[7] Supposons qu'un ensemble fini {style d'affichage S} de points ne sont pas tous colinéaires. Définir une ligne de connexion comme étant une ligne contenant au moins deux points dans la collection. Par finitude, {style d'affichage S} doit avoir raison {style d'affichage P} et une ligne de liaison {style d'affichage ell } qui sont à une distance positive l'un de l'autre mais qui sont plus proches que toutes les autres paires point-ligne. Kelly a prouvé que {style d'affichage ell } est ordinaire, par contradiction.[7] Suppose que {style d'affichage ell } n'est pas ordinaire. Ensuite, il passe par au moins trois points de {style d'affichage S} . Au moins deux d'entre eux sont du même côté de {style d'affichage P'} , la projection perpendiculaire de {style d'affichage P} sur {style d'affichage ell } . Appelle les {style d'affichage B} et {displaystyle C} , avec {style d'affichage B} étant le plus proche de {style d'affichage P'} (et peut-être coïncider avec lui). Tracez la ligne de connexion {style d'affichage m} en passant par {style d'affichage P} et {displaystyle C} , et la perpendiculaire de {style d'affichage B} à {style d'affichage B'} sur {style d'affichage m} . Alors {style d'affichage BB'} est plus court que {style d'affichage PP'} . Cela découle du fait que {style d'affichage PP'C} et {style d'affichage BB'C} sont des triangles semblables, l'un contenu dans l'autre.[7] Cependant, cela contredit la définition originale de {style d'affichage P} et {style d'affichage ell } comme la paire point-ligne avec la plus petite distance positive. Donc l'hypothèse que {style d'affichage ell } n'est pas ordinaire ne peut pas être vrai, EST[7] Melchior's proof In 1941 (Donc, avant qu'Erdős ne publie la question et la preuve ultérieure de Gallai) Melchior a montré que tout arrangement fini non trivial de lignes dans le plan projectif a au moins trois points ordinaires. Par dualité, ce résultat indique également que tout ensemble fini non trivial de points sur le plan a au moins trois lignes ordinaires.[8] Melchior a observé que, pour tout graphe plongé dans le plan projectif réel, la formule {style d'affichage V-E+F} doit être égal {style d'affichage 1} , la caractéristique d'Euler du plan projectif. Ici {style d'affichage V} , {style d'affichage E} , et {style d'affichage F} sont le nombre de sommets, bords, et les faces du graphique, respectivement. Toute disposition de lignes non triviales sur le plan projectif définit un graphe dans lequel chaque face est délimitée par au moins trois arêtes, et chaque arête délimite deux faces; alors, le double comptage donne l'inégalité supplémentaire {style d'affichage Fleq 2E/3} . En utilisant cette inégalité pour éliminer {style d'affichage F} de la caractéristique d'Euler conduit à l'inégalité {afficheur Eleq 3V-3} . Mais si chaque sommet de l'arrangement était le point de croisement de trois lignes ou plus, alors le nombre total d'arêtes serait au moins {affichage 3V} , contredisant cette inégalité. Par conséquent, certains sommets doivent être le point de croisement de seulement deux lignes, et comme le montre l'analyse plus minutieuse de Melchior, il faut au moins trois sommets ordinaires pour satisfaire l'inégalité {afficheur Eleq 3V-3} .[8] As Aigner & Ziegler (2018) Remarque, le même argument pour l'existence d'un sommet ordinaire a également été donné dans 1944 de Norman Steenrod, qui l'ont explicitement appliqué au problème de la droite ordinaire duale.[9] Melchior's inequality By a similar argument, Melchior a pu prouver un résultat plus général. Pour chaque {style d'affichage kgeq 2} , laisser {style d'affichage t_{k}} soit le nombre de points auxquels {style d'affichage k} les lignes sont incidentes. Alors[8] {style d'affichage style d'affichage somme _{kgeq 2}(k-3)t_{k}leq -3.} ou équivalent, {style d'affichage style d'affichage t_{2}geqslant 3+somme _{kgeq 4}(k-3)t_{k}.} Axiomatics H. S. M. Coxeter (1948, 1969) écrit de la preuve de Kelly que son utilisation de la distance euclidienne est inutilement puissante, "comme utiliser une masse pour casser une amande". À la place, Coxeter a donné une autre preuve du théorème de Sylvester-Gallai dans la géométrie ordonnée, une axiomatisation de la géométrie en termes d'intermédiarité qui inclut non seulement la géométrie euclidienne mais plusieurs autres géométries apparentées.[10] La preuve de Coxeter est une variante d'une preuve antérieure donnée par Steinberg dans 1944.[11] Le problème de trouver un ensemble minimal d'axiomes nécessaires pour prouver le théorème appartient aux mathématiques inverses; voir pambuccian (2009) pour une étude de cette question.

L'énoncé habituel du théorème de Sylvester-Gallai n'est pas valide en analyse constructive, car il implique le principe moins limité de l'omniscience, une forme affaiblie de la loi du tiers exclu qui est rejetée comme axiome des mathématiques constructives. Néanmoins, il est possible de formuler une version du théorème de Sylvester-Gallai qui est valide dans les axiomes de l'analyse constructive, et d'adapter la preuve de Kelly du théorème pour être une preuve valide sous ces axiomes.[12] Finding an ordinary line Kelly's proof of the existence of an ordinary line can be turned into an algorithm that finds an ordinary line by searching for the closest pair of a point and a line through two other points. Mukhopadhyay & Greene (2012) signaler l'heure de cette recherche de paire la plus proche comme {style d'affichage O(n^{3})} , basé sur une recherche par force brute de tous les triplets de points, mais un algorithme pour trouver le point donné le plus proche de chaque ligne passant par deux points donnés, à l'heure {style d'affichage O(n^{2})} , was given earlier by Edelsbrunner & Guibas (1989), en tant que sous-programme pour trouver le triangle d'aire minimale déterminé par trois points d'un ensemble donné de points. The same paper of Edelsbrunner & Guibas (1989) montre également comment construire le double arrangement de lignes aux points donnés (tel qu'utilisé dans la preuve de Melchior et Steenrod) dans le même temps, {style d'affichage O(n^{2})} , à partir duquel il est possible d'identifier tous les sommets ordinaires et toutes les lignes ordinaires. Mukhopadhyay, Agrawal & Hosabettu (1997) a d'abord montré comment trouver une seule ligne ordinaire (pas nécessairement celui de la preuve de Kelly) à l'heure {style d'affichage O(loyer m)} , and a simpler algorithm with the same time bound was described by Mukhopadhyay & Greene (2012).

The algorithm of Mukhopadhyay & Greene (2012) est basé sur la preuve de Coxeter utilisant une géométrie ordonnée. Il effectue les étapes suivantes: Choisissez un point {style d'affichage p_{0}} qui est un sommet de l'enveloppe convexe des points donnés. Construire une ligne {style d'affichage ell _{0}} qui passe par {style d'affichage p_{0}} et sinon reste à l'extérieur de la coque convexe. Trier les autres points donnés par l'angle qu'ils font avec {style d'affichage p_{0}} , regrouper des points qui forment le même angle. Si l'un des points est seul dans son groupe, puis retournez la ligne ordinaire passant par ce point et {style d'affichage p_{0}} . Pour chaque groupe de points consécutifs, dans la séquence triée par leurs angles, former deux lignes, dont chacun passe par le point le plus proche de {style d'affichage p_{0}} dans un groupe et le point le plus éloigné de {style d'affichage p_{0}} dans l'autre groupe. Pour chaque ligne {style d'affichage ell _{je}} dans l'ensemble des lignes ainsi formées, trouver le point d'intersection de {style d'affichage ell _{je}} avec {style d'affichage ell _{0}} Retourner la ligne {style d'affichage ell _{je}} dont le point d'intersection avec {style d'affichage ell _{0}} est le plus proche de {style d'affichage p_{0}} .

Comme le prouvent les auteurs, la ligne retournée par cet algorithme doit être ordinaire. La preuve est soit par construction si elle est retournée par étape 4, ou par contradiction s'il est renvoyé par étape 7: si la ligne est revenue à l'étape 7 n'étaient pas ordinaires, alors les auteurs prouvent qu'il existerait une ligne ordinaire entre un de ses points et {style d'affichage p_{0}} , mais cette ligne aurait déjà dû être trouvée et renvoyée à l'étape 4.[13] Le nombre de lignes ordinaires Les deux exemples connus d'ensembles de points avec moins de {displaystyle n/2} lignes ordinaires.

Alors que le théorème de Sylvester-Gallai stipule qu'un arrangement de points, pas tous colinéaires, doit déterminer une ligne ordinaire, il ne dit pas combien doit être déterminé. Laisser {style d'affichage t_{2}(n)} être le nombre minimum de lignes ordinaires déterminé sur chaque ensemble de {displaystyle n} points non colinéaires. La preuve de Melchior a montré que {style d'affichage t_{2}(n)gq 3} . de Bruijn and Erdős (1948) soulevé la question de savoir si {style d'affichage t_{2}(n)} se rapproche de l'infini avec {displaystyle n} . Theodore Motzkin (1951) confirmé qu'il le fait en prouvant que {style d'affichage t_{2}(n)gq {sqrt {n}}} . Gabriel Dirac (1951) a conjecturé que {style d'affichage t_{2}geq létage n/2rétage } , pour toutes les valeurs de {displaystyle n} , une conjecture qui tient toujours 2013. Ceci est souvent appelé la conjecture de Dirac-Motzkin; voir par exemple Brass, Moser & Pach (2005, p. 304). Kelly & Moser (1958) Prouvé cela {style d'affichage t_{2}(n)géq 3n/7} .

Exemple de Böröczky (même) configurer avec 10 points déterminant 5 lignes ordinaires (les cinq lignes noires pleines de la figure).

La borne inférieure conjecturée de Dirac est asymptotiquement la meilleure possible, comme les nombres pairs {displaystyle n} supérieur à quatre ont une limite supérieure correspondante {style d'affichage t_{2}(n)leq n/2} . La construction, dû à Károly Böröczky, qui réalise cette borne est constitué des sommets d'un {style d'affichage m} -gon dans le plan projectif réel et un autre {style d'affichage m} points (Donc, {style d'affichage n=2m} ) sur la droite à l'infini correspondant à chacune des directions déterminées par des paires de sommets. Bien qu'il y ait {style d'affichage m(m-1)/2} paires de ces points, ils déterminent seulement {style d'affichage m} directions distinctes. Cette disposition n'a que {style d'affichage m} lignes ordinaires, les droites qui relient un sommet {style d'affichage v} avec le point à l'infini colinéaire aux deux voisins de {style d'affichage v} . Comme pour toute configuration finie dans le plan projectif réel, cette construction peut être perturbée pour que tous les points soient finis, sans changer le nombre de lignes ordinaires.[14] Pour impair {displaystyle n} , seuls deux exemples sont connus qui correspondent à la conjecture de la limite inférieure de Dirac, C'est, avec {style d'affichage t_{2}(n)=(n-1)/2} Un exemple, by Kelly & Moser (1958), se compose des sommets, milieu des bords, et centre de gravité d'un triangle équilatéral; ces sept points ne déterminent que trois droites ordinaires. La configuration dans laquelle ces trois lignes ordinaires sont remplacées par une seule ligne ne peut pas être réalisée dans le plan euclidien, mais forme un espace projectif fini connu sous le nom de plan de Fano. En raison de cette connexion, l'exemple Kelly-Moser a également été appelé la configuration non-Fano.[15] L'autre contre-exemple, à cause de McKee,[14] se compose de deux pentagones réguliers joints bord à bord avec le milieu du bord partagé et quatre points sur la ligne à l'infini dans le plan projectif; ces 13 points ont parmi eux 6 lignes ordinaires. Les modifications de la construction de Böröczky conduisent à des ensembles de nombres impairs de points avec {displaystyle 3lfloor n/4rfloor } lignes ordinaires.[16] Csima & Sawyer (1993) Prouvé cela {style d'affichage t_{2}(n)geq lceil 6n/13rceil } sauf quand {displaystyle n} est sept. asymptotiquement, cette formule est déjà {style d'affichage 12/13 environ 92.3%} du prouvé {displaystyle n/2} borne supérieure. La {displaystyle n=7} cas est une exception car sinon la construction Kelly-Moser serait un contre-exemple; leur construction montre que {style d'affichage t(7)leq 3} . Cependant, la borne Csima-Sawyer était-elle valide pour {displaystyle n=7} , il prétendrait que {style d'affichage t_{2}(7)gq 4} .

Un résultat étroitement lié est le théorème de Beck, indiquant un compromis entre le nombre de lignes avec peu de points et le nombre de points sur une seule ligne.[17] Ben Green et Terence Tao ont montré que pour tous les ensembles de points suffisamment grands (C'est, {displaystyle n>n_{0}} pour un choix approprié de {displaystyle n_{0}} ), le nombre de lignes ordinaires est en effet au moins {displaystyle n/2} . Par ailleurs, lorsque {displaystyle n} est impair, le nombre de lignes ordinaires est au moins {style d'affichage 3n/4-C} , pour une certaine constante {displaystyle C} . Ainsi, les constructions de Böröczky pour pair et impair (discuté ci-dessus) sont les meilleurs possibles. La minimisation du nombre de lignes ordinaires est étroitement liée au problème de plantation de vergers consistant à maximiser le nombre de lignes à trois points, que Green et Tao ont également résolu pour tous les ensembles de points suffisamment grands.[18] Le nombre de lignes de connexion Article principal: Théorème de De Bruijn-Erdős (géométrie d'incidence) Comme l'a observé Paul Erdős, le théorème de Sylvester-Gallai implique immédiatement que tout ensemble de {displaystyle n} points qui ne sont pas colinéaires détermine au moins {displaystyle n} différentes lignes. Ce résultat est connu sous le nom de théorème de De Bruijn-Erdős. Comme cas de base, le résultat est clairement vrai pour {displaystyle n=3} . Pour toute valeur supérieure de {displaystyle n} , le résultat peut être réduit de {displaystyle n} pointe vers {displaystyle n-1} points, en supprimant une ligne ordinaire et l'un des deux points qu'elle contient (en prenant soin de ne pas supprimer un point pour lequel le sous-ensemble restant se trouverait sur une seule ligne). Ainsi, il s'ensuit par induction mathématique. L'exemple d'un quasi-crayon, un ensemble de {displaystyle n-1} points colinéaires avec un point supplémentaire qui n'est pas sur la même ligne que les autres points, montre que cette borne est étroite.[16] Generalizations The Sylvester–Gallai theorem has been generalized to colored point sets in the Euclidean plane, et aux systèmes de points et de droites définis algébriquement ou par des distances dans un espace métrique. En général, ces variations du théorème ne considèrent que des ensembles finis de points, pour éviter des exemples comme l'ensemble de tous les points dans le plan euclidien, qui n'a pas de ligne ordinaire.

Colored points A variation of Sylvester's problem, posé au milieu des années 1960 par Ronald Graham et popularisé par Donald J. Homme nouveau, considère des ensembles plans finis de points (pas tous alignés) qui reçoivent deux couleurs, et demande si chaque ensemble de ce type a une ligne passant par deux points ou plus qui sont tous de la même couleur. Dans le langage des ensembles et des familles d'ensembles, une déclaration équivalente est que la famille des sous-ensembles colinéaires d'un ensemble de points finis (pas tous sur une seule ligne) ne peut pas avoir la propriété B. Une preuve de cette variation a été annoncée par Theodore Motzkin mais jamais publiée; la première preuve publiée était par Chakerian (1970).[19] Coordonnées non réelles La configuration Hesse, dans laquelle la ligne passant par chaque paire de points contient un troisième point. Le théorème de Sylvester-Gallai montre qu'il ne peut pas être réalisé par des lignes droites dans le plan euclidien, mais il a une réalisation dans le plan projectif complexe.

Tout comme le plan euclidien ou plan projectif peut être défini en utilisant des nombres réels pour les coordonnées de leurs points (Coordonnées cartésiennes pour le plan euclidien et coordonnées homogènes pour le plan projectif), des systèmes abstraits analogues de points et de lignes peuvent être définis en utilisant d'autres systèmes de nombres comme coordonnées. Le théorème de Sylvester-Gallai ne tient pas pour les géométries définies de cette manière sur des corps finis: pour certaines géométries finies ainsi définies, comme l'avion Fano, l'ensemble de tous les points de la géométrie n'a pas de lignes ordinaires.[7] Le théorème de Sylvester-Gallai ne s'applique pas non plus directement aux géométries dans lesquelles les points ont des coordonnées qui sont des paires de nombres complexes ou de quaternions, mais ces géométries ont des analogues plus compliqués du théorème. Par exemple, dans le plan projectif complexe il existe une configuration de neuf points, La configuration de Hesse (les points d'inflexion d'une courbe cubique), dans lequel chaque ligne est non ordinaire, violant le théorème de Sylvester-Gallai. Une telle configuration est connue sous le nom de configuration Sylvester-Gallai, et il ne peut pas être réalisé par des points et des lignes du plan euclidien. Une autre façon d'énoncer le théorème de Sylvester-Gallai est que chaque fois que les points d'une configuration de Sylvester-Gallai sont intégrés dans un espace euclidien, préserver les colinéarités, les points doivent tous se trouver sur une seule ligne, et l'exemple de la configuration de Hesse montre que ceci est faux pour le plan projectif complexe. Cependant, Kelly (1986) prouvé un analogue de nombre complexe du théorème de Sylvester-Gallai: chaque fois que les points d'une configuration Sylvester-Gallai sont intégrés dans un espace projectif complexe, les points doivent tous se trouver dans un sous-espace à deux dimensions. De manière équivalente, un ensemble de points dans un espace complexe tridimensionnel dont l'enveloppe affine est l'espace entier doit avoir une ligne ordinaire, et en fait doit avoir un nombre linéaire de lignes ordinaires.[20] De la même manière, Elkis, Pretorius & Swanepoel (2006) a montré que chaque fois qu'une configuration Sylvester – Gallai est intégrée dans un espace défini sur les quaternions, ses points doivent se situer dans un sous-espace tridimensionnel.

Matroids Every set of points in the Euclidean plane, et les lignes qui les relient, peut être résumé comme les éléments et les appartements d'un matroïde orienté de rang 3. Les points et les lignes de géométries définies à l'aide d'autres systèmes de nombres que les nombres réels forment également des matroïdes, mais pas forcément orientés matroïdes. Dans ce contexte, the result of Kelly & Moser (1958) la borne inférieure du nombre de lignes ordinaires peut être généralisée aux matroïdes orientés: chaque matroïde orienté rang 3 avec {displaystyle n} éléments a au moins {style d'affichage 3n/7} lignes à deux points, ou de manière équivalente, chaque matroïde de rang 3 avec moins de lignes à deux points doit être non orientable.[21] Un matroïde sans lignes à deux points est appelé un matroïde de Sylvester. De façon connexe, la configuration Kelly-Moser avec sept points et seulement trois lignes ordinaires forme l'un des mineurs interdits pour GF(4)-matroïdes représentables.[15] Distance geometry Another generalization of the Sylvester–Gallai theorem to arbitrary metric spaces was conjectured by Chvátal (2004) et prouvé par Chen (2006). Dans cette généralisation, un triplet de points dans un espace métrique est défini comme étant colinéaire lorsque l'inégalité triangulaire pour ces points est une égalité, et une ligne est définie à partir de n'importe quelle paire de points en incluant à plusieurs reprises des points supplémentaires qui sont colinéaires avec des points déjà ajoutés à la ligne, jusqu'à ce qu'il ne soit plus possible d'ajouter de tels points. La généralisation de Chvátal et Chen stipule que chaque espace métrique fini a une ligne qui contient soit tous les points, soit exactement deux des points.[22] Remarques ^ Elkies, Pretorius & Swanepoel (2006). ^ Sauter à: a b Borwein & Moser (1990). ^ Steinberg et al. (1944); Forêt (1982). ^ MR0041447 ^ MR0056941 ^ Shephard (1968). ^ Sauter à: a b c d e Aigner & Ziegler (2018). ^ Sauter à: a b c Melchior (1941). ^ Aigner & Ziegler (2018, p. 92); La preuve de Steenrod a été brièvement résumée dans Steinberg et al. (1944). ^ Aigner & Ziegler (2018); pambuccien (2009). ^ Coxter (1948); pambuccien (2009). Pour la preuve de Steinberg, voir Steinberg et al. (1944). ^ Noyau d'amande (2016). ^ Mukhopadhyay & Greene (2012). ^ Sauter à: a b Crowe & McKee (1968). ^ Sauter à: a b Geelen, Gerards & Kapoor (2000). ^ Sauter à: a b Pach & Sharir (2009) ^ Beck (1983). ^ Green & Tao (2013). ^ Pour l'histoire de cette variation du problème, voir aussi Grünbaum (1999) ^ Basit et al. (2019). ^ Björner et al. (1993). ^ Il a craqué (2004); Chen (2006); pambuccien (2009) Références Aigner, Martin; Ziegler, Günter M. (2018), "Chapitre 11. Droites dans le plan et décomposition des graphes", Preuves du LIVRE (6e éd.), Springer, Théorème 1, pp. 77–78, est ce que je:10.1007/978-3-662-57265-8_11, ISBN 978-3-662-57265-8 Basit, Abdoul; Dvir, Zeev; Nerfs, Shubhangi; Loup, Charles (2019), "Sur le nombre de droites ordinaires déterminé par des ensembles dans l'espace complexe", Discrete & Computational Geometry, 61 (4): 778–808, arXiv:1611.08740, est ce que je:10.1007/s00454-018-0039-4, M 3943495, S2CID 125616042 Beck, Joseph (1983), "Sur la propriété de réseau du plan et quelques problèmes de Dirac, Motzkin, et Erdős en géométrie combinatoire", Combinatoire, 3 (3–4): 281–297, est ce que je:10.1007/BF02579184, M 0729781, S2CID 31011939 Björner, Anders; Les Vergnas, michel; tempête de roche, Bernd; Blanc, Neil; Ziegler, Günter M. (1993), Matroïdes orientés, Encyclopédie des mathématiques et de ses applications, volume. 46, Cambridge: la presse de l'Universite de Cambridge, p. 273, ISBN 0-521-41836-4, M 1226888 Borwein, P; Moser, O. O. J. (1990), "Une étude du problème de Sylvester et de ses généralisations", Équations mathématiques, 40 (1): 111–135, est ce que je:10.1007/BF02112289, M 1069788, S2CID 122052678 Brass, Pierre; Moser, William; L'odeur, John (2005), Problèmes de recherche en géométrie discrète, Berlin: Springer, ISBN 0-387-23815-8 de Bruijn, N. G.; Forêt, P. (1948), "Une combinatoire [sic] problème" (PDF), Recherches mathématiques, 10: 421–423, M 0028289 Chakerian, g. ré. (1970), "Problème de Sylvester sur des points colinéaires et un relatif", Mensuel mathématique américain, 77 (2): 164–167, est ce que je:10.2307/2317330, JSTOR 2317330, M 0258659 Chen, Xiaomin (2006), "Le Sylvestre – Il saisit le théorème", Discrete & Computational Geometry, 35 (2): 193–199, est ce que je:10.1007/s00454-005-1216-9, M 2195050 il saisissait, Vasek (2004), "Théorème de Sylvester-Gallai et intermédiarité métrique", Discrete & Computational Geometry, 31 (2): 175–195, est ce que je:10.1007/s00454-003-0795-6, M 2060634 Coxeter, H. S. M. (1948), "Un problème de points colinéaires", Mensuel mathématique américain, 55 (1): 26–28, est ce que je:10.2307/2305324, JSTOR 2305324, M 0024137 Coxeter, H. S. M. (1969), "12.3 Problème de Sylvester des points colinéaires", Introduction à la géométrie (2sd éd.), New York: John Wiley & Sons, pp. 181–182, ISBN 0-471-50458-0 Crowe, ré. W; McKee, J. UN. (1968), "Problème de Sylvester sur les points colinéaires", Magazine de mathématiques, 41 (1): 30–34, est ce que je:10.2307/2687957, JSTOR 2687957, M 0235452 Csima, J; Scieur, E. (1993), "Il existe {style d'affichage 6n/13} points ordinaires", Discrete & Computational Geometry, 9: 187–202, est ce que je:10.1007/BF02189318, M 1194036 Dirac, g. (1951), "Propriétés de colinéarité des ensembles de points", Revue trimestrielle de mathématiques, 2: 221–227, Code bib:1951QJMat...2..221D, est ce que je:10.1093/qmath/2.1.221, M 0043485 Edelsbrunner, Herbert; Guiba, Léonidas J. (1989), "Balayage topologique d'un arrangement", Journal des sciences informatiques et des systèmes, 38 (1): 165–194, est ce que je:10.1016/0022-0000(89)90038-X, M 0990055 Elkis, Noé; Pretorius, Lou M.; Swanepoel, Konrad J.. (2006), "Théorèmes de Sylvester-Gallai pour les nombres complexes et les quaternions", Discrete & Computational Geometry, 35 (3): 361–373, arXiv:mathématiques/0403023, est ce que je:10.1007/s00454-005-1226-7, M 2202107, S2CID 1647360 Forêt, P. (1943), "Problème 4065", Problèmes à résoudre: 4065–4069, Mensuel mathématique américain, 50 (1): 65–66, est ce que je:10.2307/2304011, JSTOR 2304011 Forêt, P. (1982), "Réminiscences personnelles et remarques sur les travaux mathématiques de Tibor Gallai" (PDF), Combinatoire, 2 (3): 207–212, est ce que je:10.1007/BF02579228, M 0698647, S2CID 1135308 Geelen, J. F.; Gérard, UN. M. H; Kapoor, UN. (2000), "Les mineurs exclus pour GF(4)-matroïdes représentables" (PDF), Journal de théorie combinatoire, Série B, 79 (2): 247–299, est ce que je:10.1006/jctb.2000.1963, M 1769191, archivé de l'original (PDF) sur 2010-09-24 Vert, Ben; Tao, Térence (2013), "Sur des ensembles définissant peu de lignes ordinaires", Discrete & Computational Geometry, 50 (2): 409–468, arXiv:1208.4714, est ce que je:10.1007/s00454-013-9518-9, M 3090525, S2CID 15813230 Grünbaum, Branko (1999), "Points d'intersection monochromes dans des familles de lignes colorées" (PDF), Géombinatoire, 9 (1): 3–9, M 1698297 Kelly, L. M. (1986), "Une résolution du problème de Sylvester-Gallai de J. P. Serre", Géométrie discrète et computationnelle, 1 (2): 101–104, est ce que je:10.1007/BF02187687, M 0834051 Kelly, L. M; Moser, O. O. J. (1958), "Sur le nombre de lignes ordinaires déterminé par {displaystyle n} points", Revue canadienne de mathématiques, 10: 210–219, est ce que je:10.4153/CJM-1958-024-6, M 0097014, S2CID 123865536 Mandelkern, Marquer (2016), "Une version constructive du théorème de Sylvester-Gallai", Journal mathématique hongrois, 150: 121–130, est ce que je:10.1007/s10474-016-0624-z, M 3542040, S2CID 124023963 Melchior, E. (1941), "À propos de la polyvalence du plan projectif", Mathématiques allemandes, 5: 461–475 Motzkine, E. (1951), "Les lignes et les plans reliant les points d'un ensemble fini", Transactions de l'American Mathematical Society, 70 (3): 451–464, est ce que je:10.2307/1990609, JSTOR 1990609, M 0041447 Mukhopadhyay, UN.; Agrawal, UN.; Hosabetto, R. M. (1997), "Sur le problème de la ligne ordinaire en géométrie computationnelle", Journal nordique d'informatique, 4 (4): 330–341, M 1607014 Mukhopadhyay, , des choses; Green, Eugène (2012), "Le problème de la ligne ordinaire revisité", Géométrie computationnelle: Théorie et applications, 45 (3): 127–130, est ce que je:10.1016/j.comgeo.2011.10.003, M 2853475 L'odeur, John; Charir, Michée (2009), "Chapitre 1. Sylvester–Cela pourrait être un problème: Les débuts de la géométrie combinatoire", La géométrie combinatoire et ses applications algorithmiques: Les conférences d'Alcalá, Enquêtes mathématiques et monographies, volume. 152, Société mathématique américaine, pp. 1–12 Pambuccian, Victor (2009), "Une analyse inverse du théorème de Sylvester-Gallai", Notre Dame Journal of Formal Logic, 50 (3): 245–260, est ce que je:10.1215/00294527-2009-010, M 2572973 Shephard, g. C. (1968), "Vingt problèmes sur les polyèdres convexes, partie I", La gazette mathématique, 52 (380): 136–156, est ce que je:10.2307/3612678, JSTOR 3612678, M 0231278 Steinberg, R; mâle, R. C; Forêt verte, T; Steenrod, N. E. (1944), "Colinéarité à trois points (solution au problème 4065)", Mensuel mathématique américain, 51 (3): 169–171, est ce que je:10.2307/2303021, JSTOR 2303021 Sylvestre, J. J. (1893), "Question mathématique 11851", Les temps éducatifs, 46 (383): 156 Woodall, H. J. (1893un), "Question mathématique 11851 a répondu", Les temps éducatifs, 46 (385): 231 Woodall, H. J. (1893b), "Question mathématique 11851 a répondu", Questions mathématiques et solutions du temps de l'éducation, 59: 98 Liens externes Malkevitch, Joseph (2003), "Un bijou géométrique discret", Colonne des fonctionnalités AMS, Société mathématique américaine, archivé à partir de l'original sur 2006-10-10 Weisstein, Éric W., "Ligne ordinaire", Présentation de MathWorld Proof par Terence Tao au 2013 Minerva Lectures hide vte Incidence structures Representation Incidence matrixIncidence graph Fields Combinatorics Block designSteiner systemGeometry IncidenceProjective planeGraph theory HypergraphStatistics Blocking Configurations Complete quadrangleFano planeMöbius–Kantor configurationPappus configurationHesse configurationDesargues configurationReye configurationSchläfli double sixCremona–Richmond configurationKummer configurationGrünbaum–Rigby configurationKlein configurationDual Theorems Sylvester–Gallai theoremDe Bruijn–Erdős theoremSzemerédi–Trotter theoremBeck's theoremBruck–Ryser–Chowla theorem Applications Design of experimentsKirkman's schoolgirl problem Categories: Géométrie plane euclidienneThéorèmes en géométrie discrèteThéorie des matroïdes