Sylvester-Could-Theorem

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. Es ist nach James Joseph Sylvester benannt, der es als ein Problem darstellte 1893, und Tibor Gallai, der einen der ersten Beweise dieses Theorems veröffentlichte 1944.

Eine Linie, die genau zwei Punkte einer Menge von Punkten enthält, wird als gewöhnliche Linie bezeichnet. Eine andere Möglichkeit, den Satz zu formulieren, ist, dass jede endliche Menge von Punkten, die nicht kollinear ist, eine gewöhnliche Linie hat. Nach einer Verstärkung des Theorems, jede endliche Punktmenge (nicht alles in einer Zeile) hat mindestens eine lineare Anzahl gewöhnlicher Linien. Ein Algorithmus kann eine gewöhnliche Linie in einer Menge von finden {Anzeigestil n} Zeitpunkte {Anzeigestil O(Miete n)} .

Inhalt 1 Geschichte 2 Äquivalente Versionen 3 Beweise 3.1 Kellys Beweis 3.2 Melchiors Beweis 3.2.1 Melchiors Ungleichung 3.3 Axiomatik 4 Finden einer gewöhnlichen Linie 5 Die Anzahl der gewöhnlichen Linien 6 Die Anzahl der Verbindungslinien 7 Verallgemeinerungen 7.1 Farbige Punkte 7.2 Nicht reale Koordinaten 7.3 Matroide 7.4 Abstandsgeometrie 8 Anmerkungen 9 Verweise 10 External links History The Sylvester–Gallai theorem was posed as a problem by J. J. Silvester (1893). Kelly (1986) schlägt vor, dass Sylvester möglicherweise durch ein verwandtes Phänomen in der algebraischen Geometrie motiviert wurde, bei dem die Wendepunkte einer kubischen Kurve in der komplexen Projektionsebene eine Konfiguration aus neun Punkten und zwölf Linien bilden (Die Hessenkonfiguration) wobei jede durch zwei der Punkte bestimmte Linie einen dritten Punkt enthält. Das Sylvester-Gallai-Theorem impliziert, dass es unmöglich ist, dass alle neun dieser Punkte echte Koordinaten haben.[1] H. J. Woodall (1893a, 1893b) behauptete, einen kurzen Beweis des Sylvester-Gallai-Theorems zu haben, aber es wurde bereits zum Zeitpunkt der Veröffentlichung als unvollständig vermerkt. Eberhard Melchior (1941) bewies den Satz (und tatsächlich ein etwas stärkeres Ergebnis) in einer äquivalenten Formulierung, sein projektives Dual. Keine Ahnung von Melchiors Beweis,[2] Paul Erdős (1943) wiederholte die Vermutung, was später von Tibor Gallai bewiesen wurde, und bald darauf von anderen Autoren.[3] In einem 1951 Rezension, Erdős nannte das Ergebnis "Satz von Could",[4] aber es wurde bereits in a Sylvester-Gallai-Theorem genannt 1954 Rezension von Leonard Blumenthal.[5] Es ist eines von vielen mathematischen Themen, die nach Sylvester benannt sind.

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. Die projektive Ebene kann aus der euklidischen Ebene gebildet werden, indem zusätzliche Punkte hinzugefügt werden "bei unendlich" wo Linien, die in der euklidischen Ebene parallel sind, sich schneiden, und durch Hinzufügen einer einzelnen Zeile "bei unendlich" enthält alle hinzugefügten Punkte. Jedoch, Die zusätzlichen Punkte der Projektionsebene können nicht dazu beitragen, nichteuklidische endliche Punktmengen ohne gewöhnliche Linie zu erstellen, da jede endliche Punktmenge in der projektiven Ebene in eine euklidische Punktmenge mit demselben kombinatorischen Muster von Punkt-Linien-Inzidenzen umgewandelt werden kann. Deswegen, Jedes Muster aus endlich vielen sich schneidenden Punkten und Linien, das in einem dieser beiden Ebenentypen existiert, existiert auch in dem anderen. Nichtsdestotrotz, Die projektive Sichtweise ermöglicht es, bestimmte Konfigurationen einfacher zu beschreiben. Im Speziellen, es erlaubt die Verwendung von projektiver Dualität, in denen die Rollen von Punkten und Linien in Aussagen der projektiven Geometrie gegeneinander ausgetauscht werden können. Unter projektiver Dualität, Die Existenz einer gewöhnlichen Linie für eine Menge nicht kollinearer Punkte in RP2 ist äquivalent zur Existenz eines gewöhnlichen Punktes in einer nichttrivialen Anordnung von endlich vielen Linien. Eine Anordnung heißt trivial, wenn alle ihre Geraden durch einen gemeinsamen Punkt gehen, und ansonsten nicht trivial; Ein gewöhnlicher Punkt ist ein Punkt, der zu genau zwei Geraden gehört.[2] Das längliche Dodekaeder, ein Zonoeder. Seine acht roten Parallelogrammflächen entsprechen gewöhnlichen Punkten einer fünfzeiligen Anordnung; Eine äquivalente Form des Sylvester-Gallai-Theorems besagt, dass jeder Zonoeder mindestens eine Parallelogrammfläche hat.

Anordnungen von Linien haben eine kombinatorische Struktur, die eng mit Zonoedern verbunden ist, Polyeder, die als Minkowski-Summe einer endlichen Menge von Liniensegmenten gebildet werden, Generatoren genannt. In dieser Verbindung, Jedes Paar gegenüberliegender Flächen eines Zonoeders entspricht einem Kreuzungspunkt einer Anordnung von Linien in der Projektionsebene, mit einer Leitung für jeden Generator. Die Anzahl der Seiten jeder Fläche ist doppelt so groß wie die Anzahl der Linien, die sich in der Anordnung kreuzen. Zum Beispiel, das gezeigte längliche Dodekaeder ist ein Zonoeder mit fünf Generatoren, zwei Paar gegenüberliegender Sechskantflächen, und vier Paare von gegenüberliegenden Parallelogrammflächen. In der entsprechenden fünfzeiligen Anordnung, zwei Linientripel kreuzen sich (entsprechend den zwei Paaren von gegenüberliegenden Sechsecken) und die verbleibenden vier Linienpaare kreuzen sich an gewöhnlichen Punkten (entsprechend den vier Paaren gegenüberliegender Parallelogramme). Eine äquivalente Aussage des Sylvester-Gallai-Theorems, in Bezug auf Zonoeder, ist, dass jeder Zonoeder mindestens eine Parallelogrammfläche hat (Rechtecke zählen, Rauten, und Quadrate als Spezialfälle von Parallelogrammen). Noch stärker, wann immer Sätze von {Anzeigestil n} Punkte in der Ebene garantiert mindestens haben {Anzeigestil t_{2}(n)} gewöhnliche Linien, Zonoeder mit {Anzeigestil n} Generatoren können garantiert mindestens haben {Anzeigestil 2t_{2}(n)} Parallogramm-Gesichter.[6] Proofs The Sylvester–Gallai theorem has been proved in many different ways. Es könnte 1944 Beweis schaltet zwischen euklidischer und projektiver Geometrie hin und her, um die Punkte in eine äquivalente Konfiguration umzuwandeln, in der eine gewöhnliche Linie als eine Linie mit der Steigung am nächsten bei Null gefunden werden kann; für Details, see Borwein & Moser (1990). Das 1941 Der Beweis von Melchior verwendet die projektive Dualität, um das Problem in eine äquivalente Frage nach Anordnungen von Linien umzuwandeln, was mit der Eulerschen Polyederformel beantwortet werden kann. Ein weiterer Beweis von Leroy Milton Kelly zeigt im Widerspruch, dass die Verbindungslinie mit dem kleinsten Nicht-Null-Abstand zu einem anderen Punkt gewöhnlich sein muss. Und, nach einem früheren Beweis von Steinberg, H. S. M. Coxeter zeigte, dass die metrischen Konzepte von Steigung und Entfernung, die in den Beweisen von Gallai und Kelly vorkommen, unnötig mächtig sind, Stattdessen beweist man den Satz nur mit den Axiomen der geordneten Geometrie.

Kelly's proof Notation for Kelly's proof This proof is by Leroy Milton Kelly. Aigner & Ziegler (2018) nennen "einfach das beste" der vielen Beweise dieses Theorems.[7] Angenommen, eine endliche Menge {Anzeigestil S} von Punkten ist nicht alles kollinear. Definieren Sie eine Verbindungslinie als eine Linie, die mindestens zwei Punkte in der Sammlung enthält. Durch Endlichkeit, {Anzeigestil S} muss einen Punkt haben {Anzeigestil P} und eine Verbindungslinie {Anzeigestil ell } die einen positiven Abstand voneinander haben, aber näher beieinander liegen als alle anderen Punkt-Linien-Paare. Kelly hat das bewiesen {Anzeigestil ell } ist gewöhnlich, durch Widerspruch.[7] Annehmen, dass {Anzeigestil ell } ist nicht gewöhnlich. Dann geht es durch mindestens drei Punkte von {Anzeigestil S} . Mindestens zwei davon befinden sich auf derselben Seite {Anzeigestil P'} , die senkrechte Projektion von {Anzeigestil P} an {Anzeigestil ell } . Ruf Sie an {Anzeigestil B} und {Anzeigestil C} , mit {Anzeigestil B} am nächsten sein {Anzeigestil P'} (und möglicherweise damit zusammenfallen). Ziehe die Verbindungslinie {Anzeigestil m} durchgehen {Anzeigestil P} und {Anzeigestil C} , und die Senkrechte aus {Anzeigestil B} zu {Anzeigestil B'} an {Anzeigestil m} . Dann {Anzeigestil BB'} ist kürzer als {Anzeigestil PP'} . Dies folgt daraus, dass {displaystyle PP'C} und {Displaystyle BB'C} sind ähnliche Dreiecke, eines in dem anderen enthalten.[7] Jedoch, dies widerspricht der ursprünglichen Definition von {Anzeigestil P} und {Anzeigestil ell } als das Punkt-Linien-Paar mit dem kleinsten positiven Abstand. Also die Annahme, dass {Anzeigestil ell } ist nicht gewöhnlich, kann nicht wahr sein, IST[7] Melchior's proof In 1941 (daher, bevor Erdős die Frage und Gallais anschließenden Beweis veröffentlichte) Melchior zeigte, dass jede nichttriviale endliche Anordnung von Linien in der projektiven Ebene mindestens drei gewöhnliche Punkte hat. Durch Dualität, Dieses Ergebnis besagt auch, dass jede endliche nichttriviale Menge von Punkten auf der Ebene mindestens drei gewöhnliche Linien hat.[8] Melchior hat das beobachtet, für jeden Graphen, der in die reelle projektive Ebene eingebettet ist, die Formel {Anzeigestil V-E+F} muss gleich sein {Anzeigestil 1} , die Euler-Charakteristik der projektiven Ebene. Hier {Anzeigestil V} , {Anzeigestil E} , und {Anzeigestil F} sind die Anzahl der Ecken, Kanten, und Flächen des Graphen, beziehungsweise. Jede nicht triviale Linienanordnung auf der projektiven Ebene definiert einen Graphen, in dem jede Fläche durch mindestens drei Kanten begrenzt ist, und jede Kante grenzt an zwei Flächen; Also, Doppelzählung ergibt die zusätzliche Ungleichheit {displaystyle Fleq 2E/3} . Mit dieser Ungleichheit zu beseitigen {Anzeigestil F} aus der Euler-Charakteristik führt zur Ungleichung {Anzeige Eleq 3V-3} . Aber wenn jeder Scheitelpunkt in der Anordnung der Kreuzungspunkt von drei oder mehr Linien wäre, dann wäre die Gesamtzahl der Kanten mindestens {Anzeige 3V} , dieser Ungleichheit widersprechen. Deswegen, einige Eckpunkte müssen der Kreuzungspunkt von nur zwei Linien sein, und wie Melchiors sorgfältigere Analyse zeigt, mindestens drei gewöhnliche Knoten werden benötigt, um die Ungleichung zu erfüllen {Anzeige Eleq 3V-3} .[8] As Aigner & Ziegler (2018) Hinweis, Das gleiche Argument für die Existenz einer gewöhnlichen Ecke wurde auch angeführt 1944 von Norman Steenrod, der es explizit auf das Problem der doppelten gewöhnlichen Linien anwandte.[9] Melchior's inequality By a similar argument, Melchior konnte ein allgemeineres Ergebnis nachweisen. Für jeden {Anzeigestil kgeq 2} , Lassen {Anzeigestil t_{k}} sei die Anzahl der Punkte, zu denen {Anzeigestil k} Linien sind Vorfälle. Dann[8] {Anzeigestil Anzeigestil Summe _{kgeq 2}(k-3)t_{k}leq -3.} oder gleichwertig, {Anzeigestil Anzeigestil t_{2}geqslant 3+sum _{kgeq 4}(k-3)t_{k}.} Axiomatics H. S. M. Coxeter (1948, 1969) schreibt über Kellys Beweis, dass seine Verwendung der euklidischen Distanz unnötig mächtig ist, "wie mit einem Vorschlaghammer eine Mandel zu knacken". Stattdessen, Coxeter gab einen weiteren Beweis des Sylvester-Gallai-Theorems innerhalb der geordneten Geometrie, eine Axiomatisierung der Geometrie in Bezug auf das Dazwischen, die nicht nur die euklidische Geometrie, sondern mehrere andere verwandte Geometrien umfasst.[10] Coxeters Beweis ist eine Variation eines früheren Beweises von Steinberg in 1944.[11] Das Problem, einen minimalen Satz von Axiomen zu finden, der zum Beweis des Satzes benötigt wird, gehört zur umgekehrten Mathematik; siehe Pambuccian (2009) für eine Untersuchung dieser Frage.

Die übliche Aussage des Sylvester-Gallai-Theorems ist in der konstruktiven Analyse nicht gültig, da es das weniger begrenzte Prinzip der Allwissenheit impliziert, eine abgeschwächte Form des Gesetzes vom ausgeschlossenen Dritten, das als Axiom der konstruktiven Mathematik abgelehnt wird. Nichtsdestotrotz, Es ist möglich, eine Version des Sylvester-Gallai-Theorems zu formulieren, die innerhalb der Axiome der konstruktiven Analyse gültig ist, und Kellys Beweis des Theorems so anzupassen, dass er ein gültiger Beweis unter diesen Axiomen ist.[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) geben Sie die Zeit für diese Suche nach dem nächsten Paar an als {Anzeigestil O(n^{3})} , basierend auf einer Brute-Force-Suche aller Punkttripel, sondern ein Algorithmus, um den nächstgelegenen gegebenen Punkt zu jeder Linie durch zwei gegebene Punkte zu finden, rechtzeitig {Anzeigestil O(n^{2})} , was given earlier by Edelsbrunner & Guibas (1989), als Subroutine zum Finden des Dreiecks mit minimaler Fläche, das durch drei einer gegebenen Menge von Punkten bestimmt wird. The same paper of Edelsbrunner & Guibas (1989) zeigt auch, wie man die duale Anordnung von Linien zu den gegebenen Punkten konstruiert (wie im Beweis von Melchior und Steenrod verwendet) in der gleichen Zeit, {Anzeigestil O(n^{2})} , woraus es möglich ist, alle gewöhnlichen Eckpunkte und alle gewöhnlichen Linien zu identifizieren. Muchopadhyay, Agrawal & Hosabettu (1997) zeigte zuerst, wie man eine einzelne gewöhnliche Linie findet (nicht unbedingt der aus Kellys Beweis) rechtzeitig {Anzeigestil O(Miete n)} , and a simpler algorithm with the same time bound was described by Mukhopadhyay & Greene (2012).

The algorithm of Mukhopadhyay & Greene (2012) basiert auf Coxeters Beweis mit geordneter Geometrie. Es führt die folgenden Schritte aus: Wählen Sie einen Punkt {Anzeigestil p_{0}} das ist ein Scheitelpunkt der konvexen Hülle der gegebenen Punkte. Konstruiere eine Linie {displaystyle ell _{0}} das durchgeht {Anzeigestil p_{0}} und bleibt ansonsten außerhalb der konvexen Hülle. Sortieren Sie die anderen gegebenen Punkte nach dem Winkel, den sie bilden {Anzeigestil p_{0}} , Gruppieren von Punkten, die denselben Winkel bilden. Wenn einer der Punkte allein in seiner Gruppe ist, dann kehre die gewöhnliche Linie durch diesen Punkt zurück und {Anzeigestil p_{0}} . Für je zwei aufeinanderfolgende Punktegruppen, in der sortierten Reihenfolge nach ihren Winkeln, zwei Linien bilden, von denen jeder durch den nächstgelegenen Punkt verläuft {Anzeigestil p_{0}} in einer Gruppe und dem am weitesten entfernten Punkt {Anzeigestil p_{0}} in der anderen Gruppe. Für jede Zeile {displaystyle ell _{ich}} in der so gebildeten Linienmenge, Finden Sie den Schnittpunkt von {displaystyle ell _{ich}} mit {displaystyle ell _{0}} Geben Sie die Zeile zurück {displaystyle ell _{ich}} dessen Schnittpunkt mit {displaystyle ell _{0}} ist am nächsten {Anzeigestil p_{0}} .

Wie die Autoren beweisen, Die von diesem Algorithmus zurückgegebene Zeile muss normal sein. Der Beweis ist entweder konstruktionsbedingt, wenn er schrittweise zurückgegeben wird 4, oder durch Widerspruch, wenn es schrittweise zurückgegeben wird 7: wenn die Linie im Schritt zurückkehrte 7 waren nicht gewöhnlich, dann beweisen die Autoren, dass es eine gewöhnliche Linie zwischen einem ihrer Punkte und geben würde {Anzeigestil p_{0}} , aber diese Zeile sollte bereits gefunden und im Schritt zurückgegeben worden sein 4.[13] Die Anzahl gewöhnlicher Geraden Die zwei bekannten Beispiele von Punktmengen mit weniger als {Anzeigestil Nr. 2} gewöhnliche Linien.

Während das Sylvester-Gallai-Theorem besagt, dass eine Anordnung von Punkten, nicht alle kollinear, muss eine gewöhnliche Linie bestimmen, es wird nicht gesagt, wie viele bestimmt werden müssen. Lassen {Anzeigestil t_{2}(n)} sei die minimale Anzahl gewöhnlicher Linien, die über jeden Satz von bestimmt wird {Anzeigestil n} nicht kollineare Punkte. Melchiors Beweis zeigte das {Anzeigestil t_{2}(n)geq 3} . de Bruijn and Erdős (1948) stellte die Frage, ob {Anzeigestil t_{2}(n)} nähert sich mit unendlich {Anzeigestil n} . Theodore Motzkin (1951) bestätigt, dass dies der Fall ist, indem er dies beweist {Anzeigestil t_{2}(n)geq {quadrat {n}}} . Gabriel Dirac (1951) vermutete das {Anzeigestil t_{2}geq lfloor n/2rfloor } , für alle Werte von {Anzeigestil n} , eine Vermutung, die immer noch steht 2013. Dies wird oft als Dirac-Motzkin-Vermutung bezeichnet; siehe zum Beispiel Messing, Moser & Pach (2005, p. 304). Kelly & Moser (1958) geprüft, dass {Anzeigestil t_{2}(n)geq3n/7} .

Beispiel von Böröczky (eben) Konfiguration mit 10 Punkte bestimmen 5 gewöhnliche Linien (die fünf durchgezogenen schwarzen Linien der Figur).

Diracs vermutete untere Schranke ist asymptotisch die bestmögliche, als gerade Zahlen {Anzeigestil n} größer als vier haben eine übereinstimmende Obergrenze {Anzeigestil t_{2}(n)leq n/2} . Die Konstruktion, wegen Károly Böröczky, die diese Grenze erreicht, besteht aus den Eckpunkten einer regulären {Anzeigestil m} -gon in der realen projektiven Ebene und eine andere {Anzeigestil m} Punkte (daher, {Anzeigestil n=2m} ) auf der Linie im Unendlichen, die jeder der Richtungen entspricht, die durch Scheitelpunktpaare bestimmt sind. Allerdings sind da {Anzeigestil m(m-1)/2} Paare dieser Punkte, sie bestimmen nur {Anzeigestil m} unterschiedliche Richtungen. Diese Anordnung hat nur {Anzeigestil m} gewöhnliche Linien, die Linien, die einen Scheitelpunkt verbinden {Anzeigestil v} mit dem Punkt im Unendlichen kollinear mit den beiden Nachbarn von {Anzeigestil v} . Wie bei jeder endlichen Konfiguration in der realen Projektionsebene, diese Konstruktion kann so gestört werden, dass alle Punkte endlich sind, ohne die Anzahl der gewöhnlichen Zeilen zu ändern.[14] Für ungerade {Anzeigestil n} , Es sind nur zwei Beispiele bekannt, die mit Diracs Vermutung der unteren Grenze übereinstimmen, das ist, mit {Anzeigestil t_{2}(n)=(n-1)/2} Ein Beispiel, by Kelly & Moser (1958), besteht aus den Scheitelpunkten, Kantenmittelpunkte, und Schwerpunkt eines gleichseitigen Dreiecks; diese sieben Punkte bestimmen nur drei gewöhnliche Linien. Die Konfiguration, bei der diese drei gewöhnlichen Linien durch eine einzige Linie ersetzt werden, kann in der euklidischen Ebene nicht realisiert werden, sondern bildet einen endlichen projektiven Raum, der als Fano-Ebene bekannt ist. Wegen dieser Verbindung, Das Kelly-Moser-Beispiel wurde auch als Nicht-Fano-Konfiguration bezeichnet.[15] Das andere Gegenbeispiel, wegen McKee,[14] besteht aus zwei regelmäßigen Fünfecken, die Kante an Kante zusammen mit dem Mittelpunkt der gemeinsamen Kante und vier Punkten auf der Linie im Unendlichen in der Projektionsebene verbunden sind; diese 13 Punkte haben unter sich 6 gewöhnliche Linien. Modifikationen der Konstruktion von Böröczky führen zu Mengen ungerader Punktzahlen mit {displaystyle 3lfloor n/4rfloor } gewöhnliche Linien.[16] Csima & Sawyer (1993) geprüft, dass {Anzeigestil t_{2}(n)geq lceil 6n/13rceil } ausser wenn {Anzeigestil n} ist sieben. Asymptotisch, diese Formel ist bereits {Anzeigestil 12/13ca 92.3%} des Bewährten {Anzeigestil Nr. 2} obere Grenze. Das {Darstellungsstil n=7} Fall ist eine Ausnahme, weil sonst die Kelly-Moser-Konstruktion ein Gegenbeispiel wäre; ihre Konstruktion zeigt das {Anzeigestil t(7)leq 3} . Jedoch, für die die Csima-Sawyer-Bindung gültig war {Darstellungsstil n=7} , es würde das behaupten {Anzeigestil t_{2}(7)geq 4} .

Ein eng verwandtes Ergebnis ist der Satz von Beck, Angabe eines Kompromisses zwischen der Anzahl der Linien mit wenigen Punkten und der Anzahl der Punkte auf einer einzelnen Linie.[17] Ben Green und Terence Tao haben das für alle ausreichend großen Punktmengen gezeigt (das ist, {displaystyle n>n_{0}} für eine geeignete Auswahl an {Anzeigestil n_{0}} ), die Anzahl der ordentlichen Zeilen ist ja mindestens {Anzeigestil Nr. 2} . Außerdem, Wenn {Anzeigestil n} ist ungerade, die Anzahl der gewöhnlichen Zeilen ist mindestens {Anzeigestil 3n/4-C} , für einige konstant {Anzeigestil C} . Daher, die Konstruktionen von Böröczky für gerade und ungerade (oben diskutiert) sind bestmöglich. Die Minimierung der Anzahl gewöhnlicher Linien steht in engem Zusammenhang mit dem Obstplantagenproblem der Maximierung der Anzahl von Dreipunktlinien, die Green und Tao auch für alle ausreichend großen Punktmengen gelöst haben.[18] Die Anzahl der Verbindungslinien Hauptartikel: Satz von De Bruijn-Erdő (Einfallsgeometrie) Wie Paul Erdős bemerkte, Das Sylvester-Gallai-Theorem impliziert sofort, dass jede Menge von {Anzeigestil n} Punkte, die zumindest nicht kollinear sind {Anzeigestil n} verschiedene Linien. Dieses Ergebnis ist als Satz von De Bruijn-Erdős bekannt. Als Basisfall, das Ergebnis ist eindeutig wahr für {Darstellungsstil n=3} . Für jeden größeren Wert von {Anzeigestil n} , das Ergebnis kann von reduziert werden {Anzeigestil n} verweist auf {Anzeigestil n-1} Punkte, indem Sie eine gewöhnliche Linie und einen der beiden Punkte darauf löschen (Achten Sie darauf, keinen Punkt zu löschen, für den die verbleibende Teilmenge auf einer einzigen Linie liegen würde). Daher, es folgt durch mathematische Induktion. Das Beispiel eines Beinahe-Bleistifts, eine Menge von {Anzeigestil n-1} kollineare Punkte zusammen mit einem zusätzlichen Punkt, der nicht auf derselben Linie wie die anderen Punkte liegt, zeigt, dass diese Schranke eng ist.[16] Generalizations The Sylvester–Gallai theorem has been generalized to colored point sets in the Euclidean plane, und zu Systemen von Punkten und Linien, die algebraisch oder durch Entfernungen in einem metrischen Raum definiert sind. Im Algemeinen, Diese Variationen des Theorems berücksichtigen nur endliche Punktmengen, um Beispiele wie die Menge aller Punkte in der euklidischen Ebene zu vermeiden, die keine gewöhnliche Linie hat.

Colored points A variation of Sylvester's problem, Mitte der 1960er Jahre von Ronald Graham aufgestellt und durch Donald J. Neuer Mann, betrachtet endliche ebene Mengen von Punkten (nicht alle in einer Reihe) denen zwei Farben gegeben werden, und fragt, ob jede solche Menge eine Linie durch zwei oder mehr Punkte hat, die alle dieselbe Farbe haben. In der Sprache der Mengen und Mengenfamilien, eine äquivalente Aussage ist, dass die Familie der kollinearen Teilmengen einer endlichen Punktmenge (nicht alles in einer Zeile) kann Eigenschaft B nicht haben. Ein Beweis dieser Variation wurde von Theodore Motzkin angekündigt, aber nie veröffentlicht; der erste veröffentlichte Beweis stammt von Chakerian (1970).[19] Nicht-reale Koordinaten Die Hesse-Konfiguration, in der die Gerade durch jedes Punktepaar einen dritten Punkt enthält. Das Sylvester-Gallai-Theorem zeigt, dass es nicht durch gerade Linien in der euklidischen Ebene realisiert werden kann, aber es hat eine Realisierung in der komplexen projektiven Ebene.

So wie die euklidische Ebene oder projektive Ebene definiert werden kann, indem reelle Zahlen für die Koordinaten ihrer Punkte verwendet werden (Kartesische Koordinaten für die euklidische Ebene und homogene Koordinaten für die projektive Ebene), analoge abstrakte Systeme von Punkten und Linien können definiert werden, indem andere Zahlensysteme als Koordinaten verwendet werden. Der Sylvester-Gallai-Satz gilt nicht für so definierte Geometrien über endlichen Körpern: für einige auf diese Weise definierte endliche Geometrien, wie das Fano-Flugzeug, die Menge aller Punkte in der Geometrie hat keine gewöhnlichen Linien.[7] Das Sylvester-Gallai-Theorem gilt auch nicht direkt für Geometrien, in denen Punkte Koordinaten haben, die Paare komplexer Zahlen oder Quaternionen sind, aber diese Geometrien haben kompliziertere Analoga des Theorems. Zum Beispiel, in der komplexen projektiven Ebene gibt es eine Konfiguration von neun Punkten, Hessens Konfiguration (die Wendepunkte einer kubischen Kurve), in der jede Linie nicht gewöhnlich ist, Verletzung des Sylvester-Gallai-Theorems. Eine solche Konfiguration ist als Sylvester-Gallai-Konfiguration bekannt, und es kann nicht durch Punkte und Linien der euklidischen Ebene realisiert werden. Eine andere Möglichkeit, das Sylvester-Gallai-Theorem zu formulieren, besteht darin, dass immer dann, wenn die Punkte einer Sylvester-Gallai-Konfiguration in einen euklidischen Raum eingebettet sind, Kolinearitäten bewahren, die Punkte müssen alle auf einer Linie liegen, und das Beispiel der Hesse-Konfiguration zeigt, dass dies für die komplexe projektive Ebene falsch ist. Jedoch, Kelly (1986) bewies ein komplexes Analogon des Sylvester-Gallai-Theorems: immer dann, wenn die Punkte einer Sylvester-Gallai-Konfiguration in einen komplexen projektiven Raum eingebettet sind, die Punkte müssen alle in einem zweidimensionalen Unterraum liegen. Äquivalent, Eine Menge von Punkten in einem dreidimensionalen komplexen Raum, dessen affine Hülle der gesamte Raum ist, muss eine gewöhnliche Linie haben, und muss tatsächlich eine lineare Anzahl gewöhnlicher Linien haben.[20] Ähnlich, Elkies, Pretorius & Swanepoel (2006) zeigte, dass immer dann, wenn eine Sylvester-Gallai-Konfiguration in einen Raum eingebettet ist, der über den Quaternionen definiert ist, seine Punkte müssen in einem dreidimensionalen Unterraum liegen.

Matroids Every set of points in the Euclidean plane, und die Linien, die sie verbinden, können als die Elemente und Ebenen eines Rang-3-orientierten Matroids abstrahiert werden. Die Punkte und Linien von Geometrien, die mit anderen Zahlensystemen als den reellen Zahlen definiert sind, bilden ebenfalls Matroide, aber nicht unbedingt orientierte Matroide. In diesem Zusammenhang, the result of Kelly & Moser (1958) Untere Begrenzung der Anzahl gewöhnlicher Linien kann auf orientierte Matroide verallgemeinert werden: jedes Rang-3-orientierte Matroid mit {Anzeigestil n} Elemente hat mindestens {Anzeigestil 3n/7} Zweipunktlinien, oder äquivalent dazu muss jedes Rang-3-Matroid mit weniger Zweipunktlinien nicht orientierbar sein.[21] Ein Matroid ohne Zweipunktlinien wird als Sylvester-Matroid bezeichnet. Verwandte, Die Kelly-Moser-Konfiguration mit sieben Punkten und nur drei gewöhnlichen Linien bildet eine der verbotenen Minoren für GF(4)-darstellbare Matroide.[15] Distance geometry Another generalization of the Sylvester–Gallai theorem to arbitrary metric spaces was conjectured by Chvátal (2004) und von Chen bewiesen (2006). In dieser Verallgemeinerung, Ein Tripel von Punkten in einem metrischen Raum wird als kollinear definiert, wenn die Dreiecksungleichung für diese Punkte eine Gleichheit ist, und eine Linie wird aus jedem Paar von Punkten definiert, indem wiederholt zusätzliche Punkte eingeschlossen werden, die kollinear mit bereits zu der Linie hinzugefügten Punkten sind, bis keine weiteren Punkte mehr hinzugefügt werden können. Die Verallgemeinerung von Chvátal und Chen besagt, dass jeder endliche metrische Raum eine Linie hat, die entweder alle Punkte oder genau zwei der Punkte enthält.[22] Anmerkungen ^ Elkies, Pretorius & Swanepoel (2006). ^ Nach oben springen: a b Borwein & Moser (1990). ^ Steinberg et al. (1944); Wald (1982). ^ MR0041447 ^ MR0056941 ^ Schäfer (1968). ^ Nach oben springen: a b c d e Aigner & Ziegler (2018). ^ Nach oben springen: a b c Melchior (1941). ^ Aigner & Ziegler (2018, p. 92); Steenrods Beweis wurde in Steinberg et al. kurz zusammengefasst. (1944). ^ Aigner & Ziegler (2018); Pambukkanisch (2009). ^ Coxeter (1948); Pambukkanisch (2009). Für Steinbergs Beweis siehe Steinberg et al. (1944). ^ Mandelkern (2016). ^ Mukhopadhyay & Greene (2012). ^ Nach oben springen: a b Crowe & McKee (1968). ^ Nach oben springen: a b Geelen, Gerards & Kapoor (2000). ^ Nach oben springen: a b Pach & Sharir (2009) ^ Beck (1983). ^ Green & Tao (2013). ^ Für die Geschichte dieser Variation des Problems, siehe auch Grünbaum (1999) ^ Basit et al. (2019). ^ Björner et al. (1993). ^ Er schnappte (2004); Chen (2006); Pambukkanisch (2009) Referenzen Aigner, Martin; Ziegler, Günter M. (2018), "Kapitel 11. Linien in der Ebene und Zerlegung von Graphen", Beweise aus DAS BUCH (6Das D.), Springer, Satz 1, pp. 77–78, doi:10.1007/978-3-662-57265-8_11, ISBN 978-3-662-57265-8 Basit, Abdel; Dvir, Zeev; Nerven, Shubhangi; Wolf, Karl (2019), "Über die durch Mengen bestimmte Zahl gewöhnlicher Geraden im komplexen Raum", Discrete & Computational Geometry, 61 (4): 778–808, arXiv:1611.08740, doi:10.1007/s00454-018-0039-4, HERR 3943495, S2CID 125616042 Beck, Joseph (1983), "Über die Gittereigenschaft des Flugzeugs und einige Probleme von Dirac, Motzkin, und Erdős in kombinatorischer Geometrie", Kombinatorik, 3 (3–4): 281–297, doi:10.1007/BF02579184, HERR 0729781, S2CID 31011939 Björner, Anders; Die Vergnas, Michel; Sturmfels, Bernd; Weiß, Neil; Ziegler, Günter M. (1993), Orientierte Matroide, Enzyklopädie der Mathematik und ihrer Anwendungen, vol. 46, Cambridge: Cambridge University Press, p. 273, ISBN 0-521-41836-4, HERR 1226888 Borwein, P.; Moser, W. Ö. J. (1990), "Ein Überblick über Sylvesters Problem und seine Verallgemeinerungen", Mathematische Gleichungen, 40 (1): 111–135, doi:10.1007/BF02112289, HERR 1069788, S2CID 122052678 Brass, Peter; Moser, Wilhelm; Der Geruch, John (2005), Forschungsprobleme in der Diskreten Geometrie, Berlin: Springer, ISBN 0-387-23815-8 de Bruijn, N. G.; Wald, P. (1948), "Ein kombinatorisches [sic] Problem" (Pdf), Mathematische Untersuchungen, 10: 421–423, HERR 0028289 Chakerian, G. D. (1970), "Sylvesters Problem auf kollinearen Punkten und einem Verwandten", American Mathematical Monthly, 77 (2): 164–167, doi:10.2307/2317330, JSTOR 2317330, HERR 0258659 Chen, Xiaomin (2006), "Der Sylvester – Er schnappte sich das Theorem", Discrete & Computational Geometry, 35 (2): 193–199, doi:10.1007/s00454-005-1216-9, HERR 2195050 Er griff, Vasek (2004), "Sylvester-Gallai-Theorem und metrische Betweenness", Discrete & Computational Geometry, 31 (2): 175–195, doi:10.1007/s00454-003-0795-6, HERR 2060634 Coxeter, H. S. M. (1948), "Ein Problem kollinearer Punkte", American Mathematical Monthly, 55 (1): 26–28, doi:10.2307/2305324, JSTOR 2305324, HERR 0024137 Coxeter, H. S. M. (1969), "12.3 Sylvesters Problem der kollinearen Punkte", Einführung in die Geometrie (2und Aufl.), New York: John Wiley & Sons, pp. 181–182, ISBN 0-471-50458-0 Crowe, D. W.; McKee, T. EIN. (1968), "Sylvesters Problem an kollinearen Punkten", Zeitschrift für Mathematik, 41 (1): 30–34, doi:10.2307/2687957, JSTOR 2687957, HERR 0235452 Csima, J.; Säger, E. (1993), "Es gibt {Anzeigestil 6n/13} gewöhnliche Punkte", Discrete & Computational Geometry, 9: 187–202, doi:10.1007/BF02189318, HERR 1194036 Dirac, G. (1951), "Kollinearitätseigenschaften von Punktmengen", Vierteljährliche Zeitschrift für Mathematik, 2: 221–227, Bibcode:1951QJMat...2..221D, doi:10.1093/qmath/2.1.221, HERR 0043485 Edelsbrunner, Herbert; Guibas, Leonidas J. (1989), "Topologisches Sweeping einer Anordnung", Zeitschrift für Computer- und Systemwissenschaften, 38 (1): 165–194, doi:10.1016/0022-0000(89)90038-X, HERR 0990055 Elkies, Noam; Prätorius, Lou M.; Swanepoel, Konrad J. (2006), "Sylvester-Gallai-Theoreme für komplexe Zahlen und Quaternionen", Discrete & Computational Geometry, 35 (3): 361–373, arXiv:math/0403023, doi:10.1007/s00454-005-1226-7, HERR 2202107, S2CID 1647360 Wald, P. (1943), "Problem 4065", Probleme zur Lösung: 4065–4069, American Mathematical Monthly, 50 (1): 65–66, doi:10.2307/2304011, JSTOR 2304011 Wald, P. (1982), "Persönliche Erinnerungen und Bemerkungen zum mathematischen Werk von Tibor Gallai" (Pdf), Kombinatorik, 2 (3): 207–212, doi:10.1007/BF02579228, HERR 0698647, S2CID 1135308 Geelen, J. F.; Gerhards, EIN. M. H.; Kapoor, EIN. (2000), "Die ausgeschlossenen Minderjährigen für GF(4)-darstellbare Matroide" (Pdf), Zeitschrift für kombinatorische Theorie, Serie B, 79 (2): 247–299, doi:10.1006/jctb.2000.1963, HERR 1769191, vom Original archiviert (Pdf) an 2010-09-24 Grün, Ben; Tao, Terenz (2013), "Auf Sätzen, die wenige gewöhnliche Linien definieren", Discrete & Computational Geometry, 50 (2): 409–468, arXiv:1208.4714, doi:10.1007/s00454-013-9518-9, HERR 3090525, S2CID 15813230 Grünbaum, Branko (1999), "Einfarbige Schnittpunkte in Familien farbiger Linien" (Pdf), Geombinatorik, 9 (1): 3–9, HERR 1698297 Kelly, L. M. (1986), "Eine Auflösung des Sylvester-Gallai-Problems von J. P. Fest", Diskrete und Computergeometrie, 1 (2): 101–104, doi:10.1007/BF02187687, HERR 0834051 Kelly, L. M.; Moser, W. Ö. J. (1958), "Über die Anzahl der ordentlichen Linien bestimmt durch {Anzeigestil n} Punkte", Kanadisches Journal für Mathematik, 10: 210–219, doi:10.4153/CJM-1958-024-6, HERR 0097014, S2CID 123865536 Mandelkern, Markieren (2016), "Eine konstruktive Version des Sylvester-Gallai-Theorems", Ungarisches Mathematisches Journal, 150: 121–130, doi:10.1007/s10474-016-0624-z, HERR 3542040, S2CID 124023963 Melchior, E. (1941), "Über Vielseite der Projektive Ebene", Deutsche Mathematik, 5: 461–475 Motzkin, Th. (1951), "Die Linien und Ebenen, die die Punkte einer endlichen Menge verbinden", Transaktionen der American Mathematical Society, 70 (3): 451–464, doi:10.2307/1990609, JSTOR 1990609, HERR 0041447 Muchopadhyay, A.; Agrawal, A.; Hosabetto, R. M. (1997), "Über das gewöhnliche Linienproblem in der Computergeometrie", Nordisches Journal für Informatik, 4 (4): 330–341, HERR 1607014 Muchopadhyay, , Dinge; Grün, Eugen (2012), "Das gewöhnliche Linienproblem noch einmal aufgegriffen", Computergeometrie: Theorie und Anwendungen, 45 (3): 127–130, doi:10.1016/j.comgeo.2011.10.003, HERR 2853475 Der Geruch, John; Sharir, Micha (2009), "Kapitel 1. Sylvester–Könnte ein Problem sein: Die Anfänge der Kombinatorischen Geometrie", Kombinatorische Geometrie und ihre algorithmischen Anwendungen: Die Alcalá-Vorlesungen, Mathematische Übersichten und Monographien, vol. 152, Amerikanische Mathematische Gesellschaft, pp. 1–12 Pambuccian, Sieger (2009), "Eine umgekehrte Analyse des Sylvester-Gallai-Theorems", Notre Dame Journal of Formal Logic, 50 (3): 245–260, doi:10.1215/00294527-2009-010, HERR 2572973 Shephard, G. C. (1968), "Zwanzig Probleme über konvexe Polyeder, Teil I", Die Mathematische Zeitung, 52 (380): 136–156, doi:10.2307/3612678, JSTOR 3612678, HERR 0231278 Steinberg, R.; Bock, R. C.; Grünwald, T.; Steenrod, N. E. (1944), "Drei-Punkte-Kollinearität (Lösung des Problems 4065)", American Mathematical Monthly, 51 (3): 169–171, doi:10.2307/2303021, JSTOR 2303021 Silvester, J. J. (1893), "Mathematische Frage 11851", Die Bildungszeit, 46 (383): 156 Woodall, H. J. (1893a), "Mathematische Frage 11851 antwortete", Die Bildungszeit, 46 (385): 231 Woodall, H. J. (1893b), "Mathematische Frage 11851 antwortete", Mathematische Fragen und Lösungen aus der Bildungszeit, 59: 98 Externe Links Malkevitch, Joseph (2003), "Ein diskretes geometrisches Juwel", AMS-Feature-Spalte, Amerikanische Mathematische Gesellschaft, ab dem Original archiviert 2006-10-10 Weißstein, Erich W., "Gewöhnliche Linie", MathWorld Proof-Präsentation von Terence Tao auf der 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: Euklidische ebene GeometrieSätze in der diskreten GeometrieMatroid-Theorie