In der Inzidenzgeometrie liefert der Satz von De Bruijn-Erdős , ursprünglich 1948 von Nicolaas Govert de Bruijn und Paul Erdős veröffentlicht [ 1 ] , eine untere Schranke für die Anzahl der Geraden, die durch n Punkte in einer projektiven Ebene bestimmt werden . Aufgrund der Dualität ist dies auch eine Schranke für die Anzahl der Schnittpunkte, die durch eine Geradenkonfiguration bestimmt werden. [ 2 ]

Obwohl der von De Bruijn und Erdős gelieferte Beweis kombinatorischer Natur ist , bemerkten De Bruijn und Erdős in ihrer Arbeit, dass das analoge ( euklidische ) Ergebnis eine Folge des Satzes von Sylvester-Gallai durch Induktion über die Anzahl der Punkte ist. [ 1 ]

Aussage des Theorems

Eine nahezu perfekte Note auf sieben Punkten

Sei P eine Konfiguration von n Punkten in einer projektiven Ebene, die nicht alle auf einer Geraden liegen. Sei t die Anzahl der durch  P bestimmten Geraden . Dann gilt:

  • t ≥ n , und
  • Wenn t = n , haben je zwei Geraden genau einen gemeinsamen Punkt von P. In diesem Fall ist P entweder eine projektive Ebene oder ein Fastbüschel , was bedeutet , dass genau n - 1 Punkte kollinear sind . [ 2 ]

Euklidischer Beweis

Der Satz gilt offensichtlich für drei nicht kollineare Punkte. Wir beweisen ihn durch vollständige Induktion .

Sei n  > 3, dann gilt der Satz auch für n  − 1. Sei P eine Menge von n Punkten, die nicht alle auf einer Geraden liegen. Der Satz von Sylvester-Gallai besagt, dass es eine Gerade gibt, die genau zwei Punkte von P enthält . Solche Geraden mit zwei Punkten heißen gewöhnliche Geraden . Seien a und b die beiden Punkte von P auf einer gewöhnlichen Geraden.

Wenn die Entfernung des Punktes a eine Menge kollinearer Punkte erzeugt, dann erzeugt P ein fast n Geradenbüschel (die n - 1 gewöhnlichen Geraden durch a plus die eine Gerade, die die anderen n - 1 Punkte enthält).

Andernfalls ergibt das Entfernen von a eine Menge P' von n  − 1 Punkten, die nicht alle auf einer Geraden liegen. Nach der Induktionsvoraussetzung bestimmt P' mindestens n − 1 Geraden. Die durch a und b  bestimmte Gerade ist nicht darunter, also bestimmt P mindestens n Geraden.

JH Conways Beweis

John Horton Conway liefert einen rein kombinatorischen Beweis, der folglich auch für Punkte und Geraden über den komplexen Zahlen , Quaternionen und Oktonionen gilt . [ 3 ]

Referenzen

  1. ^ ein b De Bruijn, NG ; Erdős, P. ( 1948), „Über ein kombinatorisches [ sic ] Problem“ (PDF) , Indagationes Mathematicae , 10 : 421–423
  2. ^ a b Batten, Lynn Margaret (1997), „2.2 The De Bruijn–Erdős theorem“, Combinatorics of Finite Geometries (2. Aufl.), Cambridge University Press, S.  25–27 , ISBN 0-521-59014-0
  3. ^ Stasys Jukna, Extremal Combinatorics , Zweite Auflage, Springer Verlag, 2011, Seiten 167 - 168.