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}$.

Literatur

• 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