Satz von de Bruijn-Erdős (Inzidenzgeometrie)

Der Satz von de Bruijn-Erdős in der Inzidenzgeometrie gibt eine untere Schranke für die Anzahl der Geraden, die durch n Punkte in der projektiven Ebene bestimmt werden. Der Satz wurde 1948 von Nicolaas Govert de Bruijn und Paul Erdős bewiesen.

Über das Dualitätsprinzip der projektiven Geometrie liefert er auch eine untere Schranke für die Anzahl der Schnittpunkte durch eine Menge von n Geraden.

Sei P eine Konfiguration von n Punkten in der projektiven Ebene, die nicht alle auf einer Geraden liegen (nicht alle kollinear sind). Sei t die Anzahl der Geraden, die durch die Punkte aus P bestimmt werden, dann ist nach dem Satz von Erdös und De Bruijn

• $t\geq n$
• Falls $t=n$ haben je zwei Geraden genau einen Punkt aus P gemeinsam. P ist dann die projektive Ebene oder ist ein „near pencil“ (Geradenbüschel, das heißt n-1 Punkte liegen auf einer Geraden und einer außerhalb). Ein „near pencil“ wird im Fall der Formulierung des Satzes für lineare Räume auch entarteter linearer Raum genannt (die projektive Ebene und „near pencils“ bilden zusammen die verallgemeinerte projektive Ebene)

Ein near pencil (Geradenbüschel) aus sieben Punkten

Der Beweis lässt sich allgemeiner für lineare Räume definieren, von denen projektive Ebenen Beispiele sind. In der allgemeineren Formulierung formulierten und bewiesen auch De Bruijn und Erdös den Satz:

Gegeben sei eine endliche Menge P von $n\geq 3$ Elementen und $A_{i}$ ($i=1,\cdots ,m$) echte Teilmengen von P, so dass jedes Paar von Elementen aus P in genau einem $A_{i}$ enthalten ist, dann gilt $m\geq n$.

Der Beweis von De Bruijn und Erdős ist kombinatorisch, es gibt aber auch, wie Erdös und De Bruijn bemerkten und in ihrer Arbeit ausführten, einen geometrischen Beweis (für den Fall der projektiven oder euklidischen Ebene), der den Satz von Sylvester-Gallai benutzt und per vollständiger Induktion über die Anzahl der Punkte fortschreitet. Manchmal wird der Satz von De Bruijn und Erdös auch zusätzlich nach Haim Hanani benannt.

Einen weiteren sehr kurzen kombinatorischen Beweis gab John Horton Conway, der auch manchmal Theodore Motzkin zugeschrieben wird, und es gibt auch einen kurzen Beweis über Lineare Algebra und Inzidenzmatrizen.

Es gibt noch einen weiteren nach Erdös und De Bruijn benannten Satz aus der Graphentheorie (Satz von de Bruijn-Erdős (Graphentheorie)).

Geometrischer Beweis

Der Satz gilt offensichtlich für drei Punkte. Der Beweis schreitet durch Induktion fort. Angenommen der Satz gilt für n-1 Punkte. Man betrachte eine Menge P von n Punkten, die nicht alle kollinear sind. Dann gibt es nach dem Satz von Sylvester-Gallai eine Gerade mit genau zwei Punkten a,b aus P. Entfernt man Punkt a können zwei Fälle auftreten:

• die übrigen Punkte von P sind kollinear, dann hat P die Konfiguration eines near pencil mit n Geraden.
• die übrigen (n-1) Punkte sind nicht kollinear. Nach Induktionsvoraussetzung bestimmen sie mindestens (n-1) Geraden. Da die Gerade durch a und b nicht darunter ist, werden mindestens n Geraden durch P bestimmt.

Literatur

• Lynn Margaret Batten: Combinatorics of Finite Geometries, Cambridge UP, 2. Auflage 1997, S. 25–27
• Lynn Margaret Batten, Albrecht Beutelspacher: Theory of finite linear spaces, Cambridge UP, 1993, 2009, S. 15f