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.

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

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

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

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

ist.

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

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

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

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

• 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