Der Satz von Sylvester-Gallai in der Geometrie besagt, dass entweder eine endliche Anzahl von Punkten in der euklidischen Ebene gegeben ist
Benannt wurde es nach James Joseph Sylvester, der es 1893 als Problem darstellte, und Tibor Gallai, der 1944 einen der ersten Beweise dieses Theorems veröffentlichte.
Eine Linie, die genau zwei Punkte enthält, wird als gewöhnliche Linie bezeichnet. Gemäß einer Verstärkung des Satzes hat jede endliche Punktmenge (nicht alle auf einer Linie) mindestens eine lineare Anzahl gewöhnlicher Linien. Es gibt einen Algorithmus, der eine gewöhnliche Linie in einem Satz von n Zeitpunkten findet, die proportional zu n log n im schlimmsten Fall sind. [1]
History [1] 19659006] [ edit ]
Das Theorem von Sylvester-Gallai wurde von JJ Sylvester (1893) als Problem gestellt. 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 (der Hesse-Konfiguration) bilden, in denen sich jeder befindet Linie, die durch zwei der Punkte bestimmt wird, enthält einen dritten Punkt. Der Satz von Sylvester-Gallai impliziert, dass es unmöglich ist, für alle neun dieser Punkte echte Koordinaten zu haben.
Woodall (1893) behauptete, einen kurzen Beweis des Satzes von Sylvester-Gallai zu haben, der jedoch bereits als unvollständig bezeichnet wurde der Zeitpunkt der Veröffentlichung. Eberhard Melchior (1941) bewies den Satz (und tatsächlich ein etwas stärkeres Ergebnis) in einer äquivalenten Formulierung, seinem projektiven Dual. Paul Erdős (1943) wußte nichts von Melchior's Beweis und nannte erneut die Vermutung, die zuerst von Tibor Gallai und bald darauf von anderen Autoren bewiesen wurde. [4]
Projektive und duale Versionen [ edit ] 19659007] Die Frage nach der Existenz einer normalen Linie kann auch für Punkte in der realen Projektionsebene RP 2 anstelle der Euklidischen Ebene gestellt werden. Die euklidische Ebene kann als eine Teilmenge der Projektionsebene betrachtet werden, aber die zusätzlichen Punkte und Linien der Projektionsebene ändern das Problem nicht, da jeder endliche Satz von Projektionspunkten in einen euklidischen Punktsatz umgewandelt werden kann, ohne dessen Satz von zu ändern gewöhnliche Linien. Daher gibt es auch in der anderen Ebene jedes Muster von Schnittpunkten und Linien, das in einer dieser beiden Ebenentypen vorhanden ist. Der projek- tive Gesichtspunkt erlaubt es jedoch, bestimmte Konfigurationen einfacher zu beschreiben. Durch die projektive Dualität entspricht das Vorhandensein einer gewöhnlichen Linie für eine Menge nicht kollinearer Punkte in RP 2 dem Vorhandensein eines gewöhnlichen Punktes in einer nicht-trivialen Anordnung von endlich vielen Linien . Eine Anordnung wird als trivial bezeichnet, wenn alle ihre Linien einen gemeinsamen Punkt durchlaufen, und ansonsten nicht trivial; Ein gewöhnlicher Punkt ist ein Punkt, der zu genau zwei Linien gehört. Eine Beschreibung des ursprünglichen Beweises des Satzes von Gallai finden sich z. Borwein & Moser (1990).
Kellys Beweis [ edit ]
Notation für Kellys Beweis Dieser Nachweis ist Leroy Milton Kelly zu verdanken.
Angenommen, eine endliche Menge S von Punkten ist nicht alle kollinear. Definieren Sie eine Verbindungslinie als Linie, die mindestens zwei Punkte in der Sammlung enthält. Nach der Endlichkeit muss es einen Punkt P und eine Verbindungslinie ℓ geben, die einen positiven Abstand voneinander haben, aber näher als alle anderen Punktlinienpaare sind. Wir werden beweisen, dass im Widerspruch normal ist.
Angenommen, ] ist nicht gewöhnlich. Dann durchläuft es mindestens drei Punkte von S . Mindestens zwei davon befinden sich auf derselben Seite von P 'der senkrechten Projektion von P auf [1945. Nennen Sie sie B und C wobei B P ' am nächsten ist (und möglicherweise mit ihm zusammenfällt ) . Zeichnen Sie die Verbindungslinie m die durch P und C, und die Senkrechte von B B bis 19459011 führt m . Dann ist BB ' kürzer als PP' . Dies folgt aus den Tatsachen, dass PP'C und BB'C ähnliche Dreiecke sind, die ineinander liegen.
Dies widerspricht jedoch der ursprünglichen Definition von P und [1945 als Punktlinienpaar mit der kleinsten positiven Entfernung. Die Annahme, dass nicht gewöhnlich ist, kann nicht wahr sein, QED.
Melchior's Beweis [ edit ]
Im Jahr 1941 (also vor der Veröffentlichung von Erdős Frage und Gallais nachfolgendem Beweis) zeigte Melchior, dass jede nicht-triviale Anordnung von Linien in der Projektionsebene dies hat mindestens drei gewöhnliche Punkte. In der Dualität bedeutet dieses Ergebnis auch, dass jede endliche nichttriviale Menge von Punkten auf der Ebene mindestens drei gewöhnliche Linien hat.
Melchior beobachtete, dass für jeden in die reale Projektionsebene eingebetteten Graphen die Formel V - E + F muss gleich 1 sein, die Euler-Eigenschaft der Projektionsebene. Hier V E und F sind die Anzahl der Scheitelpunkte, Kanten bzw. Flächen des Graphen. Jede nichttriviale Linienanordnung auf der Projektionsebene definiert einen Graphen, in dem jede Fläche durch mindestens drei Kanten begrenzt ist und jede Kante zwei Flächen begrenzt. Doppelzählung ergibt also die zusätzliche Ungleichung F ≤ 2 E / 3. Die Verwendung dieser Ungleichung, um F von der Euler-Charakteristik zu beseitigen, führt zu der Ungleichung E ≤ 3 V - 3. Aber wenn jeder Scheitelpunkt der Anordnung der Kreuzungspunkt wäre von drei oder mehr Zeilen wäre die Gesamtanzahl der Kanten mindestens 3 V was dieser Ungleichung widerspricht. Daher müssen einige Eckpunkte der Kreuzungspunkt von nur zwei Linien sein, und wie Melchior sorgfältigere Analyse zeigt, sind mindestens drei gewöhnliche Eckpunkte erforderlich, um die Ungleichung zu erfüllen E ≤ 3 V ] - 3.
Melchior's Ungleichheit [ edit ]
Durch ein ähnliches Argument konnte Melchior ein allgemeineres Ergebnis nachweisen. Für jeden k ≥ 2 sei t k die Anzahl der Punkte, auf die k Vorfälle auftreten. Dann
oder gleichwertig
Coxeters Beweis [[19659067] edit ]
H. S. M. Coxeter (1969) lieferte einen weiteren Beweis des Sylvester-Gallai-Theorems innerhalb der geordneten Geometrie, einer Axiomatisierung der Geometrie, die nicht nur die euklidische Geometrie, sondern auch mehrere andere verwandte Geometrien umfasst. Siehe Pambuccian (2009) für minimale Axiomsysteme, in denen der Satz von Sylvester-Gallai bewiesen werden kann.
Die Anzahl der gewöhnlichen Linien [ edit ]
Die beiden bekannten Beispiele von Punktmengen mit weniger als n / 2 gewöhnlichen Linien. Während der Theorem von Sylvester-Gallai dies feststellt Eine Anordnung von Punkten, die nicht alle kollinear sind, muss eine normale Linie bestimmen, sie sagt nicht aus, wie viele Punkte bestimmt werden müssen.
Es sei t 2 ( n ) die Mindestzahl gewöhnlicher Linien, die über jedem Satz von n nichtkollinearen Punkten bestimmt wurde . Melchior bewies, dass t 2 ( n ) ≥ 3 de Bruijn und Erdős (1948) stellten die Frage, ob sich t 2 ( n ) mit n der Unendlichkeit nähert. Theodore Motzkin (1951) bestätigte dies durch einen Beweis, dass . Gabriel Dirac (1951) vermutete, dass für alle Werte von n eine Vermutung, dass steht noch bis 2013 [update]. Dies wird häufig als Dirac-Motzkin-Vermutung bezeichnet, siehe beispielsweise Brass, Moser & Pach (2005, S. 304). Kelly & Moser (1958) bewies, dass t 2 ( n ) ≥ 3 n / 7.
Beispiel von Böröczkys (gerader) Konfiguration mit 10 Punkten, die 5 normale Linien bestimmen. Diracs vermutete untere Schranke ist asymptotisch die bestmögliche, da es eine nachgewiesene übereinstimmende obere Schranke gibt. t 2 ( n ) ≤ n / 2 für sogar n größer als vier. Die durch Károly Böröczky errichtete Konstruktion, die diese Grenze erreicht, besteht aus den Eckpunkten eines regulären m -Kegels in der realen Projektionsebene und einem weiteren m n (also 19659074) n = 2 m
) auf der Linie im Unendlichen, die jeder der durch Eckpunktpaare bestimmten Richtungen entspricht; Obwohl es m ( m - 1) / 2 Paare gibt, bestimmen sie nur m verschiedene Richtungen. Diese Anordnung hat nur m gewöhnliche Linien, nämlich diejenigen, die einen Scheitelpunkt v mit dem Punkt unendlich verbinden, der der durch v ' s benachbarte Scheitelpunkte bestimmten Linie entspricht . Man beachte, dass, wie bei jeder endlichen Konfiguration in der realen Projektionsebene, diese Konstruktion so gestört werden kann, dass alle Punkte endlich sind, ohne die Anzahl der gewöhnlichen Linien zu verändern. [6] Für ungerade ] n sind nur zwei Beispiele bekannt, die der unteren gebundenen Vermutung von Dirac entsprechen, dh mit t 2 ( n ) = ( n ] - 1) / 2. Ein Beispiel von Kelly & Moser (1958) besteht aus den Eckpunkten, Randmittelpunkten und dem Schwerpunkt eines gleichseitigen Dreiecks; Diese sieben Punkte bestimmen nur drei gewöhnliche Linien. Die Konfiguration, in der diese drei gewöhnlichen Linien durch eine einzige Linie ersetzt werden, kann nicht in der euklidischen Ebene realisiert werden, sondern bildet einen endlichen projizierten Raum, der als Fano-Ebene bekannt ist. Aufgrund dieser Verbindung wurde das Kelly-Moser-Beispiel auch als Nicht-Fano-Konfiguration bezeichnet. [7] Das andere Gegenbeispiel von McKee [6] besteht aus zwei regulären Fünfecken, die mit dem Mittelpunkt von Rand-an-Rand miteinander verbunden sind die gemeinsame Kante und vier Punkte auf der Linie unendlich in der Projektionsebene; Zu diesen 13 Punkten gehören 6 normale Linien. Modifikationen der Konstruktion von Böröczky führten zu einer Anzahl von ungeraden Punktzahlen mit gewöhnliche Linien [8]
2009 bewiesen Csima & Sawyer (1993), dass außer wenn n ist sieben. Asymptotisch beträgt diese Formel bereits 12/13 ~ 92,3% der nachgewiesenen oberen Schranke n / 2. Der Fall n = 7 ist eine Ausnahme, da sonst die Kelly-Moser-Konstruktion ein Gegenbeispiel wäre; ihre Konstruktion zeigt, dass t 2 (7) ≤ 3 ist. Wenn jedoch der Csima-Sawyer für n = 7 gilt, würde er behaupten, t [19659075] 2 (7) ≥ 4.
Ein eng verwandtes Ergebnis ist der Satz von Beck, der einen Kompromiss zwischen der Anzahl der Linien mit wenigen Punkten und der Anzahl der Punkte auf einer einzelnen Linie angibt.
Ben Green und Terence Tao zeigten, dass für alle ausreichend großen Punktmengen, n > n 0 die Anzahl der gewöhnlichen Linien tatsächlich mindestens n ist / 2. Wenn n ungerade ist, beträgt die Anzahl der gewöhnlichen Leitungen mindestens 3 n / 4 - C für einige Konstante C . Somit sind die Konstruktionen von Böröczky für gerade und ungerade (oben diskutiert) am besten möglich.
Die Anzahl der Verbindungsleitungen [ edit
![war ] t_ {2} geq { sqrt {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70dd6dbb11e05dbcc859598de29e9b80275b95f5)
Wie Paul Erdős bemerkte, die Sylvester-Gallai Theorem impliziert sofort, dass jede Menge von n Punkten, die nicht kollinear sind, mindestens n verschiedene Linien bestimmt. Als Basisfall gilt das Ergebnis eindeutig für n = 3. Bei einem größeren Wert von n kann das Ergebnis von n auf n - 1 Punkte durch Löschen einer normalen Linie und eines der beiden Punkte. So folgt es durch mathematische Induktion. Das Beispiel eines Bleistifts (ein Satz von n - 1 kollineare Punkte zusammen mit einem zusätzlichen Punkt, der nicht auf derselben Linie wie die anderen Punkte liegt) zeigt, dass diese Grenze eng ist. [8]
Verallgemeinerungen [ edit ]
Der Satz von Sylvester-Gallai gilt nicht direkt für Mengen von unendlich vielen Punkten oder Punkten Geometrien über endlichen Feldern. Die Menge aller Punkte in der Ebene ist zum Beispiel eine unendliche Menge ohne gewöhnliche Linien, und die Menge aller Punkte in einer endlichen Geometrie hat auch keine normalen Linien.
Bei Geometrien, die mit komplexen Zahlen- oder Quaternionkoordinaten definiert werden, ist die Situation jedoch komplizierter. Zum Beispiel gibt es in der komplexen Projektionsebene eine Konfiguration mit neun Punkten, der Hesse-Konfiguration (den Wendepunkten einer kubischen Kurve), in der jede Linie ungewöhnlich ist und gegen den Satz von Sylvester-Gallai verstößt. Eine solche Konfiguration ist als Sylvester-Gallai-Konfiguration bekannt und kann nicht durch Punkte und Linien der euklidischen Ebene realisiert werden. Das Sylvester-Gallai-Theorem kann auch anders ausgedrückt werden: Immer, wenn die Punkte einer Sylvester-Gallai-Konfiguration in einen euklidischen Raum eingebettet sind und Colinearitäten erhalten, müssen alle Punkte auf einer einzigen Linie liegen. Dies zeigt sich am Beispiel der Hesse-Konfiguration ist falsch für die komplexe Projektionsebene. Kelly (1986) erwies sich jedoch als ein komplexes Analogon zum Satz von Sylvester-Gallai: Wenn die Punkte einer Sylvester-Gallai-Konfiguration in einen komplexen Projektionsraum eingebettet werden, müssen die Punkte alle in einem zweidimensionalen Unterraum liegen. In ähnlicher Weise zeigten Elkies, Pretorius & Swanepoel (2006), dass jedes Mal, wenn sie in einen über den Quaternionen definierten Raum eingebettet sind, sie in einem dreidimensionalen Unterraum liegen müssen.
Jede Menge von Punkten in der Ebene und die sie verbindenden Linien können als Elemente und Ebenen eines Rang-3-orientierten Matroiden abstrahiert werden. In diesem Zusammenhang kann das Ergebnis von Kelly & Moser (1958), das die Anzahl der gewöhnlichen Linien unterschreitet, zu orientierten Matroiden verallgemeinert werden: Jedes auf Rang 3 orientierte Matroid mit n Elementen hat mindestens 3 n / 7 Zwei-Punkt-Linien, oder gleichwertig jedes Rang-3-Matroid mit weniger Zweipunkt-Linien muss nicht orientierbar sein. [10] Ein Matroid ohne Zwei-Punkt-Linien wird als Sylvester-Matroid bezeichnet. In ähnlicher Weise bildet die Kelly-Moser-Konfiguration mit sieben Punkten und nur drei gewöhnlichen Linien eine der verbotenen Minderjährigen für GF (4) -repräsentierbare Matroide. [7]
Siehe auch [
. Referenzen [ edit ]
- Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; Weiß, Neil; Ziegler, Günter M. (1993), Orientierte Matroiden Enzyklopädie der Mathematik und ihrer Anwendungen, 46 Cambridge: Cambridge University Press, p. 273, ISBN 0-521-41836-4, MR 1226888
- Borwein, P .; Moser, WOJ (1990), "Eine Übersicht über das Problem von Sylvester und seine Verallgemeinerungen", Aequationes Mathematicae 40 (1): 111–135, doi: 10.1007 / BF02112289 19659160] Brass, Peter; Moser, William; Pach, János (2005), Forschungsprobleme in der diskreten Geometrie Berlin: Springer, ISBN 0-387-23815-8 .
- de Bruijn, N. G .; Erdős, P. (1948), "Ein kombinatorisches [sic] Problem" (PDF) Indagationes Mathematicae 10 : 421–423 .
- Coxeter, HSM (1969), Einführung in die Geometrie New York: John Wiley & Sons, S. 181–182, ISBN 0-471-50458-0 Crowe DW; McKee, TA (1968), "Sylvesters Problem in kollinearen Punkten", Mathematics Magazine 41 (1): 30–34, Doi: 10.2307 / 2687957, JSTOR 2687957 19659168] Csima, J .; Sawyer, E. (1993), "Es gibt 6 n / 13 gewöhnliche Punkte", Discrete & Computational Geometry 9 : 187–202, doi: 10.1007 / BF02189318
- Dirac, G. (1951), "Kollinearitätseigenschaften von Punktmengen", Quart. J. Math. 2 : 221–227, Bibcode: 1951QJMat ... 2..221D, doi: 10.1093 / qmath / 2.1.221 Elkies, Noam ; Pretorius, Lou M .; Swanepoel, Konrad J. (2006), "Sylvester-Gallai-Theoreme für komplexe Zahlen und Quaternionen", Discrete and Computational Geometry 35 (3): 361–373, arXiv: math / 0403023 doi: 10.1007 / s00454-005-1226-7, MR 2202107 .
- Erdős, P. (1943), "Problem 4065", Probleme für die Lösung: 4065–4069 American Mathematical Monthly 50 (1): 65–66, doi: 10.2307 / 2304011, JSTOR 2304011
- Erdős, P. (1982), Persönliche Erinnerungen und Anmerkungen zur mathematischen Arbeit von Tibor Gallai " (PDF) Combinatorica 2 (3): 207–212, doi: 10.1007 / BF02579228 .
- Geelen, JF; Gerards, A., M. H .; Kapoor, A. (2000), "Die ausgeschlossenen Minderjährigen für GF (4) -repräsentable Matroids" (PDF) Zeitschrift für kombinatorische Theorie Serie B, 79 (2): 247–299, doi: 10.1006 / jctb.2000.1963, MR 1769191, archiviert vom Original (PDF) am 2010-09-24 .
- Green, Ben ; Tao, Terence (2013), "Auf Sets, die einige gewöhnliche Linien definieren", Discrete & Computational Geometry 50 (2): 409–468, arXiv: 1208.4714 doi: 10.1007 / s00454-013-9518-9, MR 3090525
- Kelly, LM (1986), "Eine Lösung des Sylvester-Gallai-Problems von JP Serre", Diskrete und Computational Geometry 1 (2): 101–104, doi: 10.1007 / BF02187687 .
- Kelly, LM; Moser, W. O. J. (1958), "Über die Anzahl der gewöhnlichen Linien, bestimmt durch n Punkte", Can. J. Math. 10 : 210–219, doi: 10.4153 / CJM-1958-024-6 .
- Mandelkern, Mark (2016), "Eine konstruktive Version von The Sylem-Gallai-Theorem ", Acta Mathematica Hungarica 150 : 121–130, doi: 10.1007 / s10474-016-0624-z
- Melchior, E. (1941), "Über Vielseite der Projektiven Ebene", Deutsche Mathematik 5 : 461–475 Motzkin, Th. (1951), "Die Linien und Ebenen, die die Punkte einer endlichen Menge verbinden", Transactions der American Mathematical Society 70 (3): 451–464, doi: 10.2307 / 1990609, JSTOR 1990609 .
- Mukhopadhyay, A .; Agrawal, A .; Hosabettu, RM (1997), "Über das gewöhnliche Linienproblem in der Berechnungsgeometrie", Nordic Journal of Computing 4 (4): 330–341 . Mukhopadhyay, A .; Greene, E. (2007), "Das Problem der gewöhnlichen Linie überarbeitet", Proc. 19. kanadische Konferenz über Computational Geometry (PDF) S. 61–64 .
- Pach, János; Sharir, Micha (2009), "Kapitel 1. Sylvester-Gallai-Problem: Die Anfänge der kombinatorischen Geometrie", Kombinatorische Geometrie und ihre algorithmischen Anwendungen: Die Alcalá-Vorlesungen mathematische Untersuchungen und Monographien, 152 American Mathematical Society, Seiten 1–12 .
- Pambuccian, V. (2009), "Eine Umkehranalyse des Satzes von Sylvester-Gallai", Notre Dame Journal of Formal Logic 50 (3): 245–260, doi: 10.1215 / 00294527-2009-010 .
- Steinberg, R .; Buck, R. C .; Grünwald, T .; Steenrod, NE (1944), "Dreipunktkollinearität (Lösung zu Problem 4065)", American Mathematical Monthly 51 (3): 169–171, doi: 10.2307 / 2303021, JSTOR 2303021 .
- Sylvester, JJ (1893), "Mathematische Frage 11851", The Educational Times 46 (383): 156 ] Woodall, HJ (1893), "Mathematische Frage 11851 hat geantwortet", The Educational Times 46 (385): 231 .
- Woodall, HJ (1893) , "Mathematische Frage 11851 beantwortet", Mathematische Fragen und Lösungen aus der Bildungszeit 59 : 98 .
No comments:
Post a Comment