Satz von Szemerédi und Trotter
# Satz von Szemerédi und Trotter

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.

## Aussage

Es gibt eine universelle Konstante $c_{1}=10^{60}$, so dass, wenn $P$ eine Menge von $n$ Punkten und $L$ eine Menge von $t$ Geraden in der euklidischen Ebene ist und

    ${\sqrt {n}}\leq t\leq {\frac {1}{2}}n(n-1)$

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

    $c_{1}n^{\frac {2}{3}}t^{\frac {2}{3}}$

ist.

## Folgerungen

Aus dem Satz von Szemerédi und Trotter folgt eine Vermutung von Erdős und Purdy, dass es eine universelle Konstante $c_{2}=c_{1}^{3}$ gibt, so dass wenn $P$ eine Menge von $n$ Punkten und $L$ eine Menge von Geraden in der euklidischen Ebene ist, von denen jede mindestens $k$ Punkte für ein $k\leq {\sqrt {n}}$ enthält, dann die Anzahl $t$ der Geraden in $L$ der Ungleichung

    $t<c_{2}{\frac {n^{2}}{k^{3}}}$

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 $c_{3}=10^{-7}c_{2}^{-6}$ gibt, so dass wenn $P$ eine Menge von $n$ Punkten der euklidischen Ebene ist, die nicht alle auf derselben Geraden liegen und $L$ die Menge der durch Punktepaare aus $P$ bestimmten Geraden ist, es dann mindestens einen Punkt in $P$ gibt, der auf mehr als $c_{3}n$ Geraden aus $L$ liegt.

## Höher-dimensionale Verallgemeinerungen

Aus dem Satz von Szemerédi und Trotter folgt durch Betrachten generischer Projektionen $\pi \colon \mathbb {R} ^{d}\to \mathbb {R} ^{2}$, dass wenn $P$ eine Menge von $n$ Punkten und $L$ eine Menge von $t$ Geraden im $\mathbb {R} ^{d}$ ist, die Anzahl der Inzidenzen höchstens $c_{4}(n^{\frac {2}{3}}t^{\frac {2}{3}}+n+t)$ für eine universelle Konstante $c_{4}$ ist.

Solymosi und Tao bewiesen allgemeiner fast-optimale Abschätzungen für die Anzahl der Inzidenzen zwischen Mengen von Punkten und $k$-dimensionalen Varietäten beschränkten Grades im $\mathbb {R} ^{d}$.

