Satz von Szemerédi und Trotter

mathematischer Satz

In der Mathematik ist der Satz von Szemerédi und Trotter ein 1983 von Endre Szemerédi und William T. Trotter bewiesener Lehrsatz der diskreten Geometrie.

Es gibt eine universelle Konstante  , so dass, wenn   eine Menge von   Punkten und   eine Menge von   Geraden in der euklidischen Ebene ist und

 

gilt, dann die Anzahl von Inzidenzen zwischen Punkten aus   und Geraden aus   (d. h. Punkten aus  , die auf Geraden aus   liegen) höchstens

 

ist.

Folgerungen

Bearbeiten

Aus dem Satz von Szemerédi und Trotter folgt eine Vermutung von Erdős und Purdy, dass es eine universelle Konstante   gibt, so dass wenn   eine Menge von   Punkten und   eine Menge von Geraden in der euklidischen Ebene ist, von denen jede mindestens   Punkte für ein   enthält, dann die Anzahl   der Geraden in   der Ungleichung

 

genügt. Weiterhin folgt aus dem Satz von Szemerédi und Trotter eine unabhängig von József Beck bewiesene Vermutung von Dirac, dass es eine universelle Konstante   gibt, so dass wenn   eine Menge von   Punkten der euklidischen Ebene ist, die nicht alle auf derselben Geraden liegen und   die Menge der durch Punktepaare aus   bestimmten Geraden ist, es dann mindestens einen Punkt in   gibt, der auf mehr als   Geraden aus   liegt.

Höher-dimensionale Verallgemeinerungen

Bearbeiten

Aus dem Satz von Szemerédi und Trotter folgt durch Betrachten generischer Projektionen  , dass wenn   eine Menge von   Punkten und   eine Menge von   Geraden im   ist, die Anzahl der Inzidenzen höchstens   für eine universelle Konstante   ist.

Solymosi und Tao bewiesen allgemeiner fast-optimale Abschätzungen für die Anzahl der Inzidenzen zwischen Mengen von Punkten und  -dimensionalen Varietäten beschränkten Grades im  .

Literatur

Bearbeiten
  • E. Szemerédi, W. Trotter: Extremal problems in discrete geometry, Combinatorica, Band 3, 1983, S. 381–392
  • J. Solymosi, T. Tao: An incidence theorem in higher dimensions, Discrete & Computational Geometry, Band 48, 2012, S. 255–280