Satz von Sylvester-Gallai

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]

Aussage

Sei ${\displaystyle {\mathcal {P}}}$ 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 ${\displaystyle {\mathcal {P}}}$ enthält.

Eine alternative äquivalente Formulierung lautet:

Sei ${\displaystyle {\mathcal {P}}}$ eine endliche Menge von Punkten der Ebene mit folgender Eigenschaft: Auf jeder Geraden durch zwei Punkte aus ${\displaystyle {\mathcal {P}}}$ liegt mindestens ein dritter Punkt dieser Menge. Dann liegen alle Punkte aus ${\displaystyle {\mathcal {P}}}$ 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.

Beweis

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

Wir betrachten Paare ${\displaystyle (g,P)}$ bestehend aus einer Geraden ${\displaystyle g}$ durch zwei Punkte aus ${\displaystyle {\mathcal {P}}}$ und einem Punkt ${\displaystyle P\in {\mathcal {P}}}$, der nicht auf ${\displaystyle g}$ liegt. Da nicht alle Punkte aus ${\displaystyle {\mathcal {P}}}$ auf einer Geraden liegen, gibt es solche Paare. Außerdem gibt es auch nur endlich viele solche Paare, da die Menge ${\displaystyle {\mathcal {P}}}$ endlich ist. Damit können wir ein Paar ${\displaystyle (g,P)}$ auswählen, sodass der Abstand, den ${\displaystyle P}$ von ${\displaystyle g}$ hat, minimal wird. Es bleibt zu zeigen, dass ${\displaystyle g}$ die gewünschte Eigenschaft besitzt, dass es also keinen dritten Punkt aus ${\displaystyle {\mathcal {P}}}$ 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 ${\displaystyle F}$ der Fußpunkt des Lotes von ${\displaystyle P}$ auf ${\displaystyle g}$. Nach dem Schubfachprinzip gibt es dann zwei Punkte von ${\displaystyle {\mathcal {P}}}$, die auf der gleichen Seite von ${\displaystyle F}$ auf ${\displaystyle g}$ liegen, diese seien ${\displaystyle A}$ und ${\displaystyle B}$, wobei ${\displaystyle B}$ näher an ${\displaystyle F}$ liege als ${\displaystyle A}$. Dann ist der Abstand von ${\displaystyle B}$ zur Geraden durch ${\displaystyle A}$ und ${\displaystyle P}$ kleiner als der Abstand von ${\displaystyle P}$ zu ${\displaystyle g}$, denn er ist höchstens so groß wie der Abstand von ${\displaystyle F}$ zu ${\displaystyle AP}$, der als Höhe im rechtwinkligen Dreieck ${\displaystyle APF}$ kleiner ist als die Länge der Kathete ${\displaystyle PF}$.

Dies ist ein Widerspruch zur Wahl von ${\displaystyle (g,P)}$, denn die Gerade durch ${\displaystyle A}$ und ${\displaystyle P}$ bildet demnach zusammen mit dem Punkt ${\displaystyle B}$ ein Paar mit kleinerem Abstand. Somit muss die Annahme falsch sein, auf ${\displaystyle g}$ liegen damit wie gewünscht genau zwei Punkte aus ${\displaystyle {\mathcal {P}}}$.

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–1956) aus dem Jahr 1940 und ist somit der erste Beweis.^[10] Er benutzt den Eulerschen Polyedersatz in projektiver Form.

Anwendung

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.

Eine Folgerung ist ein geometrischer Beweis des Satzes von de Bruijn und Erdös in der Inzidenzgeometrie.

Verallgemeinerungen

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 ${\displaystyle n}$ Punkten sogar mindestens ${\displaystyle \lfloor n/2\rfloor }$ solcher Geraden gibt.^[12] Andererseits sind für gerade Zahlen ${\displaystyle n}$ Konstruktionen bekannt, bei denen tatsächlich genau ${\displaystyle n/2}$ solcher Geraden existieren, sodass die Schranke nicht verbessert werden kann. Ist ${\displaystyle n}$ ungerade, so gibt es Anordnungen von ${\displaystyle n}$ Punkten, zu denen es ${\displaystyle 3\lfloor n/4\rfloor }$ Geraden gibt, die genau zwei der Punkte enthalten.^[13] Ben Green und Terence Tao konnten zeigen, dass diese Schranken zumindest für große ${\displaystyle n}$ nicht verbessert werden können, es gibt also eine Konstante ${\displaystyle n_{0}}$, sodass für jedes ${\displaystyle n>n_{0}}$ gilt: Liegen ${\displaystyle n}$ Punkte nicht auf einer Geraden, so gibt es mindestens ${\displaystyle n/2}$ (für gerade ${\displaystyle n}$) bzw. ${\displaystyle 3\lfloor n/4\rfloor }$ (für ungerade ${\displaystyle n}$) Geraden, die durch genau zwei der Punkte gehen.^[14]

Literatur

• Martin Aigner, Günter M. Ziegler: Das Buch der Beweise. Springer, Berlin, 4. Aufl., 2015. ISBN 978-3-662-44456-6. Kapitel 11: Geraden in der Ebene und Zerlegungen von Graphen.
• Peter Borwein, William Oscar Jules Moser: A survey of Sylvester's problem and its generalizations, Aequationes Mathematicae, Band 40, 1990, S. 111–135, pdf