Satz von Sylvester-Gallai

mathematischer Satz

Der Satz von Sylvester-Gallai ist ein mathematischer Satz der ebenen Geometrie. Er besagt, dass zu jeder endlichen Menge von Punkten, die nicht alle auf einer Geraden, aber in einer Ebene liegen, eine Gerade existiert, die genau zwei Punkte der Menge enthält. Benannt ist er nach James Joseph Sylvester, der die Aussage 1893 in der Educational Times erstmals formulierte,[1] und Tibor Gallai, der 1944 den ersten Beweis veröffentlichte[2], nachdem Paul Erdős das Problem 1943 neu stellte.[3] Der erste bekannte Beweis stammt von Eberhard Melchior aus dem Jahre 1940.[4]

AussageBearbeiten

Sei   eine endliche Menge von in einer Ebene liegenden Punkten, die nicht alle auf einer Geraden liegen. Dann gibt es eine Gerade, die genau zwei Punkte von   enthält.

Eine alternative äquivalente Formulierung lautet:

Sei   eine endliche Menge von Punkten der Ebene mit folgender Eigenschaft: Auf jeder Geraden durch zwei Punkte aus   liegt mindestens ein dritter Punkt dieser Menge. Dann liegen alle Punkte aus   auf einer Geraden.

Die Aussage gilt in unveränderter Form auch in höherdimensionalen Räumen; indem man drei Punkte wählt, die nicht auf einer Geraden liegen, und die durch sie bestimmte Ebene betrachtet, lässt sich das Problem auf den zweidimensionalen Fall zurückführen.

BeweisBearbeiten

Der folgende Beweis geht auf Leroy Milton Kelly zurück.[5] Er wird häufig als Musterbeispiel eines eleganten Beweises zitiert.

Wir betrachten Paare   bestehend aus einer Geraden   durch zwei Punkte aus   und einem Punkt  , der nicht auf   liegt. Da nicht alle Punkte aus   auf einer Geraden liegen, gibt es solche Paare, da die Menge endlich ist, gibt es auch nur endlich viele solcher Paare. Damit können wir ein Paar   auswählen, sodass der Abstand, den   von   hat, minimal wird. Es bleibt zu zeigen, dass   die gewünschte Eigenschaft besitzt, dass es also keinen dritten Punkt aus   gibt, der auf ihr liegt.

 
Konstellation der Punkte und Geraden im entscheidenden Beweisschritt

Dazu nehmen wir an, es gäbe drei solche Punkte. Sei zunächst   der Fußpunkt des Lotes von   auf  . Nach dem Schubfachprinzip gibt es dann zwei Punkte von  , die auf der gleichen Seite von   auf   liegen, diese seien   und  , wobei   näher an   liege als  . Dann ist der Abstand von   zur Geraden durch   und   kleiner als der Abstand von   zu  , denn er ist höchstens so groß wie der Abstand von   zu  , der als Höhe im rechtwinkligen Dreieck   kleiner ist als die Länge der Kathete  .

Dies ist ein Widerspruch zur Wahl von  , denn die Gerade durch   und   bildet demnach zusammen mit dem Punkt   ein Paar mit kleinerem Abstand. Somit muss die Annahme falsch sein, auf   liegen damit wie gewünscht genau zwei Punkte aus  .

Es gibt eine Reihe weiterer Beweise für den Satz von Sylvester-Gallai. So konnte H. S. M. Coxeter zeigen, dass die Anordnungsaxiome allein bereits zum Beweis ausreichen, der Begriff eines Abstandes also nicht notwendig ist.

Weitere Beweise stammen unter anderem von Robert Steinberg (siehe unten), Robert Creighton Buck,[6] Norman Steenrod,[6] Abraham Robinson,[7] G. D. W. Lang (1955)[8] und V. C. Williams (1968).[9] Ein Beweis des äquivalenten projektiv-dualen Satzes stammt von Eberhard Melchior (* 1912) aus dem Jahr 1940 und ist somit der erste Beweis.[10] Er benutzt den Eulerschen Polyedersatz in projektiver Form.

AnwendungBearbeiten

 
Die Fano-Ebene besteht aus 7 Punkten und 7 Geraden, wobei auf jeder Geraden drei Punkte liegen. Daher muss eine der Geraden als Kreis dargestellt werden.

Eine direkte Folge aus dem Satz von Sylvester-Gallai ist die Tatsache, dass sich die Fano-Ebene nicht in die euklidische Ebene einbetten lässt.

Der Satz gilt auch in der projektiven Ebene (Robert Steinberg)[11], sodass man die duale Aussage ableiten kann: Zu einer endlichen Menge von Geraden, die nicht alle durch einen Punkt gehen, gibt es einen Punkt, der auf genau zwei dieser Geraden liegt.

VerallgemeinerungenBearbeiten

Nach dem Satz von Sylvester-Gallai gibt es zu jeder endlichen, nicht kollinearen Punktemenge mindestens eine Gerade, die durch genau zwei der Punkte geht. Von Dirac und Motzkin stammt die Vermutung, dass es zu   Punkten sogar mindestens   solcher Geraden gibt.[12] Andererseits sind für gerade Zahlen   Konstruktionen bekannt, bei denen tatsächlich genau   solcher Geraden existieren, sodass die Schranke nicht verbessert werden kann. Ist   ungerade, so gibt es Anordnungen von   Punkten, zu denen es   Geraden gibt, die genau zwei der Punkte enthalten.[13] Ben Green und Terence Tao konnten zeigen, dass diese Schranken zumindest für große   nicht verbessert werden können, es gibt also eine Konstante  , sodass für jedes   gilt: Liegen   Punkte nicht auf einer Geraden, so gibt es mindestens   (für gerade  ) bzw.   (für ungerade  ) Geraden, die durch genau zwei der Punkte gehen.[14]

LiteraturBearbeiten

EinzelnachweiseBearbeiten

  1. Sylvester, Mathematical Question 11851, Educational Times, Band 59, 1893, S. 98.
  2. Gallai, Problem 4065, American Mathematical Monthly, Band 51, 1944, S. 169–171.
  3. Erdős, Problem 4065, American Mathematical Monthly, Band 50, 1943, S. 65.
  4. Eberhard Melchior: Über Vielseite der projektiven Ebene. In: Deutsche Mathematik, Band 5, 1940, S. 461–475. Als Adresse wurde in der Arbeit München angegeben. Dargestellt ist sein Beweis in S. Felsner: Geometric Graphs and Arrangements. Vieweg, 2004, S. 72 f.
  5. Veröffentlicht in H. S. M. Coxeter, A problem of collinear points, American Mathematical Monthly, Band 55, 1948, S. 26–28.
  6. a b Erdős, Solution to problem 4065, American Mathematical Monthly, Band 51, 1944, S. 169–171.
  7. Siehe Motzkin, The lines and planes connecting the points of a finite set, Trans. Amer. Math. Soc., Band 70, 1951, S. 451–464.
  8. Lang, The dual of a well known problem, Mathematical Gazette, Band 39, 1955, S. 314.
  9. Williams, A proof of Sylvester´s theorem on collinear points, American Mathematical Monthly, Band 75, 1968, S. 980–982.
  10. Melchior, Über Vielseite der Projektiven Ebene, Deutsche Mathematik, Band 5, 1940, S. 461–475. Dargestellt in S. Felsner Geometric Graphs and Arrangements, Vieweg 2004, S. 72f
  11. R. Steinberg, Three point collinearity, American Mathematical Monthly, Band 51, 1944, S. 169–171. Ein projektiver Beweis.
  12. G. A. Dirac: Collinearity Properties of Sets of Points. In: The Quarterly Journal of Mathematics. 1951, Vol. 2. S. 221–227. doi:10.1093/qmath/2.1.221, Th. Motzkin: The lines and planes connecting the points of a finite set. In: Transactions of the American Mathematical Society. 1951, Vol. 70. S. 451–464. doi:10.2307/1990609
  13. D. W. Crowe, T. A. McKee: Sylvester’s Problem on Collinear Points. In: Mathematics Magazine. 1968, Vol. 41, No. 1. S. 30–34. doi:10.2307/2687957
  14. Ben Green, Terence Tao: On Sets Defining Few Ordinary Lines. In: Discrete & Computational Geometry. 2013, Vol. 50, No. 2. S. 409–468. doi:10.1007/s00454-013-9518-9